Unformatted text preview:

Summary of lecturesIntroductionSorting and order statisticLower boundDynamic programmingData structuresAmortized analysisCross-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. Divide and Conquer--closest pair (Chapter 33.4) Lecture slides 10. 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•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.8Cross-topic reviews•Given a problem, –design its data structures, its algorithms, and analyze its complexity.•Space and time trade-off•Pre-processing9Questions types•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,


View Full Document

IUPUI CS 580 - SUMMARY OF LECTURES

Download SUMMARY OF LECTURES
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view SUMMARY OF LECTURES and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view SUMMARY OF LECTURES 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?