Summary of lecturesIntroductionSorting and order statisticLower boundDynamic programmingData structuresAmortized analysisNP-completenessParallel algorithmsString matchingApproximate algorithmsCross-topic reviewsQuestions types1Summary of lectures1. Introduction to Algorithm Analysis and Design (Chapter 1-3). Lecture Slides 2. Recurrence and Master Theorem (Chapter 4). Lecture Slides3. Sorting and Order Statistics (Chapter 8-9). Lecture Slides 4. Balanced Search Trees: red-back tree (chapter 13) and others Lecture Slides 5. Augmenting Data Structure (Chapter 14) Lecture Slides 6. Dynamic Programming (Chapter 15). Lecture Slides 7. Greedy Algorithms (Chapter 16). Lecture Slides8. Amortized Analysis (chapter 17) Lecture slides9. Disjoint Sets (Chapter 21). Lecture Slides 10. NP-Completeness (Chapter 34). Lecture Slides 11. Parallel Algorithms (Selected from Chapter 30, the First Edition). Lecture Slides 12. String/Pattern Matching (Chapter 32 & handout). Lecture Slides 13. Approximation Algorithms (Chapter 35). Lecture Slides 14. Divide and Conquer--closest pair (Chapter 33.4) Lecture slides 15. Lower bound: decision tree & adversary argument (handout) Lecture Slides2IntroductionAlgorithms design: data structures and algorithms (disjoint set, red-black tree, AVL, B-Tree, 2-3-4)Algorithm analysis: complexities-- space and time worst, best, average asymptotic notations: order of growth Analysis methods: loop and loop invariant recursive relation and equations Substitution, Recursion tree, Master theorem, Domain Transformation, Change of variables amortized analysis adversary argument, decision argument (worst case lower bound) Algorithms: serial vs. parallelregular vs. approximatedeterministic vs. probabilistic Design methods: divide and conquer dynamic programming, memoization greedy algorithm prune and search specific methods: 7 in closest pair, 5 in ordered statistic,3Sorting and order statistic•Sorting:–Comparison: Lower bound O(nlg n), decision tree.–Non-comparison: Bucket sort, counting sort, radix sort, (linear time).•ith smallest elements:–First (minimum), last (Maximum), both (3 n/2).–Prune-and-search•RANDOMIZED-SELECT:Expected linear time O(n) but worst-case running time O(n2). •SELECT: Linear worst-case running time O(n).Lower bound4Decision TreeAdversary Argument5Dynamic programming•Elements of DP:–Optimal substructures–Overlapping subproblems•Four steps:–Find/prove Optimal Substructure–Find recursive solution–write DP program to compute optimal value–Construct optimal solution (path).•Analysis of DP program•Relations among: recursive algorithm, divide-and-conquer, Memoization.•Auxiliary table.6Data structures•Disjoint set –Definition and implementation•Union-by-rank, path compression–Analysis•Fast increasing function and its slow reverse•Amortized analysis•Proof of the running time.•Red-black trees–Balance–Rotation–Augmenting•Other trees: –AVL, B-tree, B+-tree, 2-3-4, Treap, Splay7Amortized analysis•Find the average worse-case performance over a sequence of operations•Three methods:–Aggregate analysis:•Total cost of n operations/n,–Accounting method:•Assign each type of operation an (different) amortized cost•overcharge some operations, •store the overcharge as credit on specific objects, •then use the credit for compensation for some later operations.–Potential method:•Same as accounting method•But store the credit as “potential energy” and as a whole.8NP-completeness•P and NP•Poly reduction•Proof of NP-completeness by reduction.–Belong to NP–Is NP-hard•Reduce a (general) instance of known NPC problem to a (concrete) instance of need-to-proof problem•Prove poly reduction and their equivalence.9Parallel algorithms•PRAM models:–EREW, CREW, ERCW, CRCW•Design parallel algorithms–Analysis•Relation among models.10String matching•Naïve solution•KMP algorithm–Prefix function–Analysis: amortized method.•Appropriate string matching.11Approximate algorithms•Find near-optimal solution in poly time•Ratio•Question: given two NP-complete problems A and B, if A can be reduced to B in poly, how about their corresponding appropriate algorithms and the ratios?12Cross-topic reviews•NP-complete problem–Proof–Some (poly) algorithms such as DP algorithm (they may look like poly solution, but in fact, not).–Graph related problems, schedule problems, number and set related problems, etc. •Given a problem, –determine whether it is NP-complete, If yes,–find special cases, or find appropriate solution–Otherwise, design its data structures, its algorithms, and analyze its complexity.–DP solution for NP-complete problem, pseudo-poly.•Space and time trade-off•Pre-processing13Questions types•NP-complete proof•Parallel algorithm•Design data structures•Design algorithms (by different methods)•Given algorithm, analysis of its (different techniques) functions and complexity.•Problem-related specific questions: many!!•Recursive and recurrence.•Proof, computation, design,