
TCSS 343, Spring 2007
Algorithms
Course Schedule
Material covered by schedule subject to change, although the date of the final exam is fixed. This schedule is very tentative!
Schedule is numbered by week.  (3/26): Introduction, overview of Algorithm design; analysis of nonrecursive algorithms.
Read 1.11.4, 2.12.4, Appendix A. (3/28): Analysis of recursive algorithms. Loop Invariants, BigOh notation review. Review data structures. 
(4/2):
Divide and conquer algorithms (including at least Merge sort), recurrence relations, and analysis of them. Assignment #1 due.
Read 4.14.3, 4.6
(4/4) Quicksort, solving recurrence relations

(4/9): Master Theorem, Closest Pair, Assignment #2 due.
Read 4.5, 4.6.
(4/11): biginteger multiplication, midterm review. [Convex Hull].

(4/16): Midterm 1 on Monday, 4/16.
Read 4.4, 8.1, 8.2, 8.4
(4/18):Review trees, start dynamic programming.

(4/23): More dynamic programming., including knapsack. Assignment #3 due.
(4/25): Even more dynamic programming (including floyd's) with routing table.

(4/30): Decreases & conquer, DFS/BFS, Strongly connected components
Read 8.2, 5.15.4.
(5/2): Topological sort, strongly connected components, quickselect.

(5/7): Greedy algorithms, Prim's, Kruskal's.
Read chapter 9.19.3
(5/9): Midterm review, linebreaking problem (dynamic programming).

(5/14): Midterm 2 on Monday, 5/14.
(5/16): Greedy graph algs Dijkstra, Prim's runtime; Locators.

(5/21): Finish Dijkstra correctness; Transform and conquer.
Read chapter 6.1, 6.46.6. (5/23): TransformandConquer, lower bound stuff.

(5/28): Holiday, no class.
Read chapter 7.1,7.3.
(5/30): Space and Time Tradeoffs.
 Final Exam date: Monday, June 4, 2007
