CSE4101/5101, Winter 2009
CSE4101/5101: Advanced Data Structures
Web page contents:
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 "".)
It is important that you take a look at the departmental
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.
|Project (CSE5101 only)|| 0% ||20%|
- (Jun 5) Exam grades and UNOFFICIAL final grades have been posted online. You can access your info by logging into a CS machine and typing `courseInfo 4101 2008-09 W'.
- (May 20) The review session I mentioned in class will be held on May 26 starting at 3pm in room 105 of Vanier College. I won't be teaching, but just answering any questions you may have. Of course, attendance is optional but it will give you a chance to ask questions and hear other students' questions. (My regular office hours also continue until the exam.)
- (May 19) There are lots of textbooks in the library on algorithms and data structures that you can use as a source for additional practice problem. Some other, online sources include Professor Mirzaian's site and this site and this one for a similar course at UC Irvine. (Of course, they cover different sets of topics, but some parts will be relevant.)
- (May 6) The last two classes (May 14 and May 19) will be held in CSEB 3033.
- (Apr 22) Marks for Test 1 are now posted. To view your marks, login to a cs machine running Unix and type "courseInfo 4101" (even if you are in 5101).
- (Apr 21) In the solutions for Test 1 that I handed out, I forgot to mark node 16 in the answer to question 2.
- (Apr 21) The exam schedule has now been posted on the Registrar's web site.
- (Apr 16) York's engineering society and ITEC club have organized an IBM Student Conference with demos and a speaker, Raul Chong from IBM. It will be on Wed Apr 22 from 5:00 p.m. to 6:30 p.m. in ACW 106. RSVP (name and student #) to firstname.lastname@example.org .
- (Mar 31) The first test will be on April 9, during regular class time. You may bring into the test one 8.5x11 inch sheet with handwritten notes on both sides.
- (Mar 30) On assignment 2, question 2, you can assume for simplicity that elements in the set are distinct. (The user never tries to insert a duplicate element.)
- (Mar 26) On assignment #2, "17.4-7" should read "17.3-7".
- (Mar 19) There will be no class on Mar 24. The guest lecturer I had hoped would teach the class cannot make it.
- (Mar 17) Check out the York programming contests. The first contest of the Winter term will take place on Friday March 20, 15:00-17:00 in CSEB 1006. Check out also this facebook group.
- (Mar 14) For assignment 1, you can assume that creating an array (containing 0's) can be done in constant time (although there are ways to avoid this assumption).
- (Mar 12) I will be out of town March 20 to 25. The office hours while I'm away will be cancelled, but I will try to check email.
|March 5 ||First class|
|April 9||Test 1|
|April 22 ||Last date to drop course without receiving a grade|
|May 7||Test 2|
|May 19 ||Last class |
|May 22-June 2 ||Exam period|
- 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
- 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.
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 analysis||17.1 |
|Mar 9 ||amortized analysis||17.2-17.4|
|Mar 16 ||eager doubling and halving (not in text) and Binomial heaps||19 (and this link)|
|Mar 23 ||Fibonacci heaps||20 (and this link)|
|Mar 30 and Apr 6 ||Disjoint sets||21|
|Apr 13||Dictionaries (and BSTs)||12|
|Apr 21||B-trees and RBTs||18, 13, RBT insert slide, RBT delete slides |
|Apr 28||Augmenting RBTs, hashing||14|
|May 11||Hashing, student presentation on Suffix Trees||
|May 18||Student presentations Randomized Search Trees, T Trees and Skip Lists|
Updated June 5, 2009