COMP526 - preparation list
--------------------------

WEEK 1:

* theoretical (asymptotic) vs. experimental analysis
* computational model (RAM), pseudo-code
* time complexity, space complexity
* basic operations, worst case vs. average case complexity
* asymptotic notation: Big O and Big Omega
* frequent functions: logarithms, polynomials, exponentials
* growth rate of complexity functions
* mathematical induction 
* loop invariant method and decreasing function

WEEK 2:

* simple recursive algorithms, recurrence equations
* basic data structures: stack, queue, list 
* trees (and their representations) 
* priority queues (heap)
* sets (and their representations)

WEEK 3:

* string and string processing, Fibonacci language
* periodicity and periodicity lemma
* string/pattern matching and brute force algorithm
* Knuth-Morris-Pratt algorithm and failure function 
* the amortisation method
* Boyer-Moore and Karp-Rabin algorithms

WEEK 4:

* non-periodicity, witnesses, and elimination via duels
* PRAM and parallel string matching via duels
* pattern matching with don't care symbols
* product of polynomials, FFT and convolutions

WEEK 5:

* tries, suffix-trees and off-line pattern matching
* compact suffix trees
* longest repeated string, longest shared sub-string
* LCA (lowest common ancestor)
* pattern matching with k-mismatches
* suffix arrays

WEEK 6:

* data compression
* run-length encoding, move-to-front transform
* cyclic-rotations and Burrows-Wheeler transform
* LZW Lempel-Ziv-Welch compression and decompression

WEEK 7:

* Huffman coding, cost of Huffman trees, construction of Huffman trees
* basics of information theory, entropy and Huffman code
* error detection and error correction
* Hamming codes
* CRC (cyclic redundancy checking)
* Detection via parity of subsets of bits

WEEK 8:

* CGT (combinatorial group testing), adaptive and non-adaptive
* k-disjunct matrix, feedback vector, evidence against membership
* (d,m,n)-selectors and 2-stage CGT
* Searching for frequent items 

WEEK 9:

* sequential merging, time complexity O(n)
* sequential merge-sort, recursive approach, depth of recursion log n, merging lists based approach, time complexity O(n log n)
* sequential quick-sort, randomised recursive approach, expected depth of recursion O(log n), and time complexity O(n log n)
* Parallel prefix sums and list ranking (based on values 0/1), time complexity O(log n)
* Information dissemination, reverse process to prefix sums computation, time complexity O(log n)
* Parallel quick-sort based on list ranking and information dissemination, expected time complexity O(n log n)
* Parallel merge-sort based on merging via binary search, time complexity O(n log n)  

WEEK 10:

* basics of probability, probability space and function
* sublinear algorithms, testing 0*1* strings
* notion of distance, regular and relative Hamming/Edit distance
* input representation, epsilon-tester, testing sorted sequences