Next: About this document ... Up: Computer Science 172 Introduction Previous: Schedule

CSC 344 calendar

Spring 2002

Date Assignment Reading Subject
Jan. 28 HW1   Administrivia, syllabus, what's an algorithm, what's efficiency?
Jan. 30     Problems and instances, problem size, factors affecting efficiency
Feb. 1     Problems and instances, problem size, factors affecting efficiency
Feb. 4   pp. 3-16 Measuring algorithms; ignoring constant factors & small n's
Feb. 6 HW1 due; HW2 pp. 16-26 Review of math techniques, big-O notation
Feb. 8   pp. 27-32 Basic data structures
Feb. 8 Deadline to add courses
Feb. 11     Abstract data types vs. implementations
Feb. 13     Discuss homework
Feb. 15   pp. 33-39 Numerical programming, error propagation, selection sort with different data structures
Feb. 18   pp. 40-50 Sorting algorithms; using sorting to solve other problems
Feb. 20     Hash tables and hashing functions
Feb. 22 HW2 due   Heapsort and Mergesort; mention lower bounds
Feb. 22 Deadline to drop courses
Feb. 25   pp. 53-62 Quicksort; Memoization and dynamic programming
Feb. 27     Discuss homework and big-O notation
Mar. 1 HW3 pp. 62-75 Applications of dynamic programming
Mar. 4   pp. 75-80 Divide-and-conquer algorithms (and dynamic programming)
Mar. 6     Recurrence relations and divide-and-conquer algorithms
Mar. 8     The Master Method for solving recurrence relations
Mar. 11 HW3 due   Analyzing algorithms with the Master Method
Mar. 13     Improving algorithms with the Master Method; integer multiplication; mentioned FFT's and applications to multiplication and music
Mar. 15   pp. 81-92 Graphs, graph problems, adjacency-matrix representation
Mar. 18     Review for midterm exam
Mar. 20     Midterm exam
Mar. 22     Discuss midterm exam
Mar. 25-29 Spring break: no classes
Apr. 1 Deadline to withdraw from courses
Apr. 1 HW4, in part   Discuss homework & dynamic programming
Apr. 3     Adjacency-list representation; MST, connectedness, reachability problems
Apr. 5   pp. 81-92 Depth-first and breadth-first search; reachability, shortest paths, and connectedness
Apr. 8 HW4, the rest pp. 90-95 More fun with DFS and BFS; classifying edges
Apr. 10   pp. 95-102 Minimum spanning trees and shortest paths
Apr. 12   pp. 102-113 Applications of graph algorithms
Apr. 15   pp. 100-101 Dijkstra's Algorithm for shortest paths
Apr. 17     Analyzing Dijkstra's algorithm, with various data structures for various variables
Apr. 19   p. 102 Floyd-Warshall's algorithm
Apr. 22 HW4 due pp. 115-125 Backtracking: mouse in a maze
Apr. 24   pp. 125-134 Heuristic techniques: local search, simulated annealing, neural nets, genetic algorithms
Apr. 26   pp. 139-141 Problem reductions to show something is easy
Apr. 29   pp. 141-143 Problem reductions to show something is hard
1-May   pp. 143-144 P and NP; more reductions; hard vs. complete
3-May   pp. 144-147 NP-completeness of SAT
6-May     The polynomial hierarchy; space-bounded classes; parallel complexity classes NC1, AC0, NC
8-May     Catch up and review for final
10-May     Catch up and review for final
15-May Final exam, 8:00-10:00

Last modified:
Stephen Bloch