Midterm Review for CMPS 6610, Fall 2020

Relevant Material:

  1. Analyzing Algorithms (Ch. 2.2)

  2. Asymptotic Notation (Ch. 3, A)

  3. Tree Review: Heaps, Binary Search Trees, and Decision Trees (Ch. 6, 12.1, 12.2, 13.2, 8.1)
    • BST
      • Binary search tree definition; BST property
      • Rotations
      • In-order tree traversal
    • Heaps
      • Heap definition; max-heap property
      • Using array implementation, findMin takes O(1) time, and extractMin and decreaseKey take O(log n) time
      • Heapsort: Repeatedly extract min in min-heap; O(n log n) time
    • Lower bound for sorting (using decision trees)
    • Reading: LowerBoundSorting slides and heaps_BST slides
    • Relevant/related material:
    • Practice problems from the book:
      • page 153: all exercises
      • page 156: 6.2-3, 6.2-4
      • page 160: 6.4-3
      • page 167: 6-2
      • page 289: 12.1-1,2,3,4
      • page 314: 13.2-3

  4. Divide & Conquer (Ch. 2.3, 4.3-4.6)
    • You can call an algorithm divide-and-conquer only if the size of subproblems can be written as n/b where b>1
    • Mergesort, binary search, recursive squaring
    • Not: Convex hull
    • Find the runtime recurrence for a recursive algorithm given in pseudocode
    • Solving Recurrences: Solve a runtime recurrence (i.e., find an upper bound for a recursively defined T(n)):
      • Recursion Tree: Find a guess what a (runtime) recurrence could solve to using recursion trees
        • Given T(n) = aT(n/b) + f(n)
        • a = #of subproblems = #of children at each node
        • n/b = subproblem size
        • Height of the tree = log_b (n) [log of n base b]
      • Big-Oh Induction
        • Prove your guess/claim using big-Oh induction (substitution method): Find conditions on constants c and n_0 in inductive step. (No need to handle base case.)
      • Master Theorem
        • Compute n^(log_b (a)) and compare with f(n)
        • Clearly write which case of the Master theorem applies, and give the values for ε, k, and c:
          • For case 1: Give the value of ε>0
          • For case 2: Give the value of k≥0
          • For case 3: Give the value of ε>0, check the regularity condition and give the value of c<1
        • Proof of the master theorem
    • Reading: DivideAndConquer1 slides, Substitution and Master Method Notes, Master theorem proof chapter
    • Relevant/related material:
    • Practice problems from the book:
      • page 87: all exercises
      • page 92: all exercises
      • page 96: 4.5-1,2,3
      • page 107: 4-1,3

  5. Quicksort (Ch. 5.2, C.3, 7)
    • Randomized Algorithms
      • Probability and expectation
      • Expected runtime vs. average runtime, best-case runtime, and worst-case runtime
    • Quicksort
      • Deterministic quicksort:
        • Best-case runtime O(n log n) [When each pivot partitions the array into two roughly equal pieces]
        • Worst-case runtime: O(n^2) [When the array is already sorted either increasing or decreasing order]
      • Randomized quicksort: Expected runtime O(n log n)
    • Reading: Quicksort slides (pages 1-44)
    • Relevant / related material:
    • Practice problems from the book:
      • page 1200: C.3-1,2,3,4
      • page 122: 5.2-3,4,5
      • page 143: 5-2
      • page 173: all exercises
      • page 178: 7.2-1,2,3

  6. Order Statistics (Ch. 9)
    • Order Statistics
      • Select the i-th smallest element
      • Randomized selection: Worst-case runtime O(n^2), expected runtime O(n)
      • Deterministic selection: Select median of medians; worst-case runtime O(n)
      • Reading: Order statistics slides (selected pages)
      • Relevant / related material:
      • Practice problems from the book:
        • page 219: 9.2-3,4

  7. Dynamic Programming (Ch. 15.2-15.4):

  8. Greedy Algorithms
    • Greedy Strategy:
      • Repeatedly identify the decision to be made (recursion)
      • Make a locally optimal choice for each decision
    • Greedy does not always work, and requires a proof of correctness.
    • Knapsack (DP for 0/1 knapsack, greedy for fractional knapsack). Pseudopolynomial runtime.
    • Reading: Knapsack slides
    • Relevant / related material:
    • Practice problems from the book:
      • page 421: 16.1-1,2,3
      • page 427: 16.2-3,4,5,7