- The number of (primitive) operations an algorithm performs before coming to a halt. The running time is expressed as a function of the input size n.
- Three Methods (of many) of solving recurrence relations:
- Master method
- T(n) = aT(n/b) + n^d where a >= 1, b > 1
- n is the size of the problem.
- a is the number of subproblems in the recursion.
- n/b is the size of each subproblem
- n^d is the cost of the work done outside the recursive calls.
- Three possible cases:
- if d > log_b a
- T(n) = theta(n^d)
- if d = log_b a
- T(n) = theta(n^d logn)
- if d < log_b a
- T(n) = theta(n^(log_b a))
- if d > log_b a
- T(n) = aT(n/b) + n^d where a >= 1, b > 1
- Iteration
- Write out a few levels of the recurrence relation dividing the subproblem further.
- Devise a general form of the recurrence relation
- Determine complexity from the general form.
- Substitution
- Write out a few levels of the recurrence relation substituting the subproblem in
- Devise a general form of the recurrence relation
- Determine complexity from the general form
- Master method
- Behavior is partly influenced by a random-number generator. The algorithm generates its own randomness.
- No particular input can consistently elicit worst-case behavior.
- Common:
- Both divide the initial problem into sub-problems.
- Difference:
- Dynamic programming is used when sub-problems overlap, and are not independent.
##Tree/Graph Traversal:
-
Topological Sort:
-
For Directed Acyclic Graph
-
Ordering vertices so that every directed edge u,v comes before v in the ordering.
-
DFS based
- Run DFS to compute finish times for each vertex
- As each vertex gets finished, add it to the front of a linked list.
-
Kahn's algorithm
- Let L be an empty list to contain the sorted elements
- Let S be the set of all nodes with no incoming edges
- While S is non-empty
- Remove node n from S
- Add n to the tail of L
- For each node m with an edge e from n to m:
- remove edge e from the graph
- if m has no other incoming edges then insert m into S
- if the graph has edges still, then it has a cycle
- otherwise L will be a topologically sorted order
-
DFS
- Checks children first
- Properties
- Parenthesis Theorem
- One of three conditions holds for DFS:
- discovery and finish times of u and v are disjoint
- [d[u], f[u]] [d[v], f[v]]
- discovery and finish time of parent and child are well-nested
- [d[u], f[u]] is contained entirely within [d[v], f[v]], u is a descendant of v
- [d[v], f[v]] is contained entirely within [d[u], f[u]], v is a descendant of u
- discovery and finish times of u and v are disjoint
- One of three conditions holds for DFS:
- White Path Theorem
- During DFS, vertex v is a descendant of vertex u iff when u is discovered, vertex v can be reached from u along of path consisting only of white vertices
- Parenthesis Theorem
- Edge classification for Edge (u,v)
- Tree edges - If v is visited for the first time as we traverse the edge (u, v). Otherwise, v has already been visited:
- Back edges - If v is an ancestor of u. Self-Loops are also considered back edges.
- Forward Edges - If v is a descendant of u.
- Cross edges - If v is neither an ancestor or descendant of u.
-
BFS
-
Checks siblings first
'Relaxing' an edge (u,v) is testing whether the shortest path to v can be improved by going through u
(find shortest path from vertex s to each other vertex v)
-
Dijkstra's
-
Shortest path from one node to all nodes. Negative edges not allowed!.
-
One iteration through nodes.
-
Complexity: O( |E| + |V|log(|V|))
-
Bellman-Ford
-
Shortest path from one node to all nodes, negative edges allowed.
-
Multiple iterations through nodes until no shortest path updates can be made.
-
False if there are negative weight cycles.
-
Complexity: O( |E| * |V| )
(find shortest path from u to v for every pair of vertices u and v)
Matrix-Multiplication Method:
-
Siedel's Algorithm
-
Floyd-Warshall
-
Shortest path between all pairs of vertices, negative edges allowed
-
Uses V x V array of minimum distance. Keeps track of shortest path between nodes. V is number of vertices.
-
y,x = i,j = row, column
Floyd-Warshall Algorithm Example structure
for k = 0 to V
for i = 0 to V
for j = 0 to V
i,j > i,k + k,j
i,j = i,k + k,j
- Complexity: O(V^3)
-
Kruskal's Algorithm
-
Edge-Wise
-
Pick smallest edge to begin with. Can be arbitrary if there is more than one smallest edge.
-
Choose next smallest edge. It doesn't have to be connected to the first. Can be arbitrary if there is more than one next smallest edge.
-
Continue in this same manner until all nodes are in the same tree.
-
Complexity: Speed is limited by sorting edges. Merge Sort results in O(E log E) complexity.
-
Prim's Algorithm
-
Node-Wise
-
Create an empty list called 'Visited'. This will keep track of nodes we have touched.
-
Pick an arbitrary starting node. Add it to the visited list.
-
Examine all vertices reachable from starting node S. Prim's is greedy, so choose smallest edge that connects to an unvisited node. Add that node to the visited list. Can be arbitrary if there are multiple unvisited nodes with the same edge weights between them and S.
-
Continue in this same manner until all nodes are in the same tree.
-
If edges weights are distinct, this MST will be unique.
-
You can add the edge weights to get the MST's total edge weight.
-
Complexity: Depends on data structures used in algorithm.
- Adj. Matrix Searching: O(V^2)
- Binary Heap and Adjacency List: O(V log V + E log V)
-
Begin with a set of values (any kind of data) and their frequency of use.
-
Sort the list by frequency.
-
Make the two-lowest frequency elements into leaves.
-
Create a parent node for those two leaves, and it's frequency will be the sum of the two lower element's frequencies (the leaves).
-
Remove the two leaves from the frequency list. Insert the parent node into the frequency list.
-
Repeat these steps, building to the right, until there is only one element left in the list.
-
This element becomes the root of your binary huffman tree.
-
To generate a code, you traverse the tree to the value you want.
-
Taking a left-hand branch is 0.
-
Taking a right-hand branch is 1.