COSC3101, Summer 2001

COSC3101: Design and Analysis of Algorithms
Summer 2001

Web page contents:

General Information
Announcements
Important Dates
Resources
Reading
Course Handouts

General Information

Instructor: Eric Ruppert
Office: Chemistry & Computer Science Building, room 344
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Email: [my last name] at cs.yorku.ca
Lectures: Mondays and Wednesdays, 17:30-19:00 in Stong College, room 303
Office Hours: Mondays 19:00-20:00, Wednesdays 15:00-16:00
Newsgroup: york.cs.course.3101

Take a look at the departmental guidelines on academic honesty.

Announcements

I will be out of town from August 26 to September 4. If you have questions about the course, they'll have to wait until after Labour Day. Assignment 4 has been marked. You can check your mark using courseInfo on Ariel. You can pick up the assignment after Labour Day.

IMPORTANT: There was a mistake in the solution to assignment 4, question 4. Corrected solution. There was also a mistake in the solution to question 5(c). Dijkstra's algorithm will actually work correctly for the example I gave. However, if we add a fourth vertex and an edge (3,4) with weight 1, then Dijkstra's algorithm will compute the shortest distance from 1 to 4 as 6, even though the correct distance is 4.

Hint for question 2 on assignment 4: Formalize and prove the following claim. Let Ti be the partial solution constructed after i iterations of Kruskal's algorithm. Every MST of the graph is an extension of Ti. Why does uniqueness of the MST follow from this claim?

For assignment 4, question 5, the four parts should be worth 4, 6, 4 and 6 marks, respectively (not 3,8,3,6).

For assignment 4, question 5(a), your graph should be unweighted. (BFS doesn't handle edge weights anyway.)

Old announcements about assignment 3.

This link has solutions to a couple problems discussed at the pre-midterm problem session.

Important Dates

Monday, May 28 First class
Wednesday, May 30 Assignment 1 handed out
Friday, June 8 Last date to add course without instructor's permission
Friday, June 15 Last date to add course with instructor's permission
Monday, June 18 Assignment 1 due, Assignment 2 handed out
Monday, July 2 Dominion Day holiday (no class)
Wednesday, July 4 Assignment 2 due, Assignment 3 handed out
Wednesday, July 11 Midterm Test
Friday, July 13 Last date to drop course without receiving a grade
Wednesday, July 25 Assignment 3 due, Assignment 4 handed out
Monday, August 6 Simcoe Day (no class)
Wednesday, August 15 Last class, Assignment 4 due

Resources

Textbooks

Other References

See my page of links for web pages related to theoretical computer science.

Reading

In the readings listed below, "CLR" refers to the course text, Introduction to Algorithms by Cormen, Leiserson and Rivest and "E" refers to Jeff Edmonds's notes: Pooh's Thinking About Algorithms Abstractly. Readings in brackets are suggested; others are required.

When you do the readings, you should do as many of the related exercises in the textbook as possible.

Lecture Topics Reading
May 28 introduction, asymptotic notation CLR 1, 2, E [1.2], 1.3
May 30 asymptotic notation, summations CLR 3, [E 1.4]
June 4 summations, recurrences CLR 4, [E 1.5]
June 6 recurrences none
June 11 master theorem, invariants E 4
June 13 invariants CLR 33.2
June 18 recursive algorithms E 5.2.2, 5.2.3, [rest of E 5, CLR 31.2]
June 20 recursive algorithms, priority queues CLR 7, [E 6.1]
June 25 heapsort, quicksort CLR 8, [E 5.2.1]
June 27 selection CLR 10
July 4 sorting lower bound, sorting in linear time CLR 9, [E 6.2, 7]
July 9 end of sorting, greedy algorithms (coin changing example) CLR 17.1-17.3, E 8.2, [E8.1]
July 16 greedy algorithms (scheduling, knapsack examples) none
July 18 greedy algorithms (knapsack, Kruskal's MST) CLR 24
July 23 greedy MST algorithms (finishing up Kruskal's, Prim's) CLR 22.1, 22.2
July 25 dynamic programming CLR 16, [E9]
July 30 dynamic programming E 9.3.1, 9.3.4, 9.3.7, 9.3.8
August 1 basic graph algorithms CLR 23.1-23.4, review CLR 5 if necessary
August 8 depth-first search, Dijkstra's algorithm CLR 25.0-25.2, [E8.3]
August 13 Dijkstra (continued), all-pairs shortest paths CLR 26.0-26.2
August 15 More on shortest paths, conclusions none

Course Handouts

Course handouts are no longer online.

Updated August 26, 2001