COSC3101, Section A, Fall 2001

COSC3101: Design and Analysis of Algorithms
Fall 2001
Daytime Section

The main course web page contains information relevant to both sections. This page contains information for the daytime section.

Course outline

Announcements

Exam grades and *unofficial* final grades have been posted.

Assignment 4 has been marked. You can pick yours up from my office, and the marks are available from courseInfo. The average was 78%.

There is a mistake in question 3 of the solutions for test 2 that I handed out. You should replace "Since S* agrees with S_i on jobs 1...i-1, j>i. So d_j>= d_i >= t*" by "Since S* does job j at time t, d_j must be after t. Since t >= t*, d_j is also after t*"

You can check your grades using the command "courseInfo 3101 A".

Reading

The readings below refer to chapters and sections of the course text, Introduction to Algorithms, 2nd edition, by Cormen, Leiserson, Rivest and Stein. Note: The chapter and section numbers will be different if you are using the first edition of the textbook.

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

Important: I'll assume that you already know the contents of Appendix B, so you should read over any material in that appendix that you don't feel comfortable with.

Lecture Topics Reading
Sept 7 introduction, asymptotic notation 1, 2.1, 2.2, 3
Sept 10 asymptotic notation, sums Appendix A.1
Sept 12 bounding sums Appendix A.2
Sept 14 recurrences (and review of strong induction) 4
Sept 17 recurrences 2.3
Sept 21 recurrences (incl. Master Theorem) none
Sept 24 Euclid's algorithm for gcd 31.2 (review 31.1 if necessary)
Sept 26 More invariant examples (multiplication) none (but see note below)
Sept 28 Recursive algorithms (divide and conquer) 2.3 again (and see note below)
Oct 1 More on recursive algorithms none
Oct 3 Priority queues: different implementations6.1-6.3, 6.5
Oct 5 Heap sort, quick sort 6.4, 7.1, 7.2
Oct 10 Quick sort 7.3, 7.4
Oct 15 Selection 9
Oct 17 Lower bounds 8.1
Oct 19 Counting sort, radix sort 8.2-8.3
Oct 22 Radix sort, bucket sort 8.4
Oct 24 Greedy algorithms: intro, coin changing 16.1 (See note below)
Oct 26 Greedy scheduling 16.2, look at 16.5
Oct 29 Greedy scheduling none
Oct 31 Fractional knapsack, Kruskal's MST algorithm 23
Nov 2 Kruskal's MST algorithm 21.1
Nov 5 Prim's MST algorithm 21.2
Nov 7 Dynamic programming: canoes, matrix-chain multiplication 15.0-15.3
Nov 9 DP: Longest common subsequence, printing neatly15.4
Nov 12 DP: more examples 15.5
Nov 14 DP: more examples none
Nov 19 DP algorithm for parsing CFG, all-pairs shortest paths25.0, 25.1, review appendix B.4
Nov 21 Floyd-Warshall algorithm, BFS 25.2, 22.1, 22.2
Nov 23 BFS, DFS 22.3
Nov 26 Topological sort, strongly connected components22.4,22.5
Nov 28 Dijkstra's algorithm24.0, 24.3,24.5
Nov 30 Dijkstra's algorithmnone
Dec 3, 5 Review--bring questionsnone

Optional: If you still feel a little uncomfortable with invariants, you might want to read chapter 4 of Jeff Edmonds' Thinking About Algorithms Abstractly. (Available here.) If you want supplementary reading about recursive algorithm design, see Chapter 5 of those notes.

Since the text's discussion of greedy algorithms is not so great, you might want to look at Sections 8.1 and 8.2 of Jeff Edmonds' notes. You may also want to rely more heavily on the lectures than on the text for this part of the course.

Updated December 19, 2001
Send comments to ruppert@cs.yorku.ca.