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

  1. The class consists of exercises and the project.
  2. 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.
  3. The project is worth 50 points in total. In order to pass, the students have to receive at least 25 points.

Literature

Project rules

  1. The project is written in pairs.
  2. 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
  3. For late submission, students get -5 points (for each started week)

Project topic (group Mon)

  1. The input is a natural number n.
  2. 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.
  3. Such sequences have applications in error-correcting Gray codes.
  4. 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).
  5. The expected contents of the documentation:
    • formal statement of the problem,
    • pseudo-code of algorithms,
    • proof of correctness,
    • complexity analysis.

Project topic (group Wed)

  1. As input, you are given three natural numbers n, m, k. We assume k is much smaller than n and m.
  2. 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).
  3. 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).
  4. Such sequences arose from applications in processing medical images.
  5. 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).
  6. The expected contents of the documentation:
    • formal statement of the problem,
    • pseudo-code of algorithms,
    • proof of correctness,
    • complexity analysis.
Powered by CMSimple