CSE 3101, Fall 2008

CSE 3101: Design and Analysis of Algorithms
Fall 2008

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: Mondays, Wednesdays and Fridays, 15:30-16:30 in room 215 of Bethune College
Email: [my last name]@cse.yorku.ca (Please use a York email account when sending me email, and start your subject line with "[3101]".)
Office Hours: Tuesdays 14:00-15:00 and Fridays at various times. You can also try dropping by my office when I'm in or making an appointment by sending me email.

Academic Honesty

It is important that you 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

Quiz 5%
Test 1 20%
Test 2 20%
Exam 40%
Homework Problems 15%


Important Dates

First class Wednesday, September 3
Quiz Friday, September 12
No class (university holiday) Wednesday, October 1
Test 1 Friday, October 10
Thanksgiving (no class) Monday, October 13
Makeup test for test 1 (see announcements above)Wednesday, October 29
Assignment 7 dueWednesday, February 4
Assignment 8 dueFriday, February 6
Test 2 Monday, February 9
Last class Wednesday, February 18
Exam period February 20-March 3
Last date to drop course without receiving a gradeTuesday, March 10



Optional Supplementary Reading

Other References

Web Links


This section will be filled in as the term progresses. Don't fall behind with your reading.

WeekTopics Reading in CLRS
prereqBackground Math See handout below
Sep 3Introduction 1, 2.1, 2.2, 31.2
Sep 8Loop invariantsnone
Sep 15Proving correctness2.3
Sep 22Divide and conquer 4
Sep 29Master Theorem, Selection4 (see also Section 6 of these notes), 9.3
Oct 6More on selection (incl. Problem 9.3-3). Sorting. 8
Oct 13Sorting. Dynamic Programming.8, 15
Oct 20 Dynamic Programming.15
Oct 27More Dynamic Programming, including all-pairs shortest paths25.1, 25.2
Nov 3Greedy Algorithms16
Feb 2Greedy Algorithms for MSTs23
Feb 9Graph algorithms22.1 to 22.3
Feb 16Dijkstra's algorithm24.3

Course Handouts

Updated March 3, 2009