CS 466/666
Advanced Algorithms

Fall 1999

 

Announcements

Assignment 4 now available.


Assignments

Assignment 1

Assignment 2

Assignment 3

Assignment 4


Lectures

Tuesdays and Thursdays, 10:00-11:20, in MC 1056.
First meeting: Tuesday, September 14; final meeting: Thursday, December 2.


Course personnel

Instructor: Jonathan Buss, DC 2113, x4428, jfbuss@trurl.math.
Office hours Tuesdays and Thursdays, 11:40-12:30. I am often in at other times; email or phone to make sure.


Teaching Assistant: Darin Ohashi, DC 2130, x3333, dmohashi@algonquin.
Office hours Monday and Wednesday 2:00-3:00.


Electronic information

This web page will have updates on readings, assignments, and other information.

Check the course newsgroup uw.cs.cs466 regularly for last-minute announcements and for answers to questions of general interest.


Pre-requisites

Undergraduate students should normally have taken CS341 prior to CS466 (although some may have taken the older CS340). You will have become familiar with many common algorithms and data structures and with techniques to design new ones. You will have had an introduction to concepts of lower bounds, including NP-completeness.

The combined 240/340 section (Spring 98) does NOT qualify as sufficent background. Please see the instructor if you took that section and have not subsequently taken 341.

Graduate students with an interest in algorithms will normally have acquired sufficient background preparation in their previous studies. See me if you wish to discuss your individual situation.


Course work

The written work for CS 466 will comprise four homework assignments, a midterm, and a final exam. Graduate students enrolled in CS 666 will also do a small project. (More information to become available.)

Homework assignments. There will be four homework assignments, due in class on the specified date. I expect the first to be due on Tuesday, October 5, and the others due on Thursdays: October 21, November 18, and December 2. One-third of the course grade will be based on these assigned problems.

You must do your own work on the assigned problems. You are permitted to discuss general aspects of the assigned problems with other students in the class, but you must create your own solution based on your own understanding of the problem. Normally, a discussion in which one of the participants writes something down for the other prevents doing one's own work. You are of course free to discuss assignments with the instructor or the TA.

Exams. A midterm exam will be held on Thursday, October 28, 4:30-6:30pm, in DWE 3518. Inform the instructor immediately if any conflicts arise.

The final exam will be held during the official exam period (December 9-22). 40% of the course mark will be based on the exam.

Due Dates

October 5: Homework 1
October 25 (Mon): Homework 2
October 28: Midterm Exam
November 18: Homework 3
December 2: Homework 4


References

One copy of each of the following references are on three-hour reserve at the Davis Centre library.

For background material, one good source is the CS 341 text,
G. Brassard and P. Bratley, Fundamentals of Algorithmics, Prentice Hall, 1996. Call number QA9.58.B73.
If you don't already have a copy, you probably have a fully adequate alternative from your previous courses. If you do want to get a general reference, I personally like
T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms, McGraw-Hill, 1990. Call number QA76.6.C662.

We will draw new material from the above texts, as well as the following.

D.S. Hochbaum, ed., Approximation Algorithms For NP-Hard Problems, PWS, 1997. Call number T57.7.A68.

R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995. Call number QA274.M68.

Note that these works are copyrighted. You have individual responsibility to respect their copyrights. If you wish to make a copy of sections or chapters, consult with a librarian to determine what restrictions and licensing agreements apply.


I may also put occasional class notes on the course web page.

Readings

Tuesday, Sep. 14:
Motwani and Raghavan, section 7.2, pp. 163-166.

Thursday, Sep. 16:
Estivill-Castro and Wood, "A Survey of Adaptive Sorting Algorithms," Computing Surveys 24 (1992) p. 441.
Introduction and section 1, through p. 456.

Sep. 21, 23:
Continue Estivil-Castro and Wood.

Sep. 28:
Amortized analysis:  either BB sections 4.6, 5.8 and 5.9, or CLR chapters 18, 20 and section 22.4. Handout: implementing a queue with two stacks.

Sep. 30, Oct. 5:
Binomial Heaps:  BB sec. 5.8 or CLR chap. 20.
Fibonacci Heaps:  CLR chap. 21.

Oct 7:
Splay trees:  any of For extra detail, see the original paper by Sleator and Tarjan, "Self-Adjusting Binary Search Trees," J. Assoc. Comput. Mach. 32 (1985) 652-686.

Oct 12:
Randomized computation:  BB section 10.6
Example - treaps:  Motwani and Raghavan, section 8.2

Oct 14:
Chernoff bounds:  MR, section 4.1 A min-cut algorithm:  MR, section 10.2

Oct 21:
Skip lists: Copies of transparencies
Estivill-Castro and Wood, pp. 465-466.

Oct 26:
Finished min-cut:  MR, section 10.2

Nov 2:
Sorting and merging networks:  CLR ch. 28, or BB 11.6.

Nov 4:
The PRAM model. Basic algorithms. CLR ch. 30 or BB 11.1,.2,.3

Nov 9,11:
PRAM algorithms: Expression evaluation (BB 11.5), connected components (BB 11.4).

Nov 16,18:
Approximation algorithms. Vertex cover and set cover (CLR 37.1, 37.3).
A sampling of techniques: Max Cut (hill climbing); TSP (problem transformation); knapsack (rounding the problem). No precise reference, but see CLR 37.2 and 37.4 for related iteas.

Nov 23,25:
Online algorithms. Hochbaum, ch. 13, esp. sections 13.1, 13.2.1, 13.2.2, 13.3.1 13.3.2, 13.4.2. 13.5.1.

Nov 30, Dec 2:
Lower bounds and techniques.
Adversary arguments. Information theory and Kolmogorov complexity.
Completeness for approximation problems (summary of Hochbaum, ch. 10.)

About this document ...

The initial form of this document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998), which is Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.