B_ADS Algorithms and Data Structures

University of Finance and Administration
Summer 2025
Extent and Intensity
2/2. 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
There are no prerequisites for this course.
Course Enrolment Limitations
The course is offered to students of any study field.
Course objectives
The objective of the course is to give students an overview of common types of algorithms and to familiarize them with the theory of computational complexity.
The students will understand different types of algorithms (sequential and parallel, deterministic and probabilistic, optimization and approximation). Each type is explained with examples of specific algorithms. An emphasis is given to an analysis of their time complexity. The lecture also covers an introduction to computational complexity: classes P and NP are introduced, polynomial reducibility for decision problems defined, and the methodology of NP-completeness proofs explained.
Learning outcomes
After finishing this course students will be capable of:
- designing and efficient implementation of simple polynomial time algorithms
- designing data structures for an efficient implementation of simple polynomial time algorithms
- analyzing the time and space complexity of concrete algorithms with polynomial complexity;
- recognizing computationally intractable problems.
Syllabus
  • This curriculum is designed for full-time study, course of instruction for part-time study is given in the study material in the form of methodological sheets (ML).
  • 1st lecture Overview of concept definitions, data structures, resources to describe the complexity of algorithms, an example of calculating the complexity of the algorithm.
  • 2nd lecture Complexity of arithmetic operations, simple sorting algorithms, complex sorting algorithms.
  • 3rd lecture Search in text using finite automata: Aho-Corasick algorithm and its analysis.
  • 4th lecture Algorithms divide and conquer, solving recurrent equations, search in the median in linear time, Strassen's algorithm for matrix multiplication.
  • 5th lecture Sets Definition, Graphs Definition.
  • 6th lecture BFS graph algorithms (breadth search), DFS graph algorithms (depth-first search), graph context testing., graph algorithms - search for two-contiguous components of a non-oriented graph..
  • 7th lecture Graph algorithms (continuation): topological sorting, detection of strongly contiguous components of a oriented graph.
  • 8th lecture Tree structures, decision trees
  • 9th lecture Parallel algorithms - multiplication of nuts on an abstract parallel PRAM machine, testing the touchability in the graph.
  • 10th lecture Parallel algorithms (continuation): transposition and sorting networks.
  • 11th lecture Problems that can be solved deterministically in polynomial time (Class P) , problems solvable nondeterministically in polynomial time (Class NP), NP-complete problems, polynomial transferability.
  • 12th lecture Approximation algorithms.
Literature
  • Povinná literatura
  • A.Koubková, J.Pavelka: Úvod do teoretické informatiky, Matfyzpress 1998 (aktualizované vydání 2003), ISBN: 80-85863-33-2
  • Doporučená literatura
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd. Ed., MIT Press/McGraw Hill, 2001. ISBN: 0-262-03293-7
  • Další zdroje
  • www.vsfs.cz/knihovna
  • www.knihovna.vsfs.cz/info/volne_eiz.html
Teaching methods
Type of teaching: Teaching consists of lectures and exercises in   full time and managed through group consultations in   combined studies.
The scope of compulsory participation in education: Minimum mandatory participation in exercises in full-time is   75%, the controlled group consultations in   50% of the combined studies. Students who fail to meet mandatory scope of participation, may be given during the semester   additional study obligations (to the extent that will demonstrate academic achievement and acquired competencies necessary for successful completion of course).
Assessment methods
Course completion: The course is concluded with a credit and examination. The test is in written form and the writing is available for   90 minutes. Credit certifying fulfillment of the course requirements.
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: 14 hodin KS/semestr.
Teacher's information
http://kti.mff.cuni.cz/~cepek/vyuka.html
The course is also listed under the following terms Winter 2007, Summer 2008, Winter 2008, Summer 2009, Summer 2010, Summer 2011, summer 2012, Summer 2013, Summer 2014, Summer 2015, Summer 2016, Summer 2017, Summer 2018, Summer 2019, Summer 2020, Summer 2021, Summer 2022, Summer 2023, Summer 2024.
  • Enrolment Statistics (recent)
  • Permalink: https://is.vsfs.cz/course/vsfs/summer2025/B_ADS