Homework: Homework 3. Greedy Algorithms

Assigned

• September 22, 2026

Due

• October 2, 2026 10:00pm

Collaboration

Make sure you review and understand the policies on the syllabus before you discuss your work on this assignment with anyone.

Submitting

You will submit your compiled pdf on Gradescope. Everything must be typed in \(\Latex\) If you are asked to design an algorithm, please provide: (a) the pseudocode or precise description in words of the algorithm, (b) an explanation of the intuition for the algorithm, (c) a proof of correctness, (d) the running time of your algorithm and (e) justification for your running time analysis.

1. 15.1-2 Select Last activity to start instead of first to finish

2. 15.1-3 Give counter examples that fail for always selecting: Least duration, overlaps the fewest, earliest start time.

3. 15.2-3 0-1 Knapsack that sorted by increasing weight is the same as sorted by decreasing value.

4. 15-1abc Coin Changing

5. 15-2a Average Completion Time

Bonus. 15.2-7 Optimal Payoff