Class Notes
(811,690)

Canada
(494,876)

University of Toronto Scarborough
(30,852)

Computer Science
(300)

CSCC73H3
(10)

Vassos Hadzilacos
(10)

Lecture

# Assignment 2

by
OneClass4706

Unlock Document

Computer Science

CSCC73H3

Vassos Hadzilacos

Fall

Description

Computer Science C73 September 28, 2010
Scarborough Campus University of Toronto
Homework Assignment #2
Due: October 19, 2010, by 10:30 am
(in the drop box for your CSCC73 tutorial section, near room SW-626A)
Appended to this document is a cover page for your assignment. Fill it out, staple your answers to it,
and deposit the resulting document into the course drop box (without putting it in an envelope).
Question 1. (10 marks) Solve Exercise 1 on page 246 of the textbook by Kleinberg and Tardo ¨s. You
should not only describe your algorithm, but also explain why it works and why it achieves the required
bound of O(logn) queries.
Question 2. (10 marks) The standard algorithm for merging two sorted lists requires time proportional
to the size of the resulting list. Suppose we are given k sorted lists, each containing n elements. We want
to merge these into a single sorted list.
a. (5 marks) Here is one algorithm to solve our problem: We merge the ﬁrst two lists; then we merge
the resulting list with the third list; then we merge the resulting list with the fourth list, etc. What is the
time complexity of this algorithm in terms of k and n?
b. (5 marks) Give a more eﬃcient divide-and-conquer algorithm to solve this problem. What is the time
complexity of your algorithm?
Question 3. (10 marks) If G = (V,E) is a graph and V ⊆ V , the subgraph of G induced by V is ′
′ ′ ′ ′ ′
the graph G = (V ,E ), where E = {(u,v) ∈ E : u,v ∈ V }. Intuitively, this is the graph we obtain from
G if we delete all nodes except those in V and all edges that have (at least) one endpoint outside of V . ′
Professor N. O’Bright suggests the following divide-and-conquer algorithm to compute the MST of a
connected, undirected graph G = (V,E) with edge costs c(e) for each e ∈ E. If G consists of a single node,
the MST trivially has no edges. Otherwise, we partition the set of nodes of G arbitrarily into two sets V 1
and V of about the same size; we recursively compute the MSTs of the subgraphs of G induced by V and
2 1
V2; and we join these two MSTs by a minimum cost edge that crosses the V /V cut. More 1rec2sely, the
algorithm that N. O’Bright proposes is this:
d&c-mst(G)
if |V | = 1 then return ∅
else
let V ⊆ V be such that |V | = ⌈|V |/2⌉, and V := V − V
1 1 2 1
let G1and G b2 the subgraphs of G induced by V and V1, respe2tively
let e be a minimum cost edge connecting a node in V to1a node in V 2
return d&c-mst(G ) ∪ 1&c-mst(G ) ∪ {e}2
Is this algorithm correct? If so, prove it; otherwise, provide a counterexample.
Question 4. (5 marks) Demonstrate the polynomial multiplication algorithm that uses the FFT by using
2
it to multiply the polynomials 1 + x + 2x and 2 + 3x: Use the FFT to evaluate each polynomial at an
appropriate set of points, and show the resulting vectors; multiply the vectors component-wise; and use
the inverse FFT to obtain the coeﬃcients of the ﬁnal result. Show your work.
(continued)
1 Question 5. (15 marks) In class we discussed Karatsuba’s divide-and-conquer algorithm for integer
multiplication, which multiplies n-bit numbers by recursively multiplying n/2 bit numbers (see Section 5.5
of the textbook). In this problem we show that it is possible to get an asymptotically faster algorithm by
recursively multiplying n/3-bit numbers. To do this, we use ideas about fast multiplication of polynomials
given

More
Less
Related notes for CSCC73H3