Midterm

About the midterm
19:06

  • 31 October 2023
  • Computers and calculators not allowed
  • You can bring one A4 sheet with your own notes

Contents

  1. Basics
    • Establish and prove the time complexity of an algorithm
    • Solve recursions
    • Find and prove the loop invariant of an algorithm
  2. Divide and conquer
  3. Dynamic programming
  4. Greedy

NYU Practice midterm
19:06

Textbook exercises
19:06

Exercises from (Cormen et al., 2022)

  • Solving recurrences: 4.4-1, 4.4-4
  • Dynamic programming: 14-2
  • Huffman: 15.3-3

Recurrence relations
19:06

Instead of using the Master Theorem, draw a tree and do the proof by induction

Divide and conquer
19:06

Dynamic programming
19:06