SubjectsSubjects(version: 953)
Course, academic year 2019/2020
Algorithms and Graphs 1 - B500008
Title: Algoritmy a grafy 1
Guaranteed by: CTU in Prague, Faculty of Information Technology (500)
Faculty: University of Chemistry and Technology, Prague
Actual: from 2019 to 2019
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 [HT]
Capacity: unknown / unknown (unknown)
Min. number of students: unlimited
State of the course: not taught
Language: Czech
Teaching methods: full-time
Teaching methods: full-time
Guarantor: Tvrdík Pavel prof. Ing. CSc.
Valla Tomáš RNDr. Ph.D.
Interchangeability : N500015
Examination dates   Schedule   
Annotation -
The course covers the basic principles of creating efficient algorithms, data structures and graph theory that every computing expert should know.
Last update: Svozil Daniel (04.01.2019)
Aim of the course -

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
Last update: Kubová Petra (02.01.2018)
Literature -

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.

Last update: Kubová Petra (02.01.2018)
Syllabus -

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

Last update: Svozil Daniel (04.01.2019)
Registration requirements -

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.

Last update: Kubová Petra (02.01.2018)
Course completion requirements - Czech

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.

Last update: Svozil Daniel (07.02.2018)
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
Coursework assessment
Form Significance
Examination test 70
Continuous assessment of study performance and course -credit tests 30