Thursday, November 18, 2010

Course Outline

For my own sanity I have decided to put together a list of everything that was mentioned in class up to this point. It should help with planning how we are going to prepare for exams.

  1. Mathematical Background

    Alsuwaiyel Chapter 2.
  2. Recurrence Relations

  3. Proof by Induction

    Alsuwaiyel Chapter 5
  4. Asymptotic Notation

    The order of an Algorithm. Big-O, Ω, Θ small-o.
  5. Greedy Algorithms

    • Knapsack Problem
    • Coin Change Problem
    • Dijkstra's Algorithm
    • Prim's Algorithm
    • Kruskal's Algorithm
    • Huffman Codes
  6. Dynamic Programming

    • Best Sum Problem
    • Longest Common Subsequence
    • Shortest Path Problems - All Pairs
    • Matrix Chain Multiplication
    • Assembly Line Scheduling
  7. Backtracking

    • 3 Colouring Problem
    • 8 Queen Problem
  8. String Matching

    • Naive (brute force approach)
    • Knuth-Morris-Pratt (KMP) Algorithm and the prefix function

  9. Disjoint Sets

  10. Other Things that I have not categorized

    • Bellman-Ford Algorithm and Relaxation
    • Floyd-Warshall Algorithm
    • Transitive Closure
    • Magic Squares - siamese technique for odd ordered sqaures, LUX for singly even ordered squares.

No comments:

Post a Comment