Homework: Homework 2. Divide and Conquer

Assigned

• September 15, 2026

Due

• September 25, 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. 4.3-1ab Substitution Method.

2. 4.4-1ac Recursion Tree analysis. Just sketch the tree and give a reasonable guess on the upper bound. What is the height, what is the cost of the first, second, and last level?

3. 4.5-1abde (no c) Tight Asymptotic Bounds ($\Theta$)

4. 4.5-3 Binary Search Analysis

5. Max Give an efficient algorithm for finding the maximum value of an array of size n (assume n is a power of 2) using divide and conquer. Prove that it is correct, and argue the runtime. Is this any faster than an iterative approach using a for loop to search every element in order?

Bonus. 4-6 Chip Testing page 122 (hardcover).