CPSC 311 - Analysis of Algorithms

Syllabus

Notes and Announcements

Class Members

To see class members, go to THIS page.

Assignments

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