Problem Statement

• Purchase items for corporate expansion
• Each item costs
  • Item increases in cost by factor each week
• Only buy one item each week
• To minimize the total cost of purchases:
  • Sort items in decreasing order of
  • Purchase items in that order
• Prove this is optimal

Approach to Problem

• Identify how much buying each item costs
  • to buy item on week
• Consider what the solution is asking for
  • Order of picking elements
  • Similar to the Algorithmic Pizza problem!
• We will assume this similarity was not thought of

Approach to Problem

• Consider the Greedy solution compared to the OPT
  • Greedy always picks the item with the lowest first
  • Let Greedy have picked first and OPT have picked
• OPT picks
• Let's swap to
  • How does this change the sum?

Compare Greedy vs Optimal

• Which one is better?
• Recall that thus left-hand side is larger

Is This Proof Enough?

• Not quite enough!
• Logic only holds for swapping the first item!
  • We need to prove this holds for all swaps

Generalized Proof

• Which one is better?
• Recall that thus left-hand side is larger

• Generalizes to all swaps

Problem Statement

• We are given a complete binary tree with vertices
  • Each node has a distinct value
• Find a "local minimum," i.e. a node that is lower than all adjacent nodes
  • Use only inspections of vertex values

• Crucial Information: Not necessarily sorted

Approach to Problem

• Start very simple by isolating a part of the problem
  • Consider just the root
  • Checking if it is a local minimum takes time
• If not, we could recurse on both sides
  • Leads to
  • Note: How do we know that the subproblem is exactly half?
• What if we could recurse to just one side?

Analyze Properties

• Suppose
• Would ever be a local minimum?
  • What if we just looked into the left branch?
• But is it correct?

Correctness

• Suppose we go to a node that is less than the current
  • Are we guaranteed to find a local minimum?
• Yes
  • Either we find one along the path
  • Or we reach a leaf, which must be a local minimum!