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