Course: Algorithms for Hard Problems

» List of faculties » PRF » KMI
Course title Algorithms for Hard Problems
Course code KMI/ALS2
Organizational form of instruction Lecture + Exercise
Level of course Master
Year of study not specified
Semester Summer
Number of ECTS credits 5
Language of instruction Czech
Status of course Compulsory, Compulsory-optional
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Lecturer(s)
  • Juračka Jakub, Mgr.
  • Osička Petr, Mgr. Ph.D.
  • Jančar Petr, prof. RNDr. CSc.
Course content
The course provides introduction to hard problems, particularly algorithms for hard problems and related parts of computational complexity theory. " Approximate solutions to hard problems " Complexity of optimization problems " Approximation algorithms for selected hard problems, design techniques " Approximation classes " Linear programming " Randomized algorithms

Learning activities and teaching methods
Lecture, Demonstration
Learning outcomes
The students become familiar with advanced concepts of algorithms and complexity.
2. Comprehension: Classify hard problems
Prerequisites
unspecified

Assessment methods and criteria
Oral exam, Written exam

Active participation in class. Completion of assigned homeworks. Passing the oral (or written) exam.
Recommended literature
  • Arora S., Barak B. (2009). Computational Complexity: A Modern Approach.. Cambridge University Press.
  • Ausiello G. et al. (1999). Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties. Springer, Berlin.
  • Hromkovič J. (2003). Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. 2nd Edition. Springer.
  • Korte B., Vygen J. (2018). Combinatorial Optimization (Theory and Algorithms). Springer.
  • Lee J. (2004). A First Course in Combinatorial Optimization. Cambridge Univ. Press.
  • Matoušek J., Nešetřil J. (2010). Kapitoly z diskrétní matematiky. Praha, Karolinum.


Study plans that include the course
Faculty Study plan (Version) Category of Branch/Specialization Recommended year of study Recommended semester
Faculty: Faculty of Science Study plan (Version): Computer Science - Specialization in Artificial Intelligence (2020) Category: Informatics courses 1 Recommended year of study:1, Recommended semester: Summer
Faculty: Faculty of Science Study plan (Version): Applied Computer Science - Specialization in Software Development (2024) Category: Informatics courses 1 Recommended year of study:1, Recommended semester: Summer
Faculty: Faculty of Science Study plan (Version): Bioinformatics (2021) Category: Informatics courses 1 Recommended year of study:1, Recommended semester: Summer
Faculty: Faculty of Science Study plan (Version): Computer Science - Specialization in General Computer Science (2020) Category: Informatics courses 1 Recommended year of study:1, Recommended semester: Summer
Faculty: Faculty of Science Study plan (Version): Teaching Training in Computer Science for Secondary Schools (2019) Category: Pedagogy, teacher training and social care 1 Recommended year of study:1, Recommended semester: Summer
Faculty: Faculty of Science Study plan (Version): Applied Computer Science - Specialization in Computer Systems and Technologies (2024) Category: Informatics courses 1 Recommended year of study:1, Recommended semester: Summer