Mastering Greedy Algorithms and Divide-and-Conquer for CSCI 570 Homework 3

Introduction to CSCI 570 Homework 3

Welcome to this detailed tutorial designed to help you tackle the key concepts in CSCI 570 Homework 3. This assignment covers greedy algorithms, divide-and-conquer, master theorem, and dynamic programming. We'll use timely examples from 2026, such as the summer music festival season and the latest AI-driven event planning tools, to illustrate these algorithms. By the end, you'll have a solid understanding of how to approach each problem without directly copying solutions.

Greedy Algorithms: Connecting Rods and Scheduling Performances

Connecting Rods with Minimum Cost

The first problem asks: given n rods of lengths L1, L2, ..., Ln, connect them into one rod. The cost of connecting two rods equals the sum of their lengths. The goal is to minimize total cost. This is a classic greedy problem: always connect the two shortest rods first. Why? Because connecting shorter rods early reduces the number of times longer rods are added to the sum. Think of it like merging files in data compression or combining small tasks in project management. In 2026, with the rise of AI-powered logistics, similar greedy strategies optimize supply chain costs.

For example, if rods are lengths 4, 3, 2, and 6, the greedy algorithm picks 2 and 3 (cost 5), then 4 and 5 (cost 9), then 6 and 9 (cost 15), total 29. Any other order yields higher cost. To implement, use a min-heap (priority queue) to repeatedly extract two smallest rods and insert their sum.

Music Festival Scheduling with Deadlines and Turnouts

Problem 2 involves scheduling n performances over m days, each with deadline D_i and audience turnout A_i. We need to maximize total turnout. Two naive greedy approaches fail: (a) sorting by increasing deadline and scheduling consecutively, and (b) sorting by decreasing turnout. Both can miss optimal solutions. For example, consider artists: Artist 1: D=1, A=100; Artist 2: D=2, A=90; Artist 3: D=2, A=80. Greedy by deadline schedules 1 (day1), then 2 (day2), missing 3. But optimal is schedule 2 and 3 (days 1 and 2) for total 170. Similarly, greedy by turnout picks 1 (day1), then 2 (day2), missing 3. The correct greedy uses a max-heap: sort by deadline, then for each day, add all artists with that deadline to a heap keyed by turnout, and schedule the highest turnout artist. This yields optimal solution, similar to scheduling tasks with profits in job sequencing.

Master Theorem: Analyzing Recurrences

Comparing Running Times

Problem 3: T(n) = 7T(n/2) + n^2. Using Master Theorem, a=7, b=2, f(n)=n^2. Compare n^(log_b a) = n^(log_2 7) ≈ n^2.807. Since f(n) = n^2 = O(n^(2.807 - ε)), case 1: T(n) = Θ(n^(log_2 7)). For ALG' with T'(n) = a T'(n/4) + n^2 log n, we need T' asymptotically faster than T. Compute n^(log_4 a) = n^(log_4 a). For T' to be faster, we need n^(log_4 a) < n^(log_2 7). Taking logs: (log_4 a) < (log_2 7). Since log_4 a = (log_2 a)/2, we get (log_2 a)/2 < log_2 7 => log_2 a < 2 log_2 7 => a < 7^2 = 49. Also, we need f(n) = n^2 log n to satisfy case 2 or 3? Actually, we want T' = Θ(n^(log_4 a)) if f(n) is polynomially smaller. For a just below 49, n^(log_4 a) is just below n^(log_4 49) = n^(log_2 7). So the largest integer a is 48. But careful: if a=48, then n^(log_4 48) ≈ n^2.792, still less than n^2.807. So a=48 works.

StrangeSort Recurrence

Problem 4: StrangeSort. For n items, it splits into two lists: B contains items with count < n/2, C with count ≥ n/2. The counts are computed in O(n^2) time (for each x, scan all others). Then recursively sort B and C. The recurrence: T(n) = 2T(n/2) + O(n^2). Using Master Theorem, a=2, b=2, f(n)=n^2. n^(log_b a)=n^1. f(n)=n^2 is asymptotically larger, so case 3: T(n) = Θ(n^2). But wait, the split is not exactly half? Since each item's count is compared to n/2, the sizes of B and C are each at most n/2? Actually, because counts are integers, the split could be uneven. But worst-case, one side could have n-1 items? Let's analyze: For distinct items, the median will have count exactly (n-1)/2, so B and C each have about n/2. However, if all items are equal? They are distinct, so median splits evenly. So recurrence holds. Thus T(n) = Θ(n^2).

Master Method Applications

Problem 5: (a) T(n)=T(n/2)+2^n. f(n)=2^n, which is not polynomial, so Master Theorem does not apply. (b) T(n)=5T(n/5)+n log n - 1000n. Here a=5, b=5, f(n)=n log n. n^(log_5 5)=n^1. f(n)=Θ(n log n) = Θ(n^1 log^k n) with k=1, so case 2: T(n)=Θ(n log^2 n). (c) T(n)=2T(n/2)+log^2 n. a=2, b=2, f(n)=log^2 n. n^(log_2 2)=n^1. f(n)=o(n), so case 1: T(n)=Θ(n). (d) T(n)=49T(n/7)-n^2 log n. The minus sign is unusual; Master Theorem assumes positive f(n). So does not apply. (e) T(n)=3T(n/4)+n log n. a=3, b=4, f(n)=n log n. n^(log_4 3)≈n^0.792. f(n)=Ω(n^(0.792+ε)), check regularity: 3f(n/4)=3*(n/4)log(n/4)= (3/4)n log(n/4) ≤ c n log n for c=0.75<1, so case 3: T(n)=Θ(n log n).

Divide-and-Conquer: Linked Lists and Skyline

Searching in a Sorted Singly Linked List

Problem 6: Binary search on a sorted array takes O(log n) but on a singly linked list, we cannot access middle in O(1). A divide-and-conquer approach: find the middle element by traversing half the list (O(n)), compare, then recurse on left or right half. Recurrence: T(n)=T(n/2)+O(n) => T(n)=O(n) by Master Theorem (a=1, b=2, f(n)=n, case 3). So worst-case O(n), which is linear search. No improvement over linear search.

Mergesort for Singly Linked List

Problem 7: Mergesort on linked list works by splitting into two halves (using slow/fast pointer), recursively sorting, and merging. Splitting takes O(n), merging takes O(n), recurrence T(n)=2T(n/2)+O(n) => O(n log n). This is optimal for comparison-based sorting.

Skyline Problem

Problem 8: Given buildings (L, H, R), compute skyline. Part (a): Combine two skylines in O(m+n) by merging like merge sort, tracking current heights. Part (b): Use divide-and-conquer: recursively compute skyline for left and right halves, then merge in O(n). Recurrence T(n)=2T(n/2)+O(n) => O(n log n). This is a classic problem, often asked in tech interviews.

Dynamic Programming: Fundraising Ticket Combinations

Problem 9: Count distinct ways to reach $n using 1-dollar and 2-dollar tickets. This is like Fibonacci: dp[0]=1 (empty), dp[1]=1, dp[2]=2, dp[n]=dp[n-1]+dp[n-2]. Subproblem: number of ways to reach amount i. Recurrence: dp[i] = dp[i-1] + dp[i-2]. Pseudocode: initialize dp[0]=1, dp[1]=1; for i=2 to n: dp[i]=dp[i-1]+dp[i-2]; return dp[n]. Time O(n), space O(1) if optimized.

Conclusion

This tutorial covered key algorithms from CSCI 570 Homework 3, using current trends like music festivals and AI logistics. Practice these problems to deepen your understanding. Good luck!