CPSC 311 - Analysis of Algorithms

Syllabus

Notes and Announcements

Grades on the final and the last homeworks helped the class as a whole significantly. A final curve of 12% was applied for the class. In addition, two students' borderline grades were bumped up to the next highest grade. The final grade distribution was:
- 6 A's
- 5 B's
- 8 C's
- 3 D's
- 2 F's
That distribution is significantly better than the one from the last update handed out in class - the number of A's is the same, the number of B's has increased, and the number of F's and D's has decreased.
The overall grade breakdown, listed by alias, can be found HERE. Note: Green indicates a free late, red indicates an adjusted grade (possibly for a second late assignment), and blue indicates adjusted programming assignments. Bold grades indicate those "bumped up" or a special case (one F was from someone who no longer attended class).
Dr. Keyser will not be in class for February 5-9. Class will still be held, with Dr. Teresa Leyk giving the lectures.
Dr. Keyser will be gone on February 22-23. Class will still be held, but office hours are cancelled.
The original paper describing skip lists can be downloaded HERE.
Dr. Keyser will not be available during regular office hours on March 6 and 8. Instead, that week, the following extra hours will be offered:
- Monday, March 5: 2:00 - 3:00, 4:00 - 5:00
- Wednesday, March 7: 10:30 - 11:30
- Thursday, March 8: 4:00 - 5:00
As always, you can also arrange for meetings by appointment.
Dr. Keyser will be gone from after class April 11 - April 13. The TA will lecture on April 13.

Class Members

To see class members, go to THIS page.

Assignments

Written Homework 1: Asymptotic Analysis and Algorithm Correctness
Written Homework 2: Sorting and Order Statistics
Written Homework 3: Search Structures
Written Homework 4: Dynamic Programming, Greedy Algorithms, and Advanced Structures
Written Homework 5: Graph Algorithms and some NP-completeness
Programming Homework 1: Understanding Asymptotic Growth
Programming Homework 2: Implementing Graph Algorithms

Schedule

Future dates should be considered tenative for all information on class topics, chapters covered, and homework not yet assigned.

Day			Topics	Reading Covered or Assigned	Homework Assigned	Homework Due
1	Wed	Jan. 17	No class due to University closure	Chapters 1, 2.1
2	Fri	Jan. 19	Introduction Loop Invariants and Program Correctness	Chapters 1, 2
3	Mon	Jan. 22	Asymptotic Running Times	Chapter 3 Appendix 1
4	Wed	Jan. 24	Recursion and Algorithm Analysis	Section 2.3
5	Fri	Jan. 26	Solving Recurrances	Sections 4.1, 4.2
6	Mon	Jan. 29	The Master Method Examples	Section 4.3
7	Wed	Jan 31	Heapsort	Chapter 6	Written HW 1
8	Fri	Feb. 2	Quicksort	Chapter 7
9	Mon	Feb. 5	Linear Sorts	Chapter 8
10	Wed	Feb. 7	Review and Comparison of Sorts
11	Fri	Feb. 9	Order Statistics	Chapter 9
12	Mon	Feb. 12	Basic Data Structure Review Direct Address Tables	Chapter 10 Section 11.1	Programming HW 1
13	Wed	Feb. 14	Hash Tables	Sections 11.2, 11.3
14	Fri	Feb. 16	Open Addressing	Section 11.4	Written HW 2	Written HW 1
15	Mon	Feb. 19	Binary Search Trees	Chapter 12
16	Wed	Feb. 21	Review Red-Black Trees	Chapter 13
17	Fri	Feb. 23	Midterm 1 Through Hashing (class 14)
18	Mon	Feb. 26	Red-Black Trees	Chapter 13
19	Wed	Feb. 28	B-Trees	Chapter 18
20	Fri	Mar. 2	Review Midterm 1			Written HW 2
21	Mon	Mar. 5	B-tree Insertion/Deletion Skip Lists	Skip List Paper	Written HW 3
22	Wed	Mar. 7	Dynamic Programming	Sections 15.1, 15.3
23	Fri	Mar. 9	Dynamic Programming Example: Matrix Multiplication	Sections 15.2		Programming HW 1
			Spring Break
24	Mon	Mar. 19	Dynamic Programming Example: Longest Common Subsequence Greedy Algorithms	Section 15.4 Section 16.1
25	Wed	Mar. 21	Greedy Algorithms	Section 16.2
26	Fri	Mar. 23	Huffman Codes Disjoint Sets	Section 16.3 Sections 21.1-21.2
27	Mon	Mar. 26	Disjoint Set Forests Graph Representations	Section 21.3 Section 22.1		Written HW 3
28	Wed	Mar. 28	Breadth-First Search Depth-First Search	Sections 22.2, 22.3	Written HW 4
29	Fri	Mar. 30	Topological Sort Strongly Connected Components	Sections 22.4, 22.5
30	Mon	Apr. 2	Minimum Spanning Trees	Chapter 23
31	Wed	Apr. 4	Minimum Spanning Trees Single Source Shortest Path	Sections 24.1, 24.2	Programming HW 2
	Fri	Apr. 6	No class - reading day
32	Mon	Apr. 9	Single Source Shortest Path	Sections 24.3 - 24.5
33	Wed	Apr. 11	Polynomial Time Algorithms	Sections 34.1, 34.2		Written HW 4
34	Fri	Apr. 13	All Pairs Shortest Path	Chapter 25
35	Mon	Apr. 16	All Pairs Shortest Path Review		Written HW 5
36	Wed	Apr. 18	Midterm 2 Through Disjoint Sets (class 27)
37	Fri	Apr. 20	NP-Completeness	Section 34.3
38	Mon	Apr. 23	NP-Completeness Proofs	Section 34.4
39	Wed	Apr. 25	NP-Completeness Proofs	Section 34.5
40	Fri	Apr. 27	Approximation Algorithms	Chapter 35
41	Mon	Apr. 30	Topic to be determined (Computational Geometry?)			Written HW 5
42	Tue	May 1	Review			Programming HW 2
	Wed	May 9	Final Exam Time, 10:30 - 12:30