CSE4101/5101, Winter 2009

CSE4101/5101: Advanced Data Structures
Winter 2009

Web page contents:

General Information
Important Dates
Course Handouts

General Information

Instructor: Eric Ruppert
Office: Computer Science Building, room 3042
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Tuesdays and Thursdays, 16:00-17:30 in the Health, Nursing and Environmental Studies Building (Room 034 on Tuesdays and Room 035 on Thursdays).
Office Hours: Tuesdays and Fridays 13:00-14:00. If you cannot make it at those times, feel free to contact me to make an appointment at a different time. You can also try dropping by my office.
Email: [my last name]@cse.yorku.ca (Please use your cse account when sending me email, and start your subject line with "[4101]".)

Academic Honesty

It is important that you take a look at the departmental guidelines on academic honesty.

Although you may discuss the general approach to solving a problem with other people, you should not discuss the solution in detail. You must not take any written notes away from such a discussion. Also, you must list on the cover page of your solutions any people with whom you have discussed the problems. The solutions you hand in should be your own work. While writing them, you may look at the course textbook and your own lecture notes but no other outside sources.

Marking Scheme

Homework assignments15%15%
Test 122.5%15%
Test 222.5%15%
Project (CSE5101 only) 0% 20%


Important Dates

March 5 First class
April 9Test 1
April 22 Last date to drop course without receiving a grade
May 7Test 2
May 19 Last class
May 22-June 2 Exam period



Other References

Web Links


Readings below refer to sections and chapters of the course textbook. This table will be filled in as the term proceeds. Do not fall behind with your reading.

Week Topics Reading
Mar 2 introduction, amortized analysis17.1
Mar 9 amortized analysis17.2-17.4
Mar 16 eager doubling and halving (not in text) and Binomial heaps19 (and this link)
Mar 23 Fibonacci heaps20 (and this link)
Mar 30 and Apr 6 Disjoint sets21
Apr 13Dictionaries (and BSTs)12
Apr 21B-trees and RBTs18, 13, RBT insert slide, RBT delete slides
Apr 28Augmenting RBTs, hashing14
May 4Hashing11
May 11Hashing, student presentation on Suffix Trees
May 18Student presentations Randomized Search Trees, T Trees and Skip Lists

Course Handouts

Updated June 5, 2009