15-451 Algorithms: Lecture 2/29/00 Announcements: - Midterm Thurs 3/2 - 6 problems, total of 15 parts - Review session 8-10 pm Wed 3/1 ********** Topics: I. Shortest-paths (Dijkstra) II. Minimum Spanning Tree (Prim) III. Designing algorithms ********** I. DIJKSTRA's ALG - single-source shortest paths in weighted, directed graphs - no negative-weight edges - faster than Bellman-Ford Pseudo-code: initialize: - empty tree T with no vertices or edges - for all x != start: x.dist = inf, x.in = null - start.dist = 0, start.in = null - use priority queue Q of triples (x,x.in,x.dist), keyed by x.dist repeat until all nodes are in T: - (u,u.in,u.dist) = extract_min(Q) - add u to T, with edge (u.in,u) - for each node x that's an out-neighbor of u if x.dist > u.dist + w(u,x) then x.dist = u.dist + w(u,x) x.in = u How might one prove this correct??? [correctness: invariants at end of each loop: - (A) x.dist for x in T is shortest-path distance from start to x. - (B) x.dist for x in Q is shortest-path distance from start to x using only edges in T plus one last edge to x (from x.in). - Claim: invariant (A) holds for u at end of loop. Why??? [By (A) and (B), shortest-path using only edges in T. Any other path: consider first node x not in T. Took shortest-path to x, so by (B), x.dist is shortest-path distance to x, but x.dist > u.dist, so longer path to u.] - Claim: invariant (B) holds at end of loop. Why??? [Obvious from (A)] ] ********** E.g., 5 10 a---->b---->c | A A 1 | 1 | | 5 start = A. V V | d<--->e---->f 2 4 T empty Q: (a,-,0),(b,-,inf),(c,-,inf),(d,-,inf),(e,-,inf),(f,-,inf) T= a Q: (d,a,1),(b,a,5),(c,-,inf),(e,-,inf),(f,-,inf) T= a->d Q: (e,d,3),(b,a,5),(c,-,inf),(f,-,inf) T= a->d->e Q: (b,e,4),(f,e,7),(c,-,inf) T= a->d->e->b Q: (f,e,7),(c,b,15) T= a->d->e->b Q: (c,f,12) \ f Final: a.dist=0, d.dist=1, e.dist=3, b.dist=4, f.dist=7, c.dist=12 a b c | A A 1 | 1 | | 5 V | | d---->e---->f 2 4 ********* Analysis: n nodes, m edges - Build initial priority queue takes time??? [O(n) time since one 0, rest inf.] - Do extract_min how many times??? [n times] - Do decrease_key how many times??? [m times: each node gets updated at most in-degree times] - Overall time depends on cost for extract_min and decrease_key: - What is total time if use binary heap??? [O(lg n) for extract_min (replace with last and heapify) and O(lg n) for decrease_key (heapify) Total time: O(m * lg(n))] - If use Fibonacci heaps (see CLR, Chap 21), extract_min is O(lg n) amortized time, but decrease-value takes only O(1) amortized time. Total time: O(m + n*lg(n)) worst case. Why worst case??? [Amortized bounds on individual operations provide guarantees on worst case of sequence of operations] ********** What if all weights equal??? [Get BFS] Consider undirected, weighted graph: - What if apply Dijkstra's algorithm??? [still works] - What if alter Dijkstra's algorithm to select node of smallest distance to tree (not to the start)??? [produces MST] ********** II. Minimum Spanning Tree A SPANNING TREE is a tree containing all the nodes in an undirected graph. A MST is the shortest spanning tree (size of tree is sum of its edge lengths) PRIM's ALG: initialize: tree = {start}. No edges. repeat: add in the shortest edge between tree node and a non-tree node. E.g., 5 10 A-----B-----C | | | 1| 1| |5 | 2 | 4 | D-----E-----F Starting at A, what is MST??? [(A,D), (D,E), (B,E), (E,F), (F,C)] How might one prove this correct??? Fact about spanning trees: ST + any edge => cycle, remove any edge in the cycle, you get a ST Proof of correctness of Prim's alg: * Inductively, assume tree built so far is consistent with an MST (there might be more than one). This is certainly true at the start. * Need to show this is maintained each time we add an edge. Say T is tree so far, and M is MST consistent with it. If new edge is in M, then fine. If new edge is not in M, then edge forms a cycle with M. This edge e goes from T to outside, so if we follow the cycle we must eventually get to an edge e' that goes back in to T. We know length(e') >= length(e) by definition of the algorithm. So, if we add e to M and remove e', we get a new tree that is no longer than M was. This maintains inductive hypothesis. Running time is like Dijkstra: - O(m * lg n) if use binary heap, or - O(m + n * lg n) if use fibonacci heap What if run Prim's alg on a directed, weighted graph??? [MST of underlying undirected graph, but not a rooted, directed-MST. E.g., 4 A--->C 3 | | 1 v v B--->D 3 ] ********** III. Designing Algorithms Course setting vs. Real world What advantages do you have in a course setting??? [ - Know to use one of the studied techniques - Often told which technique to apply: big hint - Often given the running time to aim for: big hint E.g., O(n lg n), O(lg n) - Often guided through the solution, given intermediate steps - Know it's not an open research problem to devise the algorithm ] Why algorithm design is difficult: solving a puzzle ********** [Adapted from Steven S. Skiena, "The Algorithm Design Manual", Springer-Verlag 1998] Methodology: Ask yourself a sequence of questions to guide your thought process. Can I do it this way? yes because... or no because... Clearly articulate reason(s) why something does not work: can check if really holds up or overlooked something often helpful when revisiting the idea later Start with high level strategy, not low level tactics e.g., is this problem amenable to divide and conquer vs. what's a good way to do a divide e.g., is this likely to have the subproblem optimality property vs. what would the dynamic programming recurrence be ********** Questions: 1. Do I really understand the problem? - What exactly are the inputs and outputs? - What am I trying to optimize? running time, quality of solution? - Can I solve small examples by hand? - Can I formulate the problem as a graph problem, a string problem, a search problem, a data structures problem, etc? 2. Can I find a simple algorithm for this problem? - How bad is brute force? - Does a greedy approach work? - Is there a way to formulate the problem, e.g., as a graph problem, such that the desired solution is a solution to a well-known problem, e.g., finding the minimum spanning tree? - Is there a way to view the problem such that it's similar to a problem I know how to solve? - Is the problem simply a composition of two or more problems I know how to solve? - Is the problem a special case of a problem I know how to solve? Can I simplify/improve the algorithm for the more general problem? 3. What can I learn from small examples and special cases? - Are there friendly inputs for which the problem becomes easy? - Can I learn about the structure of the problem from small examples? - What if I relax some of the solution requirements? - Once I know how to solve a certain special case, why can't this be generalized to a wider class of inputs? 4. Which of the standard algorithm design paradigms are most relevant? - Sorting: Does sorting the input help? - Divide-and-conquer: Can I zero in on the solution through a series of steps eliminating batches of non-solutions? Can I split into subproblems, recursively solve the subproblems, and then merge the results? - Dynamic programming: Do the inputs or desired solution have a natural left-to-right order? Is the problem likely to have the subproblem optimality property? Can I formulate a recurrence? - Data structures: Are there certain operations being repeatedly done on the same data, such as searching, finding min/max, etc? What is a complete list of the operations? Is the data static or dynamic? Can I use a data structure I know (hash table, priority queue, binary search tree, etc) to speed up these operations? - Randomization: Can I use random sampling to advantage? - Linear programming: Can I formulate my problem as a linear or integer program? - NP-complete: Does the problem seem like satisfiability, the traveling salesperson problem, or some other NP-complete problem? 5. If the algorithm is unsatisfactory, how can I improve the algorithm? - Repeat the previous questions - Is there additional problem structure I have overlooked? - Are there steps that can be simplified? Are certain steps overkill, e.g., I am sorting when hashing would do? - Can better data structures be used? ********** Will get into this more when discuss Context-based Algorithmics. Gets easier with practice, practice, practice.