Algorithms and Data Structures 1 - NTIN060

• Title in English: Algoritmy a datové struktury 1
• Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2019
• Semester: summer
• E-Credits: 5
• Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
• Capacity: unlimited
• Min. number of students: unlimited
• State of the course: taught
• Language: Czech, English
• Teaching methods: full-time
• Guarantor: Mgr. Jan Hubička, Ph.D.; Mgr. Martin Mareš, Ph.D.; RNDr. Jan Hric
• Class: Informatika Bc.
• Classification: Informatics > Theoretical Computer Science

Annotation

English

Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)

Introductory lecture on the basic types of algorithms and data structures necessary for their implementation. It follows the lecture NPRG062 Algorithmization in the previous semester.

Czech

Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci. Navazuje na výklad v přednášce NPRG062 Algoritmizace v předchozím semestru.

Aim of the course

Last update: T_KTI (23.05.2008)

Naučit základní datové struktury, algoritmy a metody teoretické informatiky

Course completion requirements

English

Last update: Mgr. Martin Mareš, Ph.D. (04.03.2018)

It is necessary to get course credit and pass the examination (in arbitrary order). Credit is given for solving homeworks, including potential additional homeworks at the end of the semester. The nature of this requirement excludes the possibility of repeated attempts to get credit, which means that if you do not obtain enough points for homeworks, there is no other way how to get credit.

The examination consists of a written and oral part. The written part precedes the oral part, a failure in the written part implies failing the whole exam, so the oral part is skipped in such cases.

Czech

Last update: Mgr. Martin Mareš, Ph.D. (04.03.2018)

Je třeba získat zápočet a složit zkoušku (v libovolném pořadí). Zápočet se uděluje za řešení domácích úkolů a případných dodatečných úkolů na konci semestru. Povaha kontroly podmínek k udělení zápočtu vylučuje možnost jejího opakování, což znamená, že když nenasbíráte dostatek bodů, zápočet nelze získat jinak.

Zkouška se skládá z písemné a ústní části. Písemná část předchází části ústní, její nesplnění znamená, že termín zkoušky je hodnocen známkou nevyhověl(a) a ústní částí se již nepokračuje.

Literature

Last update: RNDr. Jan Hric (03.10.2017)

• Cormen, Leiserson, Rivest, Stein : Introduction to algorithms (2nd Edition), Mc Graw Hill 2001
• M.Mareš, T.Valla : Průvodce labyrintem algoritmů, CZ.NIC z.s.p.o. Praha 2017, 978-80-88168-19-5, http://pruvodce.ucw.cz/
• Videozáznamy přednášek

Requirements to the exam

English

Last update: Mgr. Martin Mareš, Ph.D. (02.03.2018)

It is necessary to understand the theory presented at the lectures and to be able to apply it to solving of algorithmic problems.

Czech

Last update: Mgr. Martin Mareš, Ph.D. (02.03.2018)

Je třeba rozumět teorii z přednášky a být schopen ji aplikovat na řešení algoritmických úloh.

Syllabus

English

Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)

Optional topics in square brackets, the rest is mandatory.

1. Means for describing the complexity of algorithms and operations with data structures

• measurement of data size, number of algorithm steps as a function of data size

• RAM computational model

• asymptotic notation

2. Tree data structures

• binary search trees

• AVL trees

• (a,b)-trees

• [red-black trees]

3. Hashing

• a description of simple collision resolution strategies

• analysis of the average time complexity of the search

• universal hashing

4. Sorting

• average case analysis for Quicksort, Randomized Quicksort

• lower bound on the complexity of comparison sorting algorithms (decision trees)

5. Basic graph algorithms

• depth-first search on an undirected graph, detection of bridges and articulations

• depth-first search on a directed graph, transitive closure, topological numbering

• [detection of components of strong connectivity in linear time]

6. Extreme paths in graphs

• extreme paths in a directed acyclic graph, the critical path method

• Dijkstra's algorithm (refresher of binary heaps, comparison of implementation using an array and a binary heap)

• Bellman-Ford's algorithm (looking for negative cycles)

• [Floyd-Warshall's algorithm]

7. Minimum spanning tree

• Jarník's and Borůvka's algorithm

• [Kruskal's algorithm and data structure for Union-Find]

8. Divide and conquer method

• general schema of divide and conquer algorithms, describing their complexity by recurrent equations

• substitution method for recurrent equations and "master theorem (cook-book)"

• simple applications: binary search, Merge sort, multiplication of numbers (Karatsuba-Ofman)

• more complex applications: Strassen's multiplication of matrices, [median search in linear time in the worst case]

9. Dynamic programming

• general principle of dynamic programming

• edit-distance of strings

• [optimal search trees]

Czech

Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)

Volitelná témata v hranatých závorkách, zbytek je povinný.

1. Prostředky pro popis složitosti algoritmů a operací nad datovými strukturami

• měření velikosti dat, počet kroků algoritmu jako funkce velikosti dat

• výpočetní model RAM

• asymptotická notace

2. Stromové datové struktury

• binární vyhledávací stromy

• AVL stromy

• (a,b)-stromy

• [červeno-černé stromy]

3. Hešování

• popis jednoduchých strategií řešení kolizí

• analýza průměrné časové složitosti vyhledávání

• univerzální hešování

4. Třídění

• analýza průměrného případu pro Quicksort, randomizovaný Quicksort

• dolní odhad složitosti porovnávacích třídících algoritmů (rozhodovací stromy)

5. Základní grafové algoritmy

• prohledávání do hloubky na neorientovaném grafu, detekce mostů a artikulací

• prohledávání do hloubky na orientovaném grafu, tranzitivní uzávěr, topologické číslování

[detekce komponent silné souvislosti v lineárním čase]

6. Extremální cesty v grafech

• extremální cesty v acyklickém orientovaném grafu, metoda kritické cesty

• Dijkstrův algoritmus (zopakování binární haldy, srovnání implementace polem a binární haldou)

• Bellmanův-Fordův algoritmus (hledání záporných cyklů)

• [Floydův-Warshallův algoritmus]

7. Minimální kostra grafu

• Jarníkův a Borůvkův algoritmus

• [Kruskalův algoritmus a datová struktura pro Union-Find]

8. Metoda rozděl a panuj

• obecné schéma algoritmů typu rozděl a panuj, souvislost jejich složitosti s rekurentními rovnicemi

• substituční metoda řešení rekurentních rovnic a „master theorem (kuchařka)“

• jednoduché aplikace: binární vyhledávání, Merge sort, násobení čísel (Karatsuba-Ofman)

• složitější aplikace: Strassenovo násobení matic, [hledání mediánu v lin. čase v nejhorším případě]

9. Dynamické programování

• obecný princip dynamického programování

• editační vzdálenost řetězců

• [optimální vyhledávací stromy]