CSCC73H3 Lecture Notes - Multiplication Algorithm, Row And Column Vectors, Polynomial Interpolation
19 Oct 2011
School
Department
Course
Professor
Document Summary
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 tard os. You should not only describe your algorithm, but also explain why it works and why it achieves the required bound of o(log n) 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. What is the time complexity of this algorithm in terms of k and n: (5 marks) give a more e cient divide-and-conquer algorithm to solve this problem.
