Themes from Homework 1

• Song question
  • Trade memory for runtime efficiency
  • Typically memory is abundant, but time is not
• Jar question
  • Try blunt force first
  • Room for improvement?
    • Each time throw, gives info about other rungs
    • Can narrow problem space?
• Assumed knowledge (did something in lecture, can assume)
  • Except for when explicitly asked
  • Show how specific implementation doesn’t break

Runtime

1. Plain language writeup
2. Convert into O(N)
3. Return largest magnitude

Greedy Algorithms

• Not needing to have a full view of the problem, and just start diving in
• Give a set of stuff
  • Some sort of subset or reordering for a goal
• Somewhat like a puzzle (don’t need to know all pieces, just need a few at a time)
  • However, puzzles are nonlinear, but greedy is
  • Typically O(N) since not global

How to prove greedy

• Greedy algorithms must be optimal solution at every step of the way

1. Clearly define counterfactuals
2. Show why counterfactuals never happen
3. Assume an optimal solution, adding the next step is still optimal

• Imagine some algorithm is better than ours
  • We can never fall behind some optimum

Proof of Interval Scheduling