Schedule, CS320, Spring 2020, McConnell   

Policies  ·  Schedule  ·  Syllabus

Schedule: look here to see what readings to study before class


Week Dates Topics Material Comments
1 1/22, 1/24 Proof techniques, formal logic, implications, induction, and application to design of algorithms Kleinberg, Ch. 1, on electronic reserve at the library
2 1/27-1/31 Proof techniques, reduction of one problem to another Kleinberg, Ch. 1
3 2/3-2/7 Big-O bounds, review of mathematical foundations Kleinberg, Ch. 2,
4 2/10-2/14 Cormen Chs. 1, 2; Ch. 3 through page 56
5 2/17-2/21 Heapsort, Elementary Graph Algorithms, independent reading Sections 8.1, 8.2, 8.3, Ch. 6, Ch. 22
6 2/24-2/28 Elementary graph algorithms. Chapter 22
7 3/2-3/6 Elementary graph algorithms; Dijkstra's algorithm, use of abstract data types. Chapter 22, Section 24.3
8 3/9-3/13 Divide-and-conquer strategy Sections 4.1, 4.2, 4.4; Section 33.4 MIDTERM EXAM 6:00-10:00 p.m. Tuesday 3/10. Exam to be posted in 'Modules' on Canvas. Upload your scanned solutions to the Midterm "assignment" in Canvas.
3/16-3/20 SPRING BREAK
9 3/23-3/27 Divide-and-conquer strategy Sections 4.1, 4.2, 4.4; Section 33.4
10 3/30-4/3 Dynamic programming Sections 15.1, 15.2, 15.4, 15.5. Withdrawal deadline extended to 3/31 due to covid-19
11 4/7-4/10 Dynamic programming Sections 15.1-15.5
12 4/13-4/17 Disjoint-set ADT. Greedy strategies. 21.1-21.2. 16.1-16.3.
13 4/20-4/24 Greedy strategies: Minimum spanning trees. 23.1-23.2
14 4/27-5/1 Amortized analysis Chapter 17.
15 5/4-5/8 Assorted topics, review.

Final exam: Thursday, May 14, 11:50-1:50. Download the exam from Canvas, work the problems, scan your solutions, and upload them to a link I will provide on Canvas. The exam is open-book but you must work alone.