COSC3101, Winter 2003

COSC3101: Design and Analysis of Algorithms
Winter 2003
Sections M and P

Web page contents:

General Information
Important Dates
Course Handouts

There are separate web pages sections N and Q.

General Information

Instructor: Eric Ruppert
Office: Computer Science Building, room 3042
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Section M Lectures: Tuesdays and Thursdays, 13:00-14:30 in Curtis Lecture Hall H
Section P Lectures: Mondays, 19:00-22:00 in room 118 of Winters College
Office Hours: Mondays from 17:30 to 18:30, Thursdays from 14:30 to 15:30 or by appointment.

There is a newsgroup, york.cs.course.3101, that you can use to discuss the course.

Take a look at the departmental guidelines on academic honesty.


Old announcements

Important Dates

Section M Section P
First class Tuesday, January 7 Monday, January 6
Assignment 1 due Tuesday, January 28 Monday, January 27
Test 1 Tuesday, February 11 Monday, February 10
Reading week (no classes) February 17-21 February 17-21
Assignment 2 due Thursday, February 27 Thursday, February 27
Last date to drop course without receiving a grade Friday, March 7Friday, March 7
Test 2 Thursday, March 13 Monday, March 17
Assignment 3 due Wednesday, March 19 Wednesday March 19
Last class Thursday, April 3 Monday, March 31
Assignment 4 due Monday, April 7 Monday, April 7



Optional Supplementary Reading

Other References

Web Links


Don't fall behind with your reading. The reading in the text is required. The reading in Edmonds's notes is optional, but helpful. (Edmonds's notes are also a good source of additional examples for many topics covered in the course.)

WeekTopics Reading in CLRS Reading in Edmonds
Jan 6Introduction 1, 2.1, 2.2 1.3
Jan 6Asymptotic Notation31.4
Jan 6, Jan 13SumsAppendix A1.5
Jan 13Recurrences41.6
Jan 20Invariants, Pre- and Post-conditions none3
Jan 20Divide-and-conquer2.311.1
Jan 20Arithmetic algorithms31.2 (review 31.1) 4.3, 11.2.2
Jan 27Heapsort66.1
Jan 27, Feb 3Quicksort711.2.1
Feb 3Linear-time selection911.2.1 (page 173)
Feb 10Lower bounds for max, searching and sorting. Counting sort.8.1,, 17.3
Feb 24Radix sort, bucket sort8.3,
Feb 24, Mar 3, Mar 10Dynamic programming15 16
Mar 10, Mar 17Greedy algorithms16.1-16.3, 16.510
Mar 17, Mar 24MST algorithms2310.2.3
Mar 24 Searching algorithms228
Mar 31 Shortest Path algorithms24.3, 25.1, 25.28.2

Course Handouts

Assignments have been taken offline.

Updated April 25, 2003