Prove or disprove three greedy rules
Solve maximum interval count by earliest finish, fractional knapsack by value density, and minimum coin count by largest denomination. The point is to identify which assumptions justify each rule.
For fractional knapsack, item A has value 60 and weight 10; item B has value 100 and weight 20. With capacity 20, taking A and half of B yields 110. This relies on fractions being allowed. In 0/1 knapsack, taking A first leaves insufficient capacity for B and yields only 60, while choosing B alone yields 100.
Acceptance checks
Implement the interval scheduler and compare to exhaustive subsets on small inputs. For fractional knapsack, reject nonpositive weights and verify the returned fractions stay within [0,1]. For coins [1,3,4], show the counterexample at six.
Use exact or carefully controlled numeric arithmetic when ratios or accumulated values are important; floating-point rounding can affect comparisons and reported totals.
Deliverable: one exchange argument, one explicitly stated divisibility assumption, and one counterexample. Explain why passing random tests is insufficient to establish a greedy-choice property.