SubjectsSubjects(version: 845)
Course, academic year 2019/2020
   Login via CAS
Complexity I - NTIN062
Title in English: Složitost I
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/1 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: cancelled
Language: Czech
Teaching methods: full-time
Guarantor: doc. RNDr. Ondřej Čepek, Ph.D.
Class: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Theoretical Computer Science
Interchangeability : NTIN090
Is co-requisite for: NTIN063
Is incompatible with: NTIN090
Is pre-requisite for: NTIN023
In complex interchangeability with: NTIN090
Annotation -
Last update: T_KTI (20.04.2004)
This is a basic course on the complexity of algorithms. Roughly the first half of the course is devoted to the study of concrete algorithms of various types (graph algorithms, divide and conquer algorithms, greedy algorithms) which work in polynomial time. The time complexity is analyzed both "classically" (worst case analysis) and in an amortized manner. The second half of the course is then devoted to the study of the NP class, polynomial reducibility among problems, and NP-completeness proofs for various problems. The course concludes with several topics related to NP-completeness.
Aim of the course - Czech
Last update: T_KTI (23.05.2008)

Naučit základy z teorie složitosti algoritmů, včetně NP-úplnosti a převoditelnosti.

Literature - Czech
Last update: doc. RNDr. Ondřej Čepek, Ph.D. (08.04.2004)

L. Kučera: Kombinatorické algoritmy

J. Plesník: Grafové algoritmy

Cormen, Leiserson, Rivest : Introduction to algorithms, Mc Graw Hill 1990

Kozen : Design and analysis of algorithms, Springer-Verlag 1992

Tarjan : Data structures and network algorithms, SIAM, 1983

Garey, Johnson : Computers and intractability - a guide to the theory of NP-completeness, W.H.Freeman 1978

Syllabus -
Last update: T_KTI (20.04.2004)

1. Time complexity of algorithms, asymptotic notation.

2. Divide and conquer algorithms (linear time median algorithm, Strassen's matrix multiplication), methods for solving recursive equations which describe the complexity of such algorithms.

3. Greedy algorithms on weighted matriods, their applications (minimum spanning tree, scheduling problems).

4. Graph algorithms based on DFS and BFS.

5. Lower bounds for time complexity of problems, decision trees, lower bound for sorting by comparisons.

6. Amortized complexity, binomial and Fibonacci heaps and their application in Dijkstra's algorithm.

7. Formal definitions of classes P and NP, polynomial reducibility among decision problems, NP-completeness.

8. Pseudopolynomial algorithms and strong NP-completeness.

9. Counting problems, class #P, #P-completeness.

10.Approximations of NP-hard problems, completely polynomial approximation schemes.

Charles University | Information system of Charles University |