COSC3101, Section M, Winter 2002

COSC3101: Design and Analysis of Algorithms
Winter 2002
Daytime Section

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

Course outline

Test 1

Announcements

Assignment 4 and the exam have now been marked. You can check your grades using courseInfo 3101 M. The fourth assignment can be picked up from my office. Have a good summer.

In the March 12 lecture I think I might have written a minus sign when I should have written a plus sign in the discussion of the greedy fractional knapsack algorithm. To clear up any confusion, value(s^)-value(s*) = (s^(i)-s*(i))(v_i/w_i) - SUM(s*(k)-s^(k))(v_k/w_k), where the SUM runs from k=i+1 to n. The SUM is less than or equal to (v_i/w_i)*SUM(s*(k)-s^(k)) = (v_i/w_i)*(s^(i)-s*(i)), so value(s^)-value(s*) is at least 0.

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
Jan 3 Introduction, asymptotic notation. 1, 2.1, 2.2, 3
Jan 8 Asymptotic notation, sums. Appendix A
Jan 10 Sums, recurrences. 4.1, 4.2
Jan 15 Recurrences. 2.3, 4.3, 4.4
Jan 17 Recurrences, including Master Theorem. none
Jan 22 Invariants. Euclid's algorithm, multiplication. 31.2 (review 31.1 if necessary). Also, see note (1) below.
Jan 24 Recursive programmes. Divide-and-conquer. More arithmetic examples 2.3 again. See note (2) below.
Jan 29 Divide-and-conquer, continued. Priority queues. 6.1-6.3, 6.5
Jan 31 Heapsort, quicksort. 6.4, 7.1
Feb 5 Analysis of quicksort. 7.2-7.4. See note (3) below.
Feb 19 Linear-time selection. Selection lower bound.9
Feb 21 Sorting lower bound. Counting sort, radix sort.8.1-8.3
Feb 26 Bucket Sort. Introduction to Greedy Algorithms. 8.4, 16.0-16.2. See note (4) below.
Feb 28 Greedy Algorithms: Coin-changing, Prim. 23
Mar 5 Greedy Algorithms: Prim (cont'd, including the generic tree-building alg), Kruskal. 21.1, 21.2
Mar 7 Greedy Algorithms: Analysis of Kruskal; scheduling problems. 16.1, first 6 paragraphs of 16.5, Optional: 16.3
Mar 12 Greedy scheduling, Greedy Fractional Knapsack. pages 382, 383.
Mar 14 Dynamic Programming (canoe rental, optimal matrix muln, longest common subsequence). Chapter 15
Mar 21 Dynamic Programming (printing neatly, another scheduling problem, 0-1 knapsack). none
Mar 26 Dynamic Programming (parsing, all-pairs shortest paths) 25.0-25.2, review B.4 if necessary
Mar 28 transitive closure, BFS, DFS 22.1-22.4
Apr 2DFS, topological sort, Dijkstra's algorithm 22.5, 24.0, 24.3, 24.5
Apr 4Dijkstra (cont'd)none

Optional:
(1) If you still feel a little uncomfortable with invariants, you might want to read chapter 4 of Jeff Edmonds's Thinking About Algorithms Abstractly. (Available here.)
(2) If you want supplementary reading about recursive algorithm design, see Chapter 5 of those notes.
(3) We won't be doing much with randomized algorithms in this course, except for the randomized version of quicksort on Feb 5 and bucket sort on Feb 26. If you want some background on analyzing randomized algorithms, see Chapter 5 of the text.
(4) Jeff Edmonds's notes are also very useful for supplementary reading on Greedy algorithms (see Chapter 8).

Updated April 5, 2002