COMP271 -- SPRING 2003 

Tentative Syllabus

 

  1. Introduction & Review
  2. Maximum Contiguous Subarray:  case study in algorithm design
  3. Divide-and-Conquer Algorithms:
    1. Mergesort
    2. Polynomial Multiplication
    3. Randomized Selection
  4. Graphs:
    1. Review: Notation, Depth/Breadth First Search
    2. Cycle Finding  & Topological Sort
    3. Minimum Spanning Trees: Kruskal's and Prim's algorithms
    4.  Dijkstra's shortest path algorithm
  5. Dynamic Programming
    1. Knapsack
    2. Chain Matrix Multiplication,
    3. Longest Common Subsequence
    4. All Pairs Shortest Path
  6. Greedy algorithms:
    1.  Activity Selection
    2.  Huffman Coding
  7. Complexity Classes:
    1. Nondeterminism
    2. the classes P and NP,
    3. NP-complete problems
    4. polynomial reductions

Return to COMP271 Home page