VSFS:N_VSA Algorithmic Complexity - Course Information
N_VSA Algorithmic Complexity
University of Finance and AdministrationWinter 2021
- Extent and Intensity
- 2/1/0. 6 credit(s). Type of Completion: zk (examination).
- Teacher(s)
- prof. RNDr. Ondřej Čepek, Ph.D. (seminar tutor)
- Guaranteed by
- prof. RNDr. Ondřej Čepek, Ph.D.
Department of Computer Science and Mathematics – Departments – University of Finance and Administration
Contact Person: Ivana Plačková - Timetable of Seminar Groups
- N_VSA/vAPH: Fri 15. 10. 14:00–15:30 S22, 15:45–17:15 S22, Fri 5. 11. 14:00–15:30 S22, 15:45–17:15 S22, Fri 19. 11. 14:00–15:30 S22, 15:45–17:15 S22, Sat 20. 11. 9:45–11:15 E304, 11:30–13:00 E304, 14:00–15:30 E304, O. Čepek
- Prerequisites
- Basic knowledge of mathematical analysis, discrete mathematics, and programming.
- Course Enrolment Limitations
- The course is offered to students of any study field.
- Course objectives
- Students acquire a basic overwiev of the concepts related to time and space complexity of algorithms.
- Learning outcomes
- After finishing this course students will be capable of:
- analyzing the time and space complexity of concrete algorithms with polynomial complexity;
- recognizing computationally intractable problems and determining the complexity class in which they belong;
- proving NP-hardness of concrete computationally intractable problems using polynomial time transformations. - Syllabus
- 1. Time and space complexity, asymptotic notation, examples of use.
- 2. Determinism and non-determinism, examples of non-deterministic algorithms.
- 3. Classes P and NP, examples of problems from the class NP.
- 4. Polynomial transformations, examples of transformations among NP problems.
- 5. NP-hardness and NP-completeness, examples od optimization and decision problems from these classes.
- 6. Cook-Levin theorem (an existence of an NP-complete decision problem).
- 7. Strong NP-completeness, examples.
- 8. Pseudopolynomial algorithms.
- 9. Aproximation algorithms for NP-hard optimization problems.
- 10. Non-aproximability, examples of non-aproximable optimization problems.
- 11. Probabilistic algorithms (Las Vegas and Monte Carlo).
- 12. Space complexity, Savitch's theorem.
- Literature
- recommended literature
- Černý, Michal. Výpočty, svazky I,II,III. Professional Publishing 2012. ISBN: 978-80-7431-049-2
- Teaching methods
- Lectures to cover theory, practical exercises to study examples.
- Assessment methods
- Written test.
- Language of instruction
- Czech
- Further comments (probably available only in Czech)
- The course can also be completed outside the examination period.
Information on the extent and intensity of the course: 18 hodin KS/semestr. - Teacher's information
- http://ktiml.mff.cuni.cz/~cepek/vyuka.html
- Enrolment Statistics (Winter 2021, recent)
- Permalink: https://is.vsfs.cz/course/vsfs/winter2021/N_VSA