Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

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
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.
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

Opinion survey results Examination dates WS schedule Noticeboard

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: doc. Mgr. Jan Hubička, Ph.D. (24.09.2020)

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.

Zkouška může mít kontaktní nebo distanční formu.

Literature -

Last update: prof. 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)