COSC3101, Summer 2001

## COSC3101: Design and Analysis of Algorithms Summer 2001

### Web page contents:

General Information
Announcements
Important Dates
Resources
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.)

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

• 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.

### Other References

• 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.
See my page of links for web pages related to theoretical computer science.