Measuring Performance
There are three ways to measure the performance of the algorithm:
1. Big Theta (Actual or Average case)
2. Big O (Worst Case/ Upper Bound)
3. Big Omega (best case/Lower Bound)
Organizing Data Efficiently with Common Data Structure
1. Dynamic Array: Can grow dynamically and maintain the position. In C#, it's List, In Java its Array List.
So how to create a dynamic array using a static array. First, Copy all the elements into the static array to its maximum size if need to insert more elements then create one more array of just double the size of the previous array and copy the elements from the previous array to the new one created .
2. Hash Table : Come in two flavors
1. Hash Set , which adds value directly like dynamic arrays.
2. Dictionary/Hash Map , which has key pair values.
3. Linked List : Individual elements are stored in a separate container and keep the address of previous and next element. This is called doubly linked list. Head and tail pointer contain first and last elements of the linked list.
4. Priority Queue : C# does not provide this data structure but provide some libraries (C5.IntervalHeap) to implement a priority queue.
A Priority Queue is just a queue in which element en-queued from back an de-queue from the front.
Priority Queue maintains the order of element arrived and de-queued based on weight.
Priority Queue used a heap to sort the arrays.
Overall 4 data structure Hash Set is faster than Priority Queue then linked list and in the last List.
Different type of algorithms:
Graph : Graph is a data structure which has node and edges . A graph can be directed and undirected and have cyclic .
A tree is a special type of graph which don't have any direction or cycle.
We can traverse in graph by two ways:
1. DFS (Depth First Traversal) : Use Stack to traverse
2. BFS (Breadth First Traversal) : Use Queue to traverse
Brute Force Algorithm: Generate all possible solution candidates and check each candidate. Brute force is inefficient when a problem is big or stretched.
Greedy Algorithm: At each step its find an optimal solution and go ahead.
Divide and Conquer :Divide into sub problems , solve sub problems and deduce the large solution and conquer.
We can use following techniques to solve this algorithm.
1. Apply Recursion.
How to ...
Divide into sub problems?
Solve micro - problem?
assemble parent solution?
Dynamic Programming: We apply dynamic programming to optimize divide and conquer strategy. So, if there is any overlapping while dividing the problem use DP , instead of repeating and recalculating the same thing again.
We uses cache to store repeated data. We can manage cache in two ways:
1. Top down : Where the cache is build on flag , Call top level function , and build cache and solution along the way.
2. Bottom Up : Construct Cache First , Deduce Solution next.
Knap Sack Problem:Given a set of items, each with a weight and a value, determine which items you should pick to maximize the value while keeping the overall weight smaller than the limit of your knapsack (i.e., a backpack).
0 1 Kanpsack means either we can take complete item or zero item.
Branch and Model:
P vs NP: How propblem can be cateogrized based on complexities.
P: Solvable in polynomial time.
NP: Non Deterministics Polynomial time. Decision Problem verifiable in polynomial time. For instance: Does a route shorter than L exits ? Answer is "Yes" or "No".
NP Complete: The hardest in NP .Like Knapsack problem.
NP Hard: At least as hard as NP complete. DO not need to be decision problem and not necessary for polynomial . Knapsack problem come under this.
There are three ways to measure the performance of the algorithm:
1. Big Theta (Actual or Average case)
2. Big O (Worst Case/ Upper Bound)
3. Big Omega (best case/Lower Bound)
Organizing Data Efficiently with Common Data Structure
1. Dynamic Array: Can grow dynamically and maintain the position. In C#, it's List, In Java its Array List.
So how to create a dynamic array using a static array. First, Copy all the elements into the static array to its maximum size if need to insert more elements then create one more array of just double the size of the previous array and copy the elements from the previous array to the new one created .
2. Hash Table : Come in two flavors
1. Hash Set , which adds value directly like dynamic arrays.
2. Dictionary/Hash Map , which has key pair values.
3. Linked List : Individual elements are stored in a separate container and keep the address of previous and next element. This is called doubly linked list. Head and tail pointer contain first and last elements of the linked list.
4. Priority Queue : C# does not provide this data structure but provide some libraries (C5.IntervalHeap) to implement a priority queue.
A Priority Queue is just a queue in which element en-queued from back an de-queue from the front.
Priority Queue maintains the order of element arrived and de-queued based on weight.
Priority Queue used a heap to sort the arrays.
Overall 4 data structure Hash Set is faster than Priority Queue then linked list and in the last List.
Different type of algorithms:
Graph : Graph is a data structure which has node and edges . A graph can be directed and undirected and have cyclic .
A tree is a special type of graph which don't have any direction or cycle.
We can traverse in graph by two ways:
1. DFS (Depth First Traversal) : Use Stack to traverse
2. BFS (Breadth First Traversal) : Use Queue to traverse
Brute Force Algorithm: Generate all possible solution candidates and check each candidate. Brute force is inefficient when a problem is big or stretched.
Greedy Algorithm: At each step its find an optimal solution and go ahead.
Divide and Conquer :Divide into sub problems , solve sub problems and deduce the large solution and conquer.
We can use following techniques to solve this algorithm.
1. Apply Recursion.
How to ...
Divide into sub problems?
Solve micro - problem?
assemble parent solution?
Dynamic Programming: We apply dynamic programming to optimize divide and conquer strategy. So, if there is any overlapping while dividing the problem use DP , instead of repeating and recalculating the same thing again.
We uses cache to store repeated data. We can manage cache in two ways:
1. Top down : Where the cache is build on flag , Call top level function , and build cache and solution along the way.
2. Bottom Up : Construct Cache First , Deduce Solution next.
Knap Sack Problem:Given a set of items, each with a weight and a value, determine which items you should pick to maximize the value while keeping the overall weight smaller than the limit of your knapsack (i.e., a backpack).
0 1 Kanpsack means either we can take complete item or zero item.
Branch and Model:
P vs NP: How propblem can be cateogrized based on complexities.
P: Solvable in polynomial time.
NP: Non Deterministics Polynomial time. Decision Problem verifiable in polynomial time. For instance: Does a route shorter than L exits ? Answer is "Yes" or "No".
NP Complete: The hardest in NP .Like Knapsack problem.
NP Hard: At least as hard as NP complete. DO not need to be decision problem and not necessary for polynomial . Knapsack problem come under this.
nice post.
ReplyDelete