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.
  1. (3/26): Introduction, overview of Algorithm design; analysis of non-recursive algorithms.
    Read 1.1-1.4, 2.1-2.4, Appendix A.
    (3/28): Analysis of recursive algorithms. Loop Invariants, Big-Oh notation review. Review data structures.
  2. (4/2): Divide and conquer algorithms (including at least Merge sort), recurrence relations, and analysis of them. Assignment #1 due.
    Read 4.1-4.3, 4.6
    (4/4) Quicksort, solving recurrence relations

  3. (4/9): Master Theorem, Closest Pair, Assignment #2 due.
    Read 4.5, 4.6.
    (4/11): big-integer multiplication, midterm review. [Convex Hull].
  4. (4/16): Midterm 1 on Monday, 4/16. Read 4.4, 8.1, 8.2, 8.4
    (4/18):Review trees, start dynamic programming.
  5. (4/23): More dynamic programming., including knapsack. Assignment #3 due.
    (4/25): Even more dynamic programming (including floyd's) with routing table.
  6. (4/30): Decreases & conquer, DFS/BFS, Strongly connected components
    Read 8.2, 5.1-5.4.
    (5/2): Topological  sort, strongly connected components, quick-select.  
  7. (5/7):  Greedy algorithms, Prim's, Kruskal's.
    Read chapter 9.1-9.3
    (5/9): Midterm review, line-breaking problem (dynamic programming).
  8. (5/14): Midterm 2 on Monday, 5/14.
    (5/16): Greedy graph algs Dijkstra, Prim's run-time; Locators.
  9. (5/21): Finish Dijkstra correctness; Transform and conquer.
    Read chapter 6.1, 6.4-6.6.
    (5/23): Transform-and-Conquer, lower bound stuff. 
  10. (5/28): Holiday, no class.
    Read chapter 7.1,7.3.
    (5/30): Space and Time Tradeoffs.

  11. Final Exam date: Monday, June 4, 2007