Exam
Hand out exam tasks on Wednesday, December 27 until Monday, January 8 .
Exam tasks for 2023 fall descriptions - in the folder Exam questions and data folder
- Task 1 -- explanation of the solution
- Task 2 -- explanation of the solution
- Task 3 -- explanation of the solution
- Results of pre-exam and post-exam survey
The plan is to have them as tasks similar to homework. Certain parts can be achieved more easily and some may take a bit more thinking to achieve. The baseline passing would require 50% points from the exam. The challenge is always to come up with something that hopefully does not have readily available solutions on the Internet and where you actually learn yourself something useful and thus build confidence on what you can now achieve after this course. The partial solutions are also solutions, just receiving a bit fewer points.
Past:
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 later - in classroom or at home -- based on COVID-19 situation and AI assistants
For the in-classroom exam, please see some topics to repeat. For homework-like exam solve those. But do not forget that the course offered a broader set of knowledge.
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