Quiz 7 will be Friday, April 20. Practice questions are available. Solutions to the practice questions are also available.
This is a course in design and analysis of algorithms. See the syllabus for details.
MWF 11:00am-12:00pm, MW 1:00pm-2:00pm or by appointment.
Due Wed. Feb. 1. From the book, with page numbers in brackets: 4.5-1(a-e)[96], 4.5-3[97], 4.5-4[97], 4-1(a-f)[107]. Also the following problem.
For simplicity in typesetting, I will use 0.59 as a stand-in for (log2(3) - 1), since that is its approximate value.
Suppose that m ≤ n. The standard (grade school) algorithm for integer multiplication multiplies an n digit number by an m digit number in time O(nm). The divide-and-conquer algorithm would take time O(n2), since it pads out the smaller number to the size of the larger number. Explain how to hybridize the grade school algorithm and the divide-and-conquer algorithm to get an algorithm that multiplies an n digit number by an m digit number in time O(n m0.59). Explain your algorithm clearly and show that it has the desired time bound. (Hint. Keep it simple.)
Due Mon. Feb. 13. From the book, with page numbers in brackets. 6.4-3[160], 6-2[167], 7.2-1[178], 7.2-2[178], 8.1-3[194].
The first two problems are from the book: 33.1-3[p. 1020], 33.1-5[p. 1021] (Hint for 33.1-5: Note that you cannot assume anything about the list of points. In particular, you cannot assume that they are the vertices of a simple polygon.)
Problem 3 is as follows. Let (a,b) and (c,d) be two points in the plane. Say that (a,b) dominates (c,d) if a > c and b > d. So a point dominates all points that are to the left and below it.
If S is a set of points, say that a point p in S is undominated if there is not any other point in S that dominates p. Give an algorithm that takes as input a set S of n points and produces a list of the undominated points in S. The algorithm must take O(n log(n)) time. Assume the set is given in an arbitrary order.
Due Mon. March 19. From the book, with page numbers in brackets. 15.4-5[397], 15-6[408]. 15-9[410].
Due Mon. April 2. From the book, exercises 16.2-1, 16.2-5 and 16-2(a).