Registration

Register yourself in Exams timetable

Do not try to register via KOS, that would not work in Algorithms. The exams are organized solely according to the Exams timetable linked above.

Organization

The exam consists of the theoretical and the programming part.

At the theoretical part the student is given a few questions (about 4-5) and writes down main lines of the solution. Typically, a question demands to write important details of the solution – a pseudocode, list of steps leading to the solution, explanation of the calculations, how the asymptotic complexity is derived in particular cases, etc.
The time for the solution is 1.5 - 2 hours.
No additional sources including printed and electronic may be used at the theoretical part.
The teacher will evaluate the written solution and upload it into brute. Optionally, the evaluation may be extended to an online consultation, if the evaluation is not clear to the student or if he or she wants to discuss any issue in their solution. The examiner may then update the evaluation/grade.
Each question should be solved with at lest 50% success.

At the programming part the student must solve a programming problem similar (and somehow simpler) to the semester programming homeworks. There are 10 data input files associated with the problem and the student's code must yield a correct solution of at least 5 files. The programming part lasts 3 hours (180 min). In the first 20 minutes of this part it is not allowed to write a code. This time is intended for individual analysis of the problem. Students can bring to the programming part any printed or electronic sources. Each student solves the programming problem individually using his/her own notebook. Accessing internet during the exam is permitted only under teacher's supervision. Any unsupervised internet access is considered to be a breach of the exam rules.

Bring in your own notebook
If you want to use a school computer instead, notify the teacher, at least one week in advance.

Late minimum correction
When you find after the failed practical exam that the failure was caused by a trivial error in your code you may ask the examiner for repeated evaluation of the corrected code. If the corrected code works according to the exam demands you may still pass this part of the exam. The necessary conditions of a success in such case are 1. The correction must be conceptually simple and physically short (few lines of code, at most). 2. The original failled solution must be uploaded to Brute before the end of the exam. 3. The correction must be done in the day of the exam.

Consecutive terms
A student which fails at any part of the exam (theoretical or programming) may repeat this part in any of later exam terms and does not have to repeat the remaining part. His/her results in the other part are not affected. When a student repeats some part more times only his/her best result from all terms of this part is graded. In total each student can take part in at most three terms of the theoretical part and three terms of the programing part.

Points and grading
At the exam, a total of the following is computed:

• Points gained by solving homeworks. Acceptable minimum is 8 points.
  
• Points gained by solving the programming part. Acceptable minimum is 5 points. Each correctly processed input file of total 10 files is worth 1 point.
  
• Points gained by solving the theoretical part. Acceptable minimum is 8 of maximum 16 points. The amount of points gained is decided by the examiner.

Points total   Grade  
============   =====
      < 21       F 
 21  -  23.99    E 
 24  -  26.99    D  
 27  -  30.99    C 
 31  -  34.99    B 
 35  -  38       A

1. Order of function growth and asymptotic complexity

• Formal definition of Order of growth, sets O(f(n)), Ω(f(n)), Θ(f(n))
• Informal definition of asymptotic complexity of an algorithm
• Assessing the asymptotic complexity of a short code which contains only loops and no recursion

2. Recursion

• Recursion tree
• Recurrences
• Assessing the asymptotic complexity of a short recursive code or an algorithm using its recursion tree
• Master theorem
• Apply master theorem to particular recurrences

3. Graph basics

• Directed and undirected graph, tree, rooted tree, weighted graph
• Graph representation - adjacency matrix, list of neighbours
• Graph searching - DFS, BFS.
• Traversing rooted trees, Pre-, In-, Post-order

4. Search trees

• BST, AVL, B-tree, rotations in binary tree
• Operations Find, Insert, Delete in search trees

5. Sort Algorithms

• Insert sort, Quick sort, Merge sort, Heap Sort, Radix sort, Counting sort
• Sort stability
• Heap, priority queue, operations Insert, Find

6. Dynamic programming

• Directed acyclic graph (DAG), topological order
• Turning recursion into tabelation, DP table
• Examples of DP problems

7. Hash tables

• Hash functions, collision, clusters
• Resolving collisions - Separate chaining, Linear probing, Double hashing, Coalesced hashing

Notes

A. Basic mathematical skills are indispensable in ALG. In particular, you should understand and be able to manipulate successfully the following: Arithmetic and geometric progression, its sum. Binomial coefficients, factorial, permutations, combinations. System of 2 or 3 linear equations. Quadratic equation and inequation, roots of quadratic function.

B. Asymptotic complexity is one of central concepts in effective programming and computer science. It is vitally important that you understand the concept and not just remember the definition(s). For example, you should be able to answer a question like: “All values from an NxN array A are copied to another 1D array B and B is then sorted. What is the complexity of the whole process? Why is it such?” The same holds for the recursion and recursive algorithms. Their complexity depends on the size and shape of the corresponding recursion tree, you should be familiar with the concept of the rooted tree, its properties, and be able to calculate depth, size and cost of a (recursion) tree in at least simple cases.

C. Most exam questions ask you to create an algorithm or to modify an existing one or to derive the properties of a proposed modification of some algorithm or data structure. Usually, just remembering and reproducing the ALG facts from the lectures is not enough to pass the exam. What is being “evaluated” is your capability to come up with a solution of a fresh problem and your ability to discuss sensibly the complexities (time and memory) and/or other properties of your solution. The seminars problems listed on ALG seminars webpage will provide you with training material. Mostly, those problems are just copies of previous years' exam questions.

The programming problem is mostly related to the following:

• Graph manipulation and/or searching
• Backtracking problems

The programming problem SHALL NOT ask you to implement

• Search tree operations
• Hash tables operations
• Standard algorithms outside the scope of the course (e.g. Dijkstra, Text search, etc.)
• Any particular sort method

Tips

A. Good understanding of the theory (see notes above) helps very much with the programming problem. Try to solve as much as possible of the problem without touching the keyboard.

B. Come equipped. Bring with you reliable algorithms sources (printed or downloaded) with examples, codes etc., it might help.

C. Consult the examiner during the exam. Though they will not tell you the solution, they might give you valuable hints, when you are stuck or not sure how to proceed.

Examples of previous years Algorithms programming exam problems. In 2023, the expected topics are mainly: rooted tree processing and recursion/backtrack (not necessarily related to trees).

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8

The examples are listed in no particular order.

Examples of the theoretical part test

1. 4 questions in one test in 2021, The same set with solutions/hints

2. 4 questions in another test in 2021, The same set with solutions/hints