Homework: Homework 0. Designing Algorithms

Assigned

• September 1, 2026

Due

• September 11, 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. Termination of Gale-Shapely Prove that the Gale-Shapely algorithm terminates in a stable perfect matching.

2. CLRS-2.1-2 Consider the procedure Sum-Array. State a loop invariant for the procedure and show it returns the sum of the numbers A[1:n]

3. CLRS-2.1-3 Rewrite the Insertion-Sort procedure to sort into monotonically decreasing order.

4. CLRS-2.2-1 Express the function $n^3/1000+100n^2-100n+3$ in $\Theta$ notation.

5. CLRS-2.3-4 Use mathematical induction to show that when $n\geq 2$ is an exact power of 2, the solution of the recurrence \(T(n)= \begin{cases} 2 & n=2, \\ 2T(n/2)+n & n>2 \end{cases}\) is $T(n)=n\log n$ (where log is $log_2$)