Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
15 Cards in this Set
- Front
- Back
|
What is Dijkstra's algorithm used for?
|
It is a method of choice for finding shortest paths in an edge and/or vertex-weighted graph. Given a particular start vertex s, it finds the shortest path from s to every other vertex in the graph, including your desired destination t.
Additionally, Dijkstra's algorithm doesn't just give the shortest path from s to t, but in general it provides the shortest path from s to all other vertices. |
|
|
Give pseudo code for Dijkstra's Algorithm.
|
Dijkstra(G,s,t)
known = {s} for i = 1 to n, dist[i] = inifinity foreach edge(s,v), dist[v] = w(s,v) last = s while(last != t) select v_next, the unknown vertex minimizing dist[v] foreach edge(v_next,x) dist[x]=min[dist[x],dist[v_next]+w(v_next,x)] last = v_next known = known union {v_next} |
|
|
What is the running time of Dijkstra's algorithm?
|
O(n^2)
|
|
|
Can Dijkstra's algorithm work on all weighted graphs?
|
No, it cannot work on graphs that contain negative-cost edges.
|
|
|
What is Kruskal's algorithm?
|
The algorithm is an approach to finding minimum spanning trees that is more efficient on sparse graphs.
This is a greedy algorithm which does not need to start with a particular vertex. |
|
|
How does Kruskal's algorithm work?
|
It builds up connected components of vertices which culminate in the minimum spanning tree.
Each vertex forms its own separate component in the tree-to-be. The algorithm repeatedly considers the lightest remaining edge and if in two different components, it inserts the edge and merge the two components into one. |
|
|
Why does Kruskal's algorithm test whether its two endpoints lie within the same connected component?
|
Because the edge needs to be discarded. Adding the edge would result in the graph containing a cycle.
|
|
|
We does Kruskal's algorithm not have to test explicitly for cycles?
|
Because each connected component is always a tree.
|
|
|
Give pseudo code for Kruskal's algorithm
|
Kruskal(g)
put edges into a priority queue ordered by weight count = 0 while(count < n-1) get next edge(v,w) if(component(v) != component(w)) add to T_kruskal merge component(v) and component(w) |
|
|
What is the time complexity of Kruskal's algorithm?
|
Sorting m edges take O(m logm), the loop makes m iterations, each testing the connectivity of two tress plus an edge. If implemented using BFS or DFS in a sparse graph we can get O(mn).
A faster implementation results if we can implement the component test in faster than O9N0 time. Using union-find, we can do such queries in O(logn) which would give our algorithm a running time of O(mlogm). |
|
|
What does the Union-Find data structure allow us to do?
|
It allows us to maintain disjoint sets in a way that give a node u, the operation Find(u) will return the name of the set containing u.
|
|
|
How can we implement Union-Find?
|
The simplest possible way is to maintain an array Component that contains the name of the set currently containing each element. Let S be a set, and assume ithas n elements denotes {1,...,n}. We will set up an array Component of size n, where Component[s] is the name of the set containing s.
We need to initialize the array by setting Component[s]=s for all s in S. |
|
|
What are the time complexities for Union-Find operations?
|
Consider the array implementation of the Union-Find data structure for some set S of size n, where unions keep the name of the larger set.
The Find operation take O(1) time. MakeUnionFins(S) takes O(n) time. Any sequence of k Union operations take at most O(k logk) time. |
|
|
What are Huffman codes?
|
They are a form of message compression
|
|
|
How do you compute a Huffman code?
|
First we record the frequency of each letter.
MISSISSIPPI M=1; I=3; S=4; P=2 Then we build a tree by adding the two lowest members recursively till we reach the root MP3 MPI6 MPIS10-Root We then label each edge as a 1 (if it's towards the right) and 0 (if it's towards the left) To find the representation of that letter we right down the path to that node. We should find that the letters with the greatest frequency have the smallest bit representation while letters with lower frequencies have higher bit representation. |
