N_VSA Algorithmic Complexity

University of Finance and Administration
Winter 2023
Extent and Intensity
2/1/0. 6 credit(s). Type of Completion: zk (examination).
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á
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
The course is also listed under the following terms Winter 2014, Winter 2015, Winter 2016, Winter 2017, Winter 2018, Winter 2019, Winter 2020, Winter 2021, Winter 2022.
  • Enrolment Statistics (recent)
  • Permalink: https://is.vsfs.cz/course/vsfs/winter2023/N_VSA