Assignment #2 This is the second assignment from winter 2010 term

40 views2 pages

For unlimited access to Class Notes, a Class+ subscription is required.

CS 341, Winter 2010
Timothy Chan
Assignment 2 (due February 11 Thursday noon)
Please read http://www.student.cs.uwaterloo.ca/~cs341/policies.html first for general in-
structions.
1. [10 marks] Consider the following recurrence:
T(n) =
(
T(n/2) + 2 T(n/4) + nif n > 2
1 if n2
Use the guess-and-check (substitution) method to prove the upper bound T(n) = O(n). Hint:
use T(n)cn c0nas the guess, where cand c0are suitable constants. You may assume
that nis a power of 2.
2. [14 marks] Given an array of nelements A[1],...,A[n] where nis 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],...,A[n/2], A[n].
Call this the shuffle problem (if we think of the array as a deck of cards, we are essentially
splitting the deck evenly and performing a perfect shuffle). Example: if the array initially
contains 1,2,3,4,5,6,7,8, it will become 1,5,2,6,3,7,4,8.
Obviously, the problem can be solved in O(n) time by using a temporary array of O(n) size.
However, we are interested in algorithms that do not use much extra space besides the given
array (such algorithms are sometimes called in-place algorithms).
Give an O(nlog n)-time algorithm for the shuffle problem that requires only O(log n) extra
space. Hint: use divide-and-conquer; besides local variables, the only extra space should come
from the recursion stack, which has size proportional to the depth of the recursion. You may
assume that nis a power of 2.
3. [24 marks] Consider the decimal conversion problem: given the decimal representation
dn1dn2···d0(di∈ {0,1,...,9}) of an n-digit number N, compute the binary represen-
tation of N. Here, nis large, and we are interested in running times that are measured
in terms of the number of bit operations. We will explore two different algorithms for this
problem (in parts (b) and (d)).
(a) [2 marks] First show that the binary representation of Nhas O(n) bits.
(b) [6 marks] The following simple algorithm solves the decimal conversion problem. Show
that its running time is O(n2) (the multiplications and additions in line 3 are done in
binary):
1
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
1 Booster Class
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Class Notes
Textbook Notes
30 Verified Answers
Study Guides
1 Booster Class