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

Studenti budou umět:

• budou mít důkladný přehled efektivních algoritmů pro řešení standardních problémů.

• pracovat s asymptotickou notací používanou při vyjadřování složitosti.

• budou rozumět algoritmům pro řazení o složitosti O(n.log n), pro speciální řazení s lineární složitostí a pro řazení ve vnějších pamětech, algoritmům asociativního a adresního vyhledávání (vyhledávací stromy, rozptýlené tabulky, vícerozměrné vyhledávací stromy).

• znát a používat pokročilé datové struktury.

• ovládat metody používané pro analýzu paměťové a operační složitosti algoritmů.

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.

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.

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

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

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

Osnovy přednášek:

1. Motivace a úvod do teorie grafů

2. Základní definice a pojmy teorie grafů I 3. Základní definice a pojmy teorie grafů II

4. Řadící algoritmy O(n^2). Binární haldy a HeapSort.

5. Nafukovací pole, amortizovaná složitost, binomiální haldy

6. Vyhledávací stromy a jejich vyvažování

7. Pravděpodobnostní algoritmy a jejich složitost. QuickSort.

8. Rekurzivní algoritmy a metoda Rozděl a panuj. Lineární řazení

9. Rozptylování (hešování) a vyhledávací tabulky

10. Dynamické programování

11. Minimální kostry grafu

12. Nejkratší cesty v grafech

13. Rezerva

Osnovy cvičení:

1. Motivace a úvod do teorie grafů

2. Základní definice a pojmy teorie grafů I 3. Základní definice a pojmy teorie grafů II

4. Řadící algoritmy O(n^2). Binární haldy a HeapSort.

5. Nafukovací pole, amortizovaná složitost, binomiální haldy

6. Vyhledávací stromy a jejich vyvažování

7. Pravděpodobnostní algoritmy a jejich složitost. QuickSort.

8. Rekurzivní algoritmy a metoda Rozděl a panuj. Lineární řazení

9. Rozptylování (hešování) a vyhledávací tabulky

10. Dynamické programování

11. Minimální kostry grafu

12. Nejkratší cesty v grafech

13. Rezerva

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.

Předpokládá se schopnost aktivního algoritmického řešení základních typů úloh, znalost nějakého vyššího programovacího jazyka (Java, C++) a znalost základních pojmů z matematické analýzy a kombinatoriky.