Exam in Algoritmics (MTAT.03.238)
Exam Date I - January 5th (Friday) @ 10-13 L2-405
Exam Date II - January 8th (Monday) @ 10-13 L2-403
For the exam you only need a pen and possibly a cheat sheet. A single one-sided A4 “cheat-sheet” is allowed. Submit it with your exam.
For repeating the material please make sure to understand the basic concepts from every set of lecture materials.
- Complexity - the O, o, Theta, Omega, omega relations between functions, and how to prove that relationship holds.
- Recurrences (e.g. T(n)= 2*T(n/2) + n) and use of the master theorem
- Theoretical and practical considerations about sorting algorithms (remember the pre-course questionnaire?)
- Binary search, array-based linear structure, linked list, skip-list
- Binary search tree BST, balanced BST, B-tree
- Hashing, hash functions, universal hashing, Bloom filters
- Binary heap, binomial heap
- Amortised analysis
- Augmentation of data structures
- Tree traversal orders and recursive and non-recursive traversal algorithms
- Graph traversal orders (BFS, DFS, random, prioritised order) and algorithms (recursive, queue, priority queue based)
- Shortest path, Dijkstra, A* algorithms
- Topological sorting, maximum flow, transitive closure by matrix multiplications
- Succinct data structures concept
- Optimisation - finding the best "instance" or value or configuration
- Heuristic search concepts - greedy, local search,
- Meta-heuristics: simulated annealing, tabu-, genetic and evolutionary algorithms, differential evolution, ACO, swarm
- Dynamic programming
- Text search: KMP, Boyer Moore and Aho Corasick algorithms
- Trie for keywords, suffix trie for all suffixes, suffix tree (compact version of the trie), suffix array
- Burrows-Wheeler transformation: e.g. decode 'smymcrt!heraisr'
Exam questions will be mostly descriptive - 4-5 "larger" questions
- discuss the main principle of (e.g. Bloom filters, meta-heuristics, etc)
- examples add numbers like 2,5,7,1,9,3 into BST,
- given a graph provide the output for some algorithm,
- prove the complexity class relation for a function;