Main navigation | Main content
CSci 4041: Algorithms
Homework 4
Homework assignments are to be completed
alone and without assistance (except from TAs and the
Instructor). Write your discussion
section number (e.g. “discussion 3”) at the
top of your work.
Due in gradescope as a PDF.
Do the following exercises from the class textbook. Show all
your reasoning for full credit.
§15.2 2, 6 3 — do not use the substitution method: instead prove that \(P (n) \geq \frac{1}{4} 2^n\) by induction. Hint: the base cases are \(n = 1, 2, 3, 4\). [10/24 Corrected to include 4.]
§15.4 3, 5 |