## Mathematical Background

Alsuwaiyel Chapter 2.## Recurrence Relations

## Proof by Induction

Alsuwaiyel Chapter 5

## Asymptotic Notation

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

## Greedy Algorithms

- Knapsack Problem
- Coin Change Problem
- Dijkstra's Algorithm
- Prim's Algorithm
- Kruskal's Algorithm
- Huffman Codes

## Dynamic Programming

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

## Backtracking

- 3 Colouring Problem
- 8 Queen Problem

## String Matching

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

## Disjoint Sets

## 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

### 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.

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment