COSC4101, Fall 2002

COSC4101: Advanced Data Structures
Fall 2002

Web page contents:

General Information
Announcements
Important Dates
Resources
Reading
Course Handouts

General Information

Instructor: Eric Ruppert
Office: Computer Science Building, room 3042
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Mondays and Wednesdays, 14:30-16:00 in room 230 of Bethune College
Office Hours: Wednesdays 16:00-17:00, Fridays 14:00-15:00 or by appointment
There is a newsgroup, york.cs.course.4101, that you can use to discuss the course.

Take a look at the departmental guidelines on academic honesty.

Announcements

The exams have been marked. The class did very well: the average was 72%, with marks ranging from 50% to 94%. The average for term work was also 72%, so the average final mark was 72%. You can check your mark using courseInfo.

Old announcements

Important Dates

Monday, September 9	First class
Monday, September 16	Yom Kippur (no class)
Wednesday, September 18	Assignment 1 handed out
Wednesday, October 9	Assignment 1 due
Thursday, October 10	Assignment 2 posted
Monday, October 14	Thanksgiving (no class)
Wednesday, October 16	Test 1
Friday, November 8	Assignment 2 due
Friday, November 8	Last date to drop course without receiving a grade
Monday, November 18	Test 2
Tuesday, Dec 3	Assignment 3 due
Tuesday, December 3	Last class (note unusual day)

Resources

Textbook

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 2nd edition, MIT Press & McGraw-Hill, 2001. For known errata, follow this link.

Other References

Michael R. Garey, and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979.
Dorit S. Hochbaum, Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1997.
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science (2nd edition), Addison-Wesley, 1994.

Web Links

Reading

Readings below refer to sections and chapters of the course textbook. Don't fall behind with your reading.

Lecture	Topics	Reading
Sep 9	introduction	none
Sep 11	amortized analysis (counter, stack with multipop)	17.0-17.3
Sep 18	amortized analysis (dynamic arrays)	17.4
Sep 23	non-amortized dynamic arrays, B-trees	18.0-18.2
Sep 25	B-trees, Binomial heaps	18.3, 19.0, 19.1 and this link
Sep 30	Binomial heaps	19.2
Oct 2	Binomial heaps, Red-black trees	13.0-13.3 and this link
Oct 7	Red-black trees	13.4
Oct 9	Augmenting data structures	14.0-14.2
Oct 21	Interval trees	14.3
Oct 23	Static dictionaries, hashing (incl. universal classes)	11.3.3, skim rest of 11.0-11.4
Oct 28	Perfect hashing	11.5
Oct 30	Disjoint set data structures	21.1-21.3
Nov 4	Disjoint set data structures	handout 1
Nov 6	Self-organizing lists	handout 2
Nov 11	Self-organizing lists	handout 2
Nov 13	Splay trees	This link. Optional reading: these notes
Nov 20	Approximation algorithms	35.0
Nov 25	Approximation algorithms	35.1-35.2
Nov 27	Approximation algorithms, languages, the class P	35.3, 34.0, 34.1
Dec 2	Verification algorithms and reductions	34.2,34.5.1
Dec 3	NP-completeness and Conclusion	34.3

Course Handouts

Assignment solutions have been taken offline.

Updated December 17, 2002

COSC4101: Advanced Data Structures Fall 2002