Algorithms and Graphs 1 - B500008
Title: Algoritmy a grafy 1
Guaranteed by: CTU in Prague, Faculty of Information Technology (500)
Actual: from 2020
Semester: winter
Points: winter s.:6
E-Credits: winter s.:6
Examination process: winter s.:
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unlimited / unlimited (unknown)
Min. number of students: unlimited
Language: Czech
Teaching methods: full-time
For type: Bachelor's
Guarantor: Tvrdík Pavel prof. Ing. CSc.
Valla Tomáš RNDr. Ph.D.
Interchangeability : N500015
Examination dates   
Annotation -
Last update: Svozil Daniel doc. Mgr. Ph.D. (04.01.2019)
The course covers the basic principles of creating efficient algorithms, data structures and graph theory that every computing expert should know.
Aim of the course -
Last update: Kubová Petra Ing. (02.01.2018)

Students will be able to:

  • Understand a set of well-known standard algorithms
  • Recognize a proper algorithm variant for any specific usage
  • Use learn basic methods of algorithm analysis to be used as a main efficiency criterion
Literature -
Last update: Kubová Petra Ing. (02.01.2018)

R:Cormen, T. H., Leiserson, C. E., Rivest, R. L. Introduction to Algorithms. The MIT Press, 2001. ISBN 0262032937.

R:Handbook of Graph Theory, 2nd Edition (Discrete Mathematics and Its Applications). Chapman and Hall/CRC, 2013. ISBN 978-1439880180.

Syllabus -
Last update: Svozil Daniel doc. Mgr. Ph.D. (04.01.2019)

1. Motivation and introduction to graph theory

2. Basic definitions and concepts of graph theory I

3. Basic definitions and concepts of graph theory II

4. Sorting algorithms O(n^2). Binary heaps and HeapSort.

5. Dynamic fields, amortized complexity, binomial heaps

6. Search trees and their balancing

7. Probabilistic algorithms and their complexity. QuickSort.

8. Recursive algorithms and divide and conquer. Linear sorting

9. Hashing and searching tables

10. Dynamic programming

11. Graph minimum spanning tree

12. Shortest paths in graphs

13. Reserve

Registration requirements -
Last update: Kubová Petra Ing. (02.01.2018)

An ability to solve basic algorithmic problems actively, to express the algorithmic solution in a high-level programming language (Java, C++), and knowledge of basic notions from calculus and combinatorics is assumed.

Course completion requirements - Czech
Last update: Svozil Daniel doc. Mgr. Ph.D. (07.02.2018)

Pro zı́skánı́ zápočtu je potřeba dostatek bodů ze semestrálního testu a z programovacích úloh. Zkouška se skládá z povinné pı́semné části a z volitelné ústnı́ části.

Teaching methods
Activity Credits Hours
Konzultace s vyučujícími 1 28
Účast na přednáškách 1 28
Práce na individuálním projektu 2 56
Příprava na zkoušku a její absolvování 1 28
Účast na seminářích 1 28
6 / 6 168 / 168