Assignment 2

3 Pages
Unlock Document

Computer Science
Vassos Hadzilacos

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 first 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 efficient 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 coefficients of the final 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

Log In


Don't have an account?

Join OneClass

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

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.