Due: Friday, March 20th in class Late assignments will be penalized 20% per day.

Book Questions from Introduction to Algorithms - 3rd ed.

5.2-4, 5.4-2

11.2-2, 11.3-4

15.1-3

Hints:

5.2-4 - Define an indicator random variable

Then E[X] will represent the number of people that receive their own hat back.

5.4-2 - Assume that you have a bucket that you will place all the balls into before tossing all of them at the same time. Then consider the Birthday Paradox.

15.1-3 - Read section 15.1 regarding the Rod Cutting problem. Then consider how to modify the routine BOTTOM-UP-CUT-ROD() on pg. 366 to solve the problem when there is an associated per cut cost.