Aktualności / News > Dydaktyka / Teaching > Lato/Summer 2018/2019 > Algorithms & Computability / Teoria Algorytmów i Obliczeń

### Algorithms & Computability / Teoria Algorytmów i Obliczeń

#### General rules

- The class consists of exercises and the project.
- During exercises, a student may collect up to 10 points. Moreover, there is a final test during the last exercises. In order to pass exercises, each student must collect at least 25 points.
- The project is worth 50 points in total. In order to pass, the students have to receive at least 25 points.

#### Literature

- everything that was suggested during the lecture,
- Arora, Barak,
*Computational Complexity: A Modern Approach*, Cambridge University Press - Widgerson,
*Mathematics and Computation*, Princeton University Press (to appear)

#### Project rules

- The project is written in pairs.
- The students have to submit the following parts of the project:

theoretical documentation (20 points) - deadline 15.04

implementation (15 points) - deadline: last week of May (27.05/29.05)

test report (15 points) - deadline 03.06/05.06 - For late submission, students get -5 points (for each started week)

#### Project topic (group Mon)

- The input is a natural number
*n.* - We ask for a longest possible sequence of binary k-tuples, such that:
- two consecutive
*k*-tuples differ on exactly one bit, - any two non-consecutive
*k*-tuples differ by at least two bits*.* - Such sequences have applications in error-correcting Gray codes.
- The students are supposed to implement two algorithms.
- an exact algorithm (please make it smarter than a brute force)
- an approximation algorithm of their own design (again, something better than just a greedy approach).
- The expected contents of the documentation:
- formal statement of the problem,
- pseudo-code of algorithms,
- proof of correctness,
- complexity analysis.

#### Project topic (group Wed)

- As input, you are given three natural numbers
*n, m, k.*We assume*k*is much smaller than*n*and*m*. - Consider a graph
*G(n,m)*with vertex set*{0,..,n-1} x {0,...,m-1}*, where edges are of the form*(x,y)(x+1,y)*or*(x,y)(x,y+1)*(addition is performed modulo*n*or*m*, respectively). - We ask for a shortest possible (cyclic) sequence of vertices of
*G(n,m)*, in which every two adjacent vertices appear together in window of length*k+1*(i.e., they appear in the sequence at distance at most*k*). - Such sequences arose from applications in processing medical images.
- The students are supposed to implement two algorithms.
- an exact algorithm (please make it smarter than a brute force)
- an approximation algorithm of their own design (again, something better than just a greedy approach).
- The expected contents of the documentation:
- formal statement of the problem,
- pseudo-code of algorithms,
- proof of correctness,
- complexity analysis.