Aktualności / News > Dydaktyka / Teaching > Historia / History > Algorithms & Computability / Teoria Algorytmów i Obliczeń, summer 2018/19
Algorithms & Computability / Teoria Algorytmów i Obliczeń, summer 2018/19
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.