Programming homeworks
There are 6 programming homeworks in the semester. The total value of the homeworks is 12 points, the value of each one homework is 2 points. To obtain the assessment it it necessary to solve successfully a number of problems which yields at least 8 points.

Exam terms and locations

Register yourself in the exam schedule document
The exams are organized with respect to the given document only. Do not use KOS system to register yourself, it will have no effect. If a particular term capacity is exceeded the priority will be given to the students listed in the schedule. Ask your teacher for clarification if anything in the exam scheme is not obvious to you.

Organization

The exam consists of the theoretical and the programming part.
At the theoretical part the student is given a few questions (typically about 4-5) and writes down main lines of the solution. Sometimes a question might demand a more detailed written solution (a code, a list of cases etc). The teacher will discuss the solution with the student and determine the grading. Each question should be solved with at lest 50% success. If a student fails to achieve 50% success in a question he/she will be given another broader auxiliary question. The auxiliary question must be solved more or less completely correctly. If this solution is correct the original question is considered to be 50% successful. If the solution of the auxiliary question is not satisfactory the whole theoretical exam part is evaluated as unsuccessful.
No additional sources including printed and electronic may be used at the theoretical part.

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 4 hours (240 min). In the first 30 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.

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       E 
 24  -  26       D  
 27  -  30       C 
 31  -  34       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.