Summer 2001

Announcements

Important Dates

Resources

Reading

Course Handouts

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.

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.

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 |

- Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest, Introduction to Algorithms, MIT Press & McGraw-Hill, 1990. Follow this link for the textbook's errata.
- Jeff Edmonds, Thinking About Algorithms Abstractly, version 0.4, available from Beta Reproductions in York Lanes.

- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
- Gilles Brassard and Paul Bratley, Fundamentals of Algorithmics, Prentice Hall, 1996.
- Michael R. Garey, and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979.
- Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science (2nd edition), Addison-Wesley, 1994.
- Robert Sedgewick, Algorithms (2nd edition), Addison-Wesley, 1988.

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 |

*Updated August 26, 2001
*