Algorithms

General Course Information

Coursework. Coursework will consist of weekly homeworks, two midterms, and a comprehensive final exam. The overall grade will be determined 20% from homework, 25% from each midterm, and 30% from the final. Group work on homeworks is permitted; each student should turn in his or her own copy of the homeworks, clearly marked with a list of the other students in the group. Homeworks will usually be assigned in lecture on Thursdays and due at the ICS distribution center on the following Thursday (by whenever the distribution center closes that day). Late assignments will not be accepted.

Text. The course text will be "Introduction to Algorithms", by T. H. Corman, C. E. Leiserson, and R. L. Rivest (MIT Press and McGraw-Hill 1994). You are expected to be familiar with the material in sections I-III of CLR; the course will review some material in section II but will primarily cover selected topics from sections IV, VI, and VII.

Course times. The course meets Tuesdays and Thursdays, 11:00 - 12:20 in CS 174. There are two discussion sections, one Wednesday 10:00 - 10:50 in ET 204 and another Wednesday 2:00 - 2:50 in SH 128. (Two more discussion sections were cancelled, and the capacities of these two sections enlarged, due to insufficient availability of teaching assistants.) All students should be enrolled both in the lecture and in one of the two discussion sections.

Instructors and office hours. The course will be taught by David Eppstein (eppstein@ics.uci.edu, office CS 358D, phone 824-6384, office hours Wednesdays 3:00-4:00). The discussion sections will be led by teaching assistants Brad Hutchings (rhutchin@ics.uci.edu, office CS 360C, phone 824-8191, office hours Tuesdays 2:00-3:00) and Mac Casale (mcasale@ics.uci.edu, office CS 360C, phone 824-8191, office hours Fridays 12:00-1:00).

Add/drop policy. All drop requests should be given to Prof. Eppstein at office hours or by appointment. Drops will be accepted only up to the second week of classes. Once your drop card has been signed, further coursework from you will not be graded. After the seventh week of classes, withdrawals will be allowed only by petition and under documented extenuating circumstances, in accordance with ICS departmental policy.

Students wishing to add should submit an enrollment agreement form to the ICS undergraduate student affairs office (forms are available from the USAO); there will be announcements in the discussion sections listing students whose forms have been processed and for whom add cards will be signed. Adds will only be accepted for students meeting the course prerequisites, and prioritized according to expected date of graduation (as verified by the USAO). If you intend to add, you should turn in all homework assignments as they are due; these will be graded once your add card has been signed.

Tentative Schedule

Week 1:

Jan 6:

Introduction. Growth of functions. Fibonacci numbers. Dynamic programming. [CLR 1 & 2]

Jan 8:

Sorting, comparison trees, and lower bounds. Mergesort. Divide and conquer. Solution of recurrences. [CLR 1, 4, & 9.1]

Homework due Jan 15 (note change of date):

(a)	Write a recursive algorithm that computes f(n), where f(n) satisfies the following recurrence: f(1) = 1 f(n) = f(n-1) + f(n/2) + 1
(b)	Write down a recurrence describing the running time of your algorithm. You do not need to solve this recurrence.

CLR problem 2-2.
CLR problem 2-3.
CLR problem 4-1.

Week 2:

Jan 13:

Divide and conquer. Merge sort. Heap sort. [CLR 1 & 7]

Jan 15:

Quicksort. Average case analysis. [CLR 8]

Homework due Jan 22: CLR exercises 1.3-7*, 7.1-4, 7.1-5, 8.3-1, 8.3-2

Week 3:

Jan 20:

Integer sorting. [CLR 9]

Jan 22:

Medians and order statistics. Heapselect. Quickselect. [CLR 10]

Homework due Jan 29: CLR exercises 9.3-1, 10.2-3, 10.3-9

Week 4:

Jan 27:

Deterministic selection. [CLR 10.3]

Jan 29:

Midterm I

Week 5:

Feb 3:

Dynamic programming. Matrix chain multiplication. [CLR 16.1 & 16.2]

Feb 5:

Common subsequences. [CLR 16.3 & 16.4]

Homework due Feb 12:

CLR exercise 16.1-1
CLR exercise 16.2-3
CLR exercise 16.3-5 (or, for extra credit, exercise 16.3-6*)
Suppose we have a lecture with n students, partitioned into k groups of friends. Is there a way of forming two discussion sections of n/2 students each, so that students in the same group of friends all go to the same discussion?
Formally, let F[i] denote the number of friends in group i, where 0 < i < k, and where the sum of the F[i]'s is n. We'd like to find a subset of the F[i]'s summing to n/2. Find a dynamic programming algorithm that does this in time O(n²). Your algorithm should output which groups to include in each discussion section, not just true or false.

Hint: you should start with a recursive algorithm taking two arguments and returning a boolean: partition(x,y) returns true when there exists a subset of the first x groups that sums to y.

Week 6:

Feb 10:

Graphs algorithms. Depth first search. Topological ordering. [CLR 23]

Feb 12:

Shortest paths. [CLR 25]

Homework due Feb 19: CLR exercises 23.3-4, 23.3-6, 25.1-1, 25.2-2, 25.2-4

Week 7:

Feb 17:

Strongly connected components. Minimum spanning trees. [CLR 23.5,24]

Feb 19:

String matching. [CLR 34]

Homework due Feb 26: CLR exercises 23.5-3, 24.1-3, 24.2-2, 34.1-4.
(Note: in ex. 23.5-3, either prove the statement or give a counterexample, don't just answer yes or no.)

Week 8:

Feb 24:

Knuth-Morris-Pratt algorithm. [CLR 34.4]

Feb 26:

Midterm II

Week 9:

Mar 3:

Computational geometry. Plane sweep. Line segment intersection. Convex hulls. [CLR 35.1,35.2]

Mar 5:

Convex hulls. Closest and farthest pairs. Nearest neighbors. [CLR 35.3]

Homework due Mar 12: CLR exercises 35.2-1, 35.2-3, 35.3-3; CLR problem 35.1a

Week 10:

Mar 10:

NP-Completeness and undecidability. [CLR 36]

Mar 12:

Approximation and greedy algorithms. [CLR 37]

ICS 161, Winter 1998:
Design and Analysis of Algorithms

General Course Information

Tentative Schedule

Other Course-Related Information

ICS 161, Winter 1998: Design and Analysis of Algorithms

General Course Information

Tentative Schedule

Other Course-Related Information

ICS 161, Winter 1998:
Design and Analysis of Algorithms