SubjectsSubjects(version: 875)
Course, academic year 2020/2021
  
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 [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: Mgr. Martin Mareš, Ph.D.
doc. RNDr. Ondřej Čepek, Ph.D.
Mgr. Jan Hubička, Ph.D.
Class: Informatika Bc.
Classification: Informatics > Theoretical Computer Science
Incompatibility : NTIX061
Interchangeability : NTIX061
Annotation -
Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)
Lecture about various types of algorithms and their time complexity (follows NTIN060 Algorithms and data structures 1).
Course completion requirements - Czech
Last update: Mgr. Martin Mareš, Ph.D. (16.10.2018)

Je třeba získat zápočet a složit zkoušku. Získání zápočtu není podmínkou pro absolvování zkoušky. Zápočet se uděluje za kombinaci účasti a aktivity na cvičení, řešení domácích úkolů a zápočtových písemek. Povaha kontroly na zápočet vylučuje možnost jejího opakování.

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: doc. Mgr. Milan Hladík, Ph.D. (22.11.2012)

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

Requirements to the exam - Czech
Last update: Mgr. Martin Mareš, Ph.D. (11.10.2017)

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

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

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)

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html