Exam
Exam dates and times are:
- Exam Date I -
- Exam Date II -
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.
Exam type will be decided based on COVID-19 situation
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
- 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
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;
- etc.