Class Notes (811,690)
CSCC73H3 (10)
Lecture

# Assignment 2

3 Pages
305 Views

Department
Computer Science
Course
CSCC73H3
Professor
Semester
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
Me

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.