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

   • Cormen - Chapter 4
   • Wikipedia

3. Proof by Induction

   Alsuwaiyel Chapter 5
   

4. Asymptotic Notation

   The order of an Algorithm. Big-O, Ω, Θ small-o.
   
   • Alsuwaiyel Chapter 1
   • Cormen - Chapter 3

5. Greedy Algorithms

   • Alsuwaiyel Chapter 8
   • Cormen - Chapter 16
   • Knapsack Problem
   • Coin Change Problem
   • Dijkstra's Algorithm
   • Prim's Algorithm
   • Kruskal's Algorithm
   • Huffman Codes

6. Dynamic Programming

   • Alsuwaiyel Chapter 7
   • Cormen - Chapter 15
   
   
   • Best Sum Problem
   • Longest Common Subsequence
   • Shortest Path Problems - All Pairs
   • Matrix Chain Multiplication
   • Assembly Line Scheduling

7. Backtracking

   • Alsuwaiyel Chapter 13
   • Wikipedia
   • 3 Colouring Problem
   • 8 Queen Problem

8. String Matching

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

9. Disjoint Sets

   • Alsuwaiyel Chapter 4
   • Wikipedia

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.