15-451 Algorithms 12/12/00 * Summary of course topics * Question/answer session Final is on Monday Dec 18, 8:30am-11:30am in PH100 ============================================================================= What the course has been about: 1. techniques for developing algorithms (useful tools, useful boxes) 2. techniques for analysis To organize these, it can help to draw a "running-time line" and place various topics according to where they would typically come up. sublinear --- near-linear --- low-degree poly --- general poly(n) O(1) O(log n) O(n), O(nlogn) O(n^2) sublinear up to low-degree poly: - data structures: hashing, search trees, heaps, union find. sublinear: - amortized analysis linear: - depth-first search, breadth-first search - selection/median-finding near-linear: - greedy algs with good data structures - Prim, Kruskal, Djikstra - divide-and-conquer (also for low-degree poly) - sorting - FFT low-degree & general poly(n): - dynamic programming - network flow, matching - linear programming - NP-completeness to tell when to look elsewhere general: - randomization ================================== In addition to the running time axis, we've also looked at a couple of different performance metrics. Performance metrics: - approximation ratio (e.g., find a vertex cover at most twice the size of the minimum one) - competitive ratio for online problems (e.g., for rent-or-buy, pay at most twice as much as could have paid in hindsight.) - static optimality (splay trees do nearly as well as best fixed tree in hindsight. learning algorithm for 2-player zero-sum games does nearly as well as best fixed strategy in hindsight). Different kinds of problems: - online problems - cryptographic protocols: RSA, ZK proofs. Analysis techniques: - recurrences - potential functions / piggy-banks - linearity of expectation (allows to break apart complicated RVs into simple ones). - CRT, group properties for number-theory algs. Another way to organize: some topics are useful tools that are used *inside* an algorithm. E.g., splay trees, hashing, union-find. Some are useful because you can reduce a lot of problems to them: network flow, linear programming. Notion of reduction is important in algorithms and in complexity theory: - solve a problem by reducing it to something you know how to do. - show a problem is hard by reducing a known hard problem to it. ===================================== Answer questions. Also some sample problems: Define TSP problem: Given weighted graph G, find a tour that visits all the nodes and returns home with least total cost. Factor of 2 approximation: find minimum spanning tree. Then traverse twice. Why is this within a factor of 2?