Warning

# Algorithms - seminars

## Semester organization

Programming homeworks
There are 8 programming homeworks in the semester. The total value of the homeworks is 16 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 10 points. The homeworks are assigned and the solutions are evaluated in the upload system.

• Each homework implements some lecture topics, sometimes the that topics might be only a part of the homework. To solve the bigger homework it may be necessary to acquaint oneself with another basic algorithm not covered in the lectures, for example shortest paths in graphs, minimum spanning tree etc.
• A successful solution of a homework must produce a correct result on at least 9 of 10 input data files.
• A successful solution has to be effectively implemented. A time limit is specified for each input data file. The limit varies between 1 and few tens of seconds for different inputs. The solution must produce the result within the time limit.
• The deadlines of the homeworks are fixed. Individual plan can be agreed upon in case of prolonged sickness, foreign trip or other important causes.
• The ALG student forum may help with discussions about the homeworks and other issues of the course.

assignment -- deadline
1.  16.2. --  8.3.   (Lab samples, Recursion)
2.  23.2. -- 15.3.   (Employees, Tree traversal)
3.   9.3. -- 29.3.   (Molecules, Graph search)
4.  16.3. --  6.4.   (Dark streets, Graph search)
5.  23.3. -- 12.4.   (BST processing)
6.   7.4. -- 26.4.   (AVL processing)
7.  13.4. --  3.5.   (Long slopes, DP, DAG)
8.  20.4. -- 10.5.   (Particles, DP)

Correct 10 of given 10 test cases   ... 2 pts
Correct 9 of given 10 test cases    ... 1 pt
Correct 8 or less of 10 test cases  ... 0 pts

Assessment

• It is necessary to obtain at least 10 points for solving the programming homeworks.
• It is vitally important to avoid plagiarism in the homeworks, read carefully the rules of Plagiarism. Consult the teacher in advance if there is anything unclear to you in this regard.

## Seminar problems

Seminar 1. problems – (complexity) – pdf, additional: pdf.
Seminar 2. problems – (recursion, recurrences) – pdf. With solutions: here.
Seminar 3. problems – (tree traversal) – pdf. With solutions: here.
Seminar 4. problems – (graph traversal) – doc. With solutions: doc.
Seminar 5. problems – (search trees, state space search) pdf .
Seminar 6. problems – (AVL and B-trees) – pdf .
Seminar 7. problems – (O(n^2) sorts) – pdf.
Seminar 8. problems – (O(n log(n)) sorts, binary heap) – pdf
Seminar 9. problems – (O(n) sorts) – pdf .
Seminar 10. problems – (Dynamic programming I) – doc. With solutions: doc.
Seminar 11. problems – (Dynamic programming II) – doc. doc.
Seminar 12. problems – (Hash tables I) – I and II: pdf.
Seminar 13. problems – (Hash tables II) – dtto
Seminar 14. problems – (Multi Dim sorts, median search) – In preparation.