CS341 Lecture : Assignment #2 This is the second assignment from winter 2010 term
16 Oct 2011
School
Department
Course
Professor
Document Summary
Please read http://www. student. cs. uwaterloo. ca/~cs341/policies. html rst for general in- structions: [10 marks] consider the following recurrence: T (n) = (cid:40) t (n/2) + 2 t (n/4) + n if n > 2 if n 2. Use the guess-and-check (substitution) method to prove the upper bound t (n) = o(n). Hint: use t (n) cn c(cid:48) n as the guess, where c and c(cid:48) are suitable constants. You may assume that n is a power of 2: [14 marks] given an array of n elements a[1], . , a[n] where n is even, we want to swap elements so that at the end the array becomes. A[1], a[n/2 + 1], a[2], a[n/2 + 2], . Call this the shu e problem (if we think of the array as a deck of cards, we are essentially splitting the deck evenly and performing a perfect shu e).
