COMP317-11A Algorithms

COMP317-11A Design and Analysis of Algorithms

Lecturer:	Tony C Smith
	G.2.26A
	838 4453
	tcs @ cs.waikato.ac.nz
Timetable:	lecture/tutorial schedule
Outline:	Course outline
Details:	University catalogue
Lab:	Lab 6 has 26 linux machines allocated for students in this class. Lab 7 has Windows and linux machines open for casual use as well.
Tutor:	Michael Walmsley
Student Reps:	TBA

Assessment

Assignment 1 (15%) Assignment One - external sorting
Assignment 2 (15%) Assignment Two - LZ78 compression
MidTerm Test (10%) Monday, 11 April 2011, starting promptly at 4.30pm, in class (50 mins)
Assignment 2 (15%) Assignment Three - pattern search
Assignment 4 (15%) Assignment Four - line intersection detection (sample data: elevenLines.csv, lines39.csv (view graph), lines100.csv (view graph))
Final examination (30%)

Topics

sorting and complexity
compression:
- LZ77
- LZ78
- LZW
- bit-packing concepts ← not on midterm test
- Shannon-Fano codes, Huffman codes, arithmetic coding
- arithmetic coding
- Laplace rule of succession
- PPM explained with a small example
- PPM
- Burrows Wheeler transform
- another explanation of the Burrows Wheeler transform operations
string searching
- Overview
- Knuth-Morris-Pratt
- Boyer-Moore
- Boyer-Moore code example
- Rabin-Karp
- suffix trie (or tree) — more to come on this topic later
computability
pattern searching:
- overview of regular expressions
- Sedgewick's NFA algorithm for pattern matching and regexp compiler construction—more or less the one I describe in the lectures
- Thompson's NFA algorithm
- My [old] lecture notes on pattern searching(TXT)
- My [old] lecture notes on regexp parsing/compiling(TXT)
- double-ended queue (a.k.a. deque, deck, dequeue)
dynamic programming
- principle of optimality
- longest common subsequence (lots of other examples on the web)
- minimum edit distance
- circuit reliability notes
- knapsack problem (as described by Steve Goddard)
geometric algorithms
- package wrap (Convex Hull)
- graham scan (Convex Hull) done from top to bottom
- k-d tree, plus animations for range searching on k-d trees
- quadtree
- closest-points problem
- line segment intersection via upward horizontal scan.
- line intersection (manhattan topology) by horizontal line scan (n.b. this one sweeps downwards, whereas I did an upward sweep in lecture)
- overview of computational geometry and its algorithms
balanced trees/lists:
- AVL
- Splay Tree
- 2-3-4 tree
- B tree ← not really covered
- red-black tree
- digital search tree & radix search trie
- skip lists
approximation methods and heuristics for NP-hard problems
- NP-hard
- bin-packing ← not really covered
- next-fit, first-fit, best-fit ← not really covered
- travelling salesperson problem ← not really covered
- scheduling ← not really covered
- generate & test
- hill-climbing
- best-first search ← not really covered
- simulated annealing
- genetic algorithms
- evolutionary programming