CSCI 570 Homework 3: Greedy Algorithms, Divide-and-Conquer, and Dynamic Programming Guide

Introduction to Greedy Algorithms and Divide-and-Conquer

In CSCI 570, you'll encounter problems that require efficient algorithm design. This guide covers key concepts from Homework 3, including greedy algorithms for rod cutting and music festival scheduling, divide-and-conquer for skyline problems, Master Theorem analysis, and dynamic programming for ticket sales. We'll use timely examples from summer festivals and gaming to make the concepts stick.

Greedy Algorithm: Connecting Rods with Minimum Cost

The problem asks: given n rods of lengths L1, L2, ..., Ln, connect them all into one rod. The cost to connect two rods equals the sum of their lengths. A greedy algorithm that always picks the two shortest rods minimizes the total cost. This is analogous to Huffman coding, where merging smallest frequencies yields optimal prefix codes.

For example, imagine you're building a giant gaming controller prop for a festival. You have rods of lengths 2, 3, 5, and 8. The greedy approach: merge 2 and 3 (cost 5), then merge 5 and 5 (cost 10), then merge 10 and 8 (cost 18). Total cost = 5+10+18 = 33. If you merged 5 and 8 first (cost 13), then 2 and 3 (cost 5), then 13 and 5 (cost 18), total = 13+5+18 = 36, which is higher. So greedy works here.

Greedy Counterexamples for Festival Scheduling

Summer music festivals are hot right now. Imagine you're scheduling artists with deadlines and expected audience turnouts. The problem explores two greedy approaches that fail.

Scheduling by Earliest Deadline

If you schedule artists in order of increasing deadlines, you might miss high-turnout artists. Example: Artist A: deadline 1, turnout 100; Artist B: deadline 2, turnout 200; Artist C: deadline 2, turnout 300. Days available: 2. Greedy by deadline: schedule A on day 1, then B on day 2 (turnout 300). But optimal: schedule B on day 1, C on day 2 (turnout 500). So greedy fails.

Scheduling by Highest Turnout

If you schedule by decreasing turnout, you might schedule a high-turnout artist too early, blocking others. Example: Artist A: deadline 1, turnout 500; Artist B: deadline 1, turnout 400; Artist C: deadline 2, turnout 300. Days: 2. Greedy by turnout: schedule A on day 1, then B cannot be scheduled (deadline 1 already taken), then C on day 2 (total 800). Optimal: schedule B on day 1, A on day 1? No, only one per day. Actually optimal: B on day 1, C on day 2 (total 700) is worse? Wait: A on day 1, C on day 2 gives 500+300=800, same as greedy. Let's try: Artist A: deadline 1, turnout 100; B: deadline 2, turnout 90; C: deadline 2, turnout 80. Days: 2. Greedy: A on day 1, B on day 2 (190). Optimal: B on day 1, C on day 2 (170) is worse. Hmm. A better counterexample: A: deadline 1, turnout 100; B: deadline 1, turnout 99; C: deadline 2, turnout 98. Days: 2. Greedy: A on day 1, C on day 2 (198). Optimal: B on day 1, C on day 2 (197) is worse. Actually greedy by turnout can be optimal if deadlines are tight? The problem expects a counterexample. Consider: A: deadline 1, turnout 100; B: deadline 2, turnout 99; C: deadline 2, turnout 98; D: deadline 2, turnout 97. Days: 2. Greedy: A on day 1, B on day 2 (199). Optimal: B on day 1, C on day 2 (197) worse. Let's search online: classic counterexample for scheduling by profit (turnout) is when a high-profit job with early deadline blocks many medium-profit jobs. Example: Job A: deadline 1, profit 100; Job B: deadline 2, profit 90; Job C: deadline 2, profit 80; Job D: deadline 3, profit 70. Days: 3. Greedy by profit: A on day 1, B on day 2, D on day 3 (260). Optimal: B on day 1, C on day 2, D on day 3 (240) is worse? Actually optimal might be A, B, D (260) same. Need a better one: A: deadline 1, profit 100; B: deadline 2, profit 50; C: deadline 2, profit 50; D: deadline 3, profit 20. Days: 2. Greedy: A on day 1, B on day 2 (150). Optimal: B on day 1, C on day 2 (100) worse. Hmm. Actually the classic counterexample for scheduling by profit alone is when a high-profit job with a late deadline is scheduled early, pushing out a medium-profit job with an early deadline. For example: A: deadline 1, profit 100; B: deadline 2, profit 90; C: deadline 2, profit 80; days=2. Greedy: A on day 1, B on day 2 (190). Optimal: B on day 1, C on day 2 (170) worse. That doesn't show greedy failing. Actually the problem says the algorithm schedules performances without gaps, so days are filled consecutively. If we have days=2, artists: A: d=1, p=100; B: d=2, p=90; C: d=1, p=80. Greedy by profit: schedule A on day 1, then B on day 2 (190). But C cannot be scheduled because day 1 is taken. Optimal: schedule C on day 1, B on day 2 (170) worse. So greedy is better. Hmm. I recall a known counterexample: jobs: J1: deadline 1, profit 10; J2: deadline 2, profit 9; J3: deadline 2, profit 8; J4: deadline 3, profit 7; days=3. Greedy by profit: J1 day1, J2 day2, J4 day3 (26). Optimal: J2 day1, J3 day2, J4 day3 (24) worse. So greedy works? Actually the problem states that the algorithm does not consistently produce optimal solution. Let's use a classic: jobs with profits and deadlines, scheduling to maximize profit. The greedy algorithm that sorts by profit and schedules each job at the latest available slot before its deadline is optimal. But here the algorithm schedules performances consecutively without gaps, which is different. So a counterexample: days=2, artists: A: d=1, p=100; B: d=2, p=90; C: d=1, p=80. Greedy by profit: A on day1, B on day2 (190). But optimal is to schedule C on day1 and B on day2 (170)? No, 190 > 170. So greedy is better. Actually we need a case where greedy fails: suppose days=2, artists: A: d=1, p=100; B: d=2, p=99; C: d=2, p=98. Greedy: A on day1, B on day2 (199). Optimal: B on day1, C on day2 (197) worse. So greedy wins. I think the issue is that the algorithm schedules in order of profit but does not allow gaps; it fills days 1..n consecutively. If a high-profit job has a late deadline, it might be scheduled early, pushing out a medium-profit job with an early deadline. Example: days=2, artists: A: d=2, p=100; B: d=1, p=90; C: d=1, p=80. Greedy by profit: A scheduled on day1 (since available), then B on day2 (190). But B's deadline is 1, so it's scheduled after its deadline? Actually if A is scheduled on day1, B on day2, B misses its deadline (deadline 1) so it's excluded. So greedy would schedule A on day1, then B is excluded, then C? Actually algorithm: sort by profit decreasing, then for each artist, schedule at the first available day (1..m). If that day > deadline, exclude. So for A (profit 100, d=2), schedule on day1 (ok). Then B (profit 90, d=1): first available day is day2, but day2 > d=1, so exclude. Then C (profit 80, d=1): first available day is day2, exclude. So total profit = 100. Optimal: schedule B on day1, A on day2 (190). So greedy gives 100, optimal 190. That's a counterexample! So we can use that.

Efficient Greedy Algorithm for Festival Scheduling

To maximize audience turnout, use a greedy algorithm that sorts artists by profit descending, then for each artist, schedule it at the latest available day ≤ its deadline. This is the classic job scheduling algorithm and is optimal. Use a disjoint-set data structure to find the latest free day quickly.

Master Theorem Applications

The Master Theorem solves recurrences of form T(n) = aT(n/b) + f(n). For problem 3, T(n) = 7T(n/2) + n^2. Here a=7, b=2, f(n)=n^2. Compare n^(log_b a) = n^(log2 7) ≈ n^2.807. Since f(n)=n^2 = O(n^(log_b a - ε)) for ε=0.807, case 1 applies: T(n) = Θ(n^(log2 7)). For ALG' with T'(n) = a T'(n/4) + n^2 log n, we need a such that T'(n) is asymptotically faster than T(n). For ALG', n^(log_4 a) compared to f(n)=n^2 log n. We want T'(n) = o(n^(log2 7)). The critical value is when log_4 a < log2 7 ≈ 2.807, so a < 4^2.807 ≈ 4^2.807 = 2^(2*2.807)=2^5.614≈49. So largest integer a is 49. Check: if a=49, then n^(log_4 49) = n^(log2 7) = n^2.807, same as ALG. For a<49, T'(n) grows slower. So largest a such that ALG' is asymptotically faster is 48.

Divide-and-Conquer: Skyline Problem

Music festivals with multiple stages create a skyline. Given stages as (L, H, R), the skyline is a list of x-coordinates and heights. To combine two skylines, merge them like merge sort, tracking current heights. The divide-and-conquer algorithm: recursively compute skyline for left and right halves, then merge in O(n). Total O(n log n).

Dynamic Programming: Ticket Sales

For fundraising, count ways to reach n dollars with 1-dollar and 2-dollar tickets. Subproblem: ways(i) = number of ways to reach i dollars. Recurrence: ways(i) = ways(i-1) + ways(i-2), with base ways(0)=1, ways(1)=1. This is Fibonacci. Use iteration to compute.

Conclusion

These problems illustrate core algorithm design techniques. Practice with festival and gaming examples to master greedy, divide-and-conquer, and DP for your CSCI 570 homework.