15-451 Algorithms: Lecture 5/4/00 Announcements: - No recitation today - Final exam review Sun 5/7 1-4 pm, 1112 Doherty - Final exam Mon 5/8 8:30-11:30 am, 2315 Doherty ********** Topic: Course Summary and Overview I. Final exam and final grades II. Course overview: Big picture III. Course overview: Topic summary IV. Last 15 mins are for FCEs ********** I. Final exam and final grades Final exam: - Intended to be similar to the midterm in difficulty, only longer - 9 questions - Roughly 1/3 on material since Quiz 2 and 2/3 on the rest - Can bring one sheet of notes, both sides ********** Study aids: - All lectures are on the lectures web page. Note that after 2/24, each lecture was posted twice, so if printed before class, check again for version after class - Solutions for the quizzes and midterm - Solutions for all homework problems. Homework exercises - Past finals posted - Review session ********** Final grades: - Solutions to the Final will be posted Wed May 10 - Dorothy will get the graded HW7s and Finals late Fri May 12 - I will email students their raw scores on Sat May 13 - Contact me by email to discuss any discrepencies, grading errors by Tues May 16 - Final grades will be determined Wed May 17 - raw scores on individual assignments will be combined according to the percentages laid out on the first day of class - grades will be on a curve consistent with curves for individual assignments (although note that almost everyone does well on Oral Homeworks) - will look to bump people's grades up based on improvement or other factors ********** II. Course overview: Big picture The goal of this course was to equip you to design "provably good" algorithms and data structures for problems you encounter after you take this course. * One aspect of this is studying many widely applicable algorithms, paradigms, and analysis techniques. - e.g., dynamic programming, randomized algorithms, amortized analysis - we started with linear time algorithms and worked our way up to algorithms of increasing time complexity right up to Linear Programming * Another aspect is the experience that is gained from developing algorithms yourself, by doing the assignments. * A third aspect is to understand a process of exploring the problem's complexity: from poly-time algorithm, NP-completeness, poly-time approximation algorithm, MAX SNP-completeness. - e.g., when to give up on provable guarantees * A final aspect is exposure to algorithm design in different settings/contexts. - e.g., external memory, parallel, crytographic ********** Many topics you had already seen, but - Covered with more emphasis on algorithm design and analysis - How can algorithms be extended? - Worked out alot of proofs in detail during class. May not be the most exciting, but important exposure to the proof techniques, so that you can prove your own algorithms are correct and obtain a given time bound. - Emphasis on probability - very important - Asked you to develop your own algorithms - Algorithms are learned by doing: we have given you many challenging problems to solve on the homeworks and you have solved them (well, most of them) - Plus topics you have not seen: E.g., universal hashing This course has not previously covered approximation to this extent, tail inequalities, the wide range of context-based algorithmics, etc. ********** One of the lessons I hope you have learned is how to approach algorithmic problems. Algorithm Design Methodology: 1. Do I really understand the problem? Do I understand its context? [solve simple examples by hand, formulate as graph problem, etc external memory, synopsis data structure, online, parallel, distributed, cryptographic] 2. Can I find a simple algorithm for this problem? What can I learn from small examples and special cases? [view as problem or composition of problems or special case of problem I know how to solve] 3. Which of the standard algorithm design paradigms or data structures are most relevant? [Divide-and-conquer, Dynamic programming, Search trees, Hashing, Priority queues, Randomization, Linear programming] 4. What type of performance guarantees are desired? Are there negative results that can be shown? [Worst-case, Average-case, Worst-case expected, Worst-case w.h.p., Amortized, Competitive ratio, Approximation ratio Lower bounds, NP-completeness, Hardness of approximation] ********* III. Course overview: Topic summary Review session will have time to give a more thorough review. Here I present the topics and some highlights: 1. Fundamentals: * Asymptotic Analysis & Recurrences * Probability & Tail Inequalities, including - How to design & analyze probabilistic algorithms e.g., randomized quicksort - Common pitfalls in probabilistic analysis of algorithms: Average case vs. Worst-case expected vs. Worst-case with high probability [average case T(n) = AVG_{inputs I of size n} T(I) expected-time E[T(I)] = sum_o T(I,o) Pr{O=o} worst-case expected-time T(n) = MAX_{inputs I of size n} E[T(i)] worst-case w.h.p.: for any input I of size n, T(I) is O(f(n)) w.h.p.] - How to use Tail inequalities to get w.h.p. bounds 2. Sorting & Order Statistics: * Sorting, including - Quicksort & its analysis - Counting and bucket sort, Radix sort - Lower bounds for comparison-based sorts - E.g., any deterministic quicksort strategy that selects a pivot from among a constant number of elements is Omega(n^2) worst case - Based on decision trees * Selection, including - Quickselect [like randomized quicksort, but recurse on one half] - Deterministic selection [median of 5, median of the medians] 3. Data Structures: * Hash tables, including - Balls into buckets analysis [what is expected lookup time for hashing with chaining] - Universal hashing [Def: a set H is a "universal family of hash functions" mapping U to {0,...,M-1} if for all x != y in U, Pr_{h in H}{ h(x) = h(y) } <= 1/M i.e. the chance of collision between x and y is at most 1/M if h is chosen randomly from H] [Why important? Any fixed hash function performs very badly for some sets. Here hash functions are chosen at random, so no one set is always bad] * Search trees, including - Red-Black trees, Splay trees, Skip-Lists, Tries When would we use one versus another? [Red-Black O(1) rotations, stays balanced Splay trees repeated search on small set of keys Skip Lists: O(1) successor, predecessor, O(1) expected delete Tries: strings, prefix matches] * Union-Find 4. Fundamental Algorithm & Analysis Techniques: * Amortized analysis, including - Methodology: E.g., steps for using the accounting (money in the bank) method - When do we use amortized analysis??? [When individual operations can be expense, but can always charge expensive operations to cheap ones. - gives worst case bound on a sequence of operations - Used for splay trees - Used for FIFO queues with Find Max & Find Min [O(1) time for Find Max, O(1) amortized for Enqueue and Dequeue] * Dynamic Programming - applied when we have - Optimal substructure [The optimal solution to the problem contains optimal solutions to subproblems] - Overlapping subproblems [Polynomial number of distinct subproblems, many recurring instances] - e.g., Bellman-Ford * Linear Programming - How to formulate, Hints on how to solve 5. Graph Algorithms: * DFS, BFS, Topological sort * Single-source shortest paths - Bellman-Ford [DP: cost(v,i) = MIN_{edges x->v} ( cost(x,i-1) + weight(x->v edge) ); works for negative weight edges; detects negative-weight cycles; O(mn)] - Dijkstra [no negative-weight edges; add closest-to-start; PQueue; O(m lg n) or faster] - Scaling algorithm [consider only highest-order bit, then progressively look at additional bits] * Minimum spanning tree - Prim [add in shortest edge to non-tree node; PQueue; O(m lg n) or faster] - Kruskal [add min-weight edge unless forms a cycle, union-find, O(m lg n)] * Max Flow / Min Cut, including - residual networks, augmenting paths - bipartite matchings - min-cost max flows 6. Computational Complexity: * NP-completeness, including - class NP - reductions [make sure go in the right direction: take general instance of the known NP-hard problem and convert it to a special case instance of the unknown NP-hard problem] - problems: SAT, 3-SAT, CLIQUE, INDEPENDENT SET, 3-COLORING, VERTEX COVER * Approximation Algorithms, including - approximation ratio - Poly-time approximation schemes - MAX SNP-hard problems, L-reductions [how differ from NP-completeness reductions: must preserve approx to within a constant factor] 7. Context-based Algorithmics: * External Memory Algorithms, including - why read large blocks from disk [amortize slow seek times] - Sequential Disk Model [N = problem size, M = internal memory size, B = disk block size, N > M >> B, input starts on disk, count CPU time and I/Os] - B-trees: how their design follows naturally from sequential disk model concerns - Parallel Disk Model [adds D = number of disks, P = number of CPUs, 1 <= DB <= M/2 Get one block from each disk per I/O, Input is striped across the D disks, in units of blocks] - External sorting - mergesort on Sequential disk model - extensions for Parallel disk model [seeing into the future by tagging with smallest key in block that is D later in the same run, using randomization to balance across disks] * Synopsis Data Structures - Sufficiently small so that fit in memory - Counting distinct values, Hot list queries, Document similarity - Medians of means technique * Online Algorithms - Competitive ratio [max over possible sequences of events of (our cost)/OPT, where OPT = optimal cost in hindsight] - rent-or-buy, paging * Parallel Algorithms - parallel randomized quicksort - PRAM model: In each step, each processor can read a word from the shared memory, perform a local operation, and then write a word to the shared memory. The running time is the number of parallel steps. In the EREW PRAM, no two processors may read or write the same memory location in the same step. - (segmented) prefix computation in O(lg n) time and n/lg n processors on an EREW PRAM * Distributed Algorithms - Higher degree of uncertainity and more independence of activities than parallel context - leader election, spanning tree, consensus, resource allocation, snapshots - Coordinated attack of 2 generals: impossibiliy result from looking at *minimum* number of delivered messages that results in both attacking - Safety and Liveness properties: something bad never happens vs. something good eventually happens * Cryptographic Algorithms - RSA Cryptosystem - Number-Theoretic algorithms: GCD, Extended GCD, Inverse mod n, Exponentiation mod n ********** Picked up many useful skills. Now know how to: - Locate post-offices (using weighted medians - HW2) - Design a cross-country vacation (using DP - HW 3) - Use piggy banks to analyze algorithms (Move-to-front - HW4) - Construct the best route for pizza delivery trucks (using min-cost max flow - HW5) - Decide on which appetizers to buy for your parties (using LP - Quiz 2) - Settle accounts among roommates in a house (HW6) - Count money in a banking system (HW7) - Decide whether to rent or buy skiis (HW7) ********** IV. Course Evaluations