Calendar of topics and assignments

CSC 344, Spring 2005

Last modified:

Date Assignment Reading Subject
20-Jan HW1   Administrivia; problems, instances, algorithms, and programs
25-Jan   1.1-1.3 Basic concepts
27-Jan   1.4 Review basic data structures
28-Jan Deadline to add courses
1-Feb   2.1-2.2 Efficiency, resources, and what should affect them
3-Feb HW1 due; HW2   Presentations & discussion on Euclid's game
8-Feb     Discuss HW1
10-Feb   2.3-2.4 How to analyze an algorithm's efficiency
15-Feb Deadline to drop courses
15-Feb   2.5-2.7 Loops and recursion
17-Feb   Appendix B Solving recurrence relations
22-Feb HW2 due 4.1-4.3 Selection (heap), Insertion (tree), and Mergesort
24-Feb   4.2, 4.6 Quicksort; some geometric examples
1-Mar HW3   Homework, convex hulls, lower bounds...
3-Mar   5.1-5.3 DFS, BFS, topological sorting
8-Mar   5.5-5.6 More decrease-and-conquer algorithms
10-Mar   6.1-6.3 Instance simplification
15-Mar HW3 due 6.4-6.5 Representation change
17-Mar   6.6 Problem reduction
19-27-Mar Spring break; no classes
28-Mar Deadline to withdraw from courses
29-Mar   7.1-7.2 Speed, for a price
31-Mar   7.1-7.2 String matching with preprocessing
5-Apr   7.3 Hashing
7-Apr HW4 7.3, 8.1-8.2 More hashing; start on dynamic programming
12-Apr   8.3-8.4 More examples of dynamic programming
14-Apr   9.1-9.3 Greedy algorithms
19-Apr     Cryptography
21-Apr   10.1-10.2 Proving a problem is difficult
26-Apr     Computability and uncomputability
28-Apr   10.3 Complexity, P and NP, NC and friends
3-May HW4 due 2003 Final Exam Catch up and review
12-May Final exam, 10:30-12:30