University of Minnesota
CSCI4041: Algorithms

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.


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\).


3, 5