Proving a Blackbox Algorithm

• Assumed degree of knowledge
  • How algorithm works
  • Runtime for algorithm
  • Proof of correctness
    • Okay to say BFS runs in $O(N+M)$ and for proof BFS finds shortest path
• Greedy works only if there is some prioritizing criteria or heuristic (what about ties in homework 1.6?)
• Gale-Shapley is balancing competing organizing principles

Greedy Algorithms

• Conduct limited analysis
• Final decision/assignment
• Only needs to cycle through data once
• Works in an underlying rule or pattern that forces broader solution into alignment
• Not a sort of search

When do you use Greedy?

• Selecting subset of elements based on optimization
• Ordering elements based on optimization
• Independent calculation based on data
• Doesn’t work when:
  • Looking for target in data
  • Sorting data
  • Non trivial optimization
• Work backwards from proof, avoiding failure

Example: Minimum # of Train Platforms

• Train arrivals and departures
• Least amount of platforms