Algorithms and Data Structures 2 - NTIN061

• Title: Algoritmy a datové struktury 2
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2020
• Semester: winter
• E-Credits: 5
• Hours per week, examination: winter s.:2/2, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech, English
• Teaching methods: full-time
• Guarantor: Mgr. Martin Mareš, Ph.D.; prof. RNDr. Ondřej Čepek, Ph.D.; doc. Mgr. Jan Hubička, Ph.D.
• Teacher(s): Mgr. Tomáš Domes; RNDr. Jiří Fink, Ph.D.; Mgr. Jelena Glišić; RNDr. Jan Hric; Bc. Filip Kastl; Mgr. Kate Konczycki; Mgr. Martin Koutecký, Ph.D.; RNDr. Petr Kučera, Ph.D.; Mgr. Vladan Majerech, Dr.; Mgr. Pavel Veselý, Ph.D.
• Class: Informatika Bc.
• Classification: Informatics > Theoretical Computer Science
• Incompatibility : NTIX061
• Interchangeability : NTIX061
• Is incompatible with: NTIX061
• Is interchangeable with: NTIX061
• In complex interchangeability with: NUIN021

Annotation

English

Lecture about various types of algorithms and their time complexity (follows NTIN060 Algorithms and data structures 1).

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

Czech

Přednáška o různých typech algoritmů a jejich časové složitosti (navazuje na NTIN060 Algoritmy a datové struktury 1).

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

Course completion requirements

Je třeba získat zápočet a složit zkoušku (v libovolném pořadí).

Pro zápočet je třeba získat 100 bodů z alespoň 150 možných udělovaných průběžně za řešení domácích úloh, písemné testy a další aktivity. Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů ani zadání náhradních domácích úloh.

V důvodných případech (dlouhodobá nemoc, pobyt v zahraničí, apod.) může cvičící stanovit individuální podmínky na udělení zápočtu.

Zkouška může být písemná, ústní nebo kombinovaná. Zkouška může mít kontaktní nebo distanční formu. Formu zkoušky určuje vyučující.

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

Literature

English

Aho, Hopcroft, Ullman : The design and analysis of computer algorithms, Addison-Wesley 1976

T.Cormen, Ch.Leiserson, R. Rivest, C. Stein : Introduction to Algorithms (2nd Edition), McGraw-Hill 2001

http://kam.mff.cuni.cz/~ludek

Last update: Hladík Milan, prof. Mgr., Ph.D. (22.11.2012)

Czech

A.Koubková, J.Pavelka : Úvod do teoretické informatiky, Matfyzpress 1999

Aho, Hopcroft, Ullman : The design and analysis of computer algorithms, Addison-Wesley 1976

T.Cormen, Ch.Leiserson, R. Rivest, C. Stein : Introduction to Algorithms (2nd Edition), McGraw-Hill 2001

L.Kučera : Kombinatorické algoritmy, SNTL Praha 1983

L.Kučera, J. Nešetřil : Algebraické metody diskretní matematiky, SNTL Praha 1989

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/

http://kam.mff.cuni.cz/~ludek

Last update: Hric Jan, RNDr. (03.10.2017)

Requirements to the exam

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

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

Syllabus

English

Optional topics in square brackets, the rest is mandatory.

1. Searching in text

• Knuth-Morris-Pratt algorithm

• Aho-Corasick algorithm

• [Rabin-Karp algorithm]

2. Flows in networks

• augmenting path algorithm

• Dinic's algorithm

• Goldberg's algorithm

• matching in bipartite graph

• [search for maximum flow of minimum price]

3. Algebraic algorithms

• discrete Fourier transformation, its motivation and application

• the FFT algorithm and its implementation by the "butterfly"

• [related transformations (cosine transformation - JPEG compression)]

4. Parallel arithmetic algorithms

• sorting networks (implementation of one sorting algorithm - either merge-sort or bitonic-sort)

• carry look-ahead algorithm for addition

5. Basic geometric algorithms in a plane

• convex hull

• the principle of plane sweeping driven by events

• [Voronoi diagram and Delaunay triangulation (Fortune's algorithm)]

6. Transferability of problems and classes of time complexity

• polynomial transformation and reduction between decision problems

• non-deterministic algorithms, Class P and NP

• NP-completeness

7. Approximation algorithms

• use of approximation algorithms, ratio and relative error

• one or two simple examples of approximation algorithms (knapsack, bin-packing, scheduling on parallel machines) including an upper estimate for their ratio (or relative) error

• approximation scheme: principle and example

8. Probabilistic algorithms and cryptography

• Monte Carlo algorithms (Rabin-Miller's Primality Test)

• public key cryptography (RSA algorithm)

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

Czech

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

1. Vyhledávání v textu

• algoritmus Knuth-Morris-Pratt

• algoritmus Aho-Corasicková

• [algoritmus Rabin-Karp]

2. Toky v sítích

• algoritmus zlepšující cesty

• Dinicův algoritmus

• Goldbergův algoritmus

• párování v bipartitním grafu

• [hledání maximálního toku minimální ceny]

3. Algebraické algoritmy

• diskrétní Fourierova transformace, její motivace a aplikace

• algoritmus FFT a jeho implementace obvodem „butterfly“

• [příbuzné transformace (kosinová - JPEG komprese)]

4. Paralelní aritmetické algoritmy

• třídící sítě (implementace jednoho třídícího algoritmu - buď merge-sort nebo bitonic-sort)

• carry look-ahead algoritmus pro sčítání čísel

5. Základní geometrické algoritmy v rovině

• konvexní obal

• princip zametání roviny řízeného událostmi

• [Voroného diagram a Delaunayova triangulace (Fortunův algoritmus)]

6. Převoditelnost problémů a třídy časové složitosti

• polynomiální transformace a redukce mezi rozhodovacími problémy

• nedeterministické algoritmy, třídy P a NP

• NP-úplnost

7. Aproximační algoritmy

• použití aproximačních algoritmů, poměrová a relativní chyba

• jeden až dva jednoduché příklady aproximačních algoritmů (knapsack, bin-packing, rozvrhování na paralelních strojích) včetně horního odhadu pro jejich poměrovou (nebo relativní) chybu

• aproximační schéma: princip a příklad

8. Pravděpodobnostní algoritmy a kryptografie

• algoritmy typu Monte Carlo (Rabinův-Millerův test prvočíselnosti)

• šifrování s veřejným klíčem (algoritmus RSA)

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