Mathematical BackgroundAlsuwaiyel Chapter 2.
Proof by InductionAlsuwaiyel Chapter 5
Asymptotic NotationThe order of an Algorithm. Big-O, Ω, Θ small-o.
- Knapsack Problem
- Coin Change Problem
- Dijkstra's Algorithm
- Prim's Algorithm
- Kruskal's Algorithm
- Huffman Codes
- Best Sum Problem
- Longest Common Subsequence
- Shortest Path Problems - All Pairs
- Matrix Chain Multiplication
- Assembly Line Scheduling
- 3 Colouring Problem
- 8 Queen Problem
- Naive (brute force approach)
- Knuth-Morris-Pratt (KMP) Algorithm and the prefix function
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.
Thursday, November 18, 2010
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.