SubjectsSubjects(version: 807)
Course, academic year 2017/2018
   Login via CAS
Algorithms and Data Structures II - NTIN061
Czech title: Algoritmy a datové struktury II
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017
Semester: winter
E-Credits: 6
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: RNDr. Jan Hric
Mgr. Martin Mareš, Ph.D.
Class: Informatika Bc.
Classification: Informatics > Theoretical Computer Science
Annotation -
Last update: G_I (24.05.2004)

Continuation of TIN060 Algorithms and data structures I
Terms of passing the course - Czech
Last update: RNDr. Jan Hric (12.10.2017)

Je třeba získat zápočet a složit zkoušku. Získání zápočtu je nutnou podmínkou pro absolvování zkoušky s výjimkou případných předtermínů. 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: T_KAM (20.04.2008)

Searching in text:

Algorithms Aho-Corasick, Knuth-Morris-Pratt, optionally Rabin-Karp

Network flows

Augmenting path algorithms (Ford-Fulkerson),

Dinic's and Goldberg's algorithm

Optionally finding maximum flow of minimum cost and bipartite matchings

Algebraic algorithms

Discrete Fourier transform, its motivation and applications

FFT algorithm (Fast Fourier Transform) and its implementation as "butterfly" circuits

Optionally related transforms (DCT -- JPEG compression)

Parallel arithmetic algorithms

Sorting networks (merge-sort or bitonic sort)

Addition of binary numbers -- carry look-ahead

Optionally the Karatsuba-Ofman algorithm for multiplication

Basic algorithms of planar geometry

Convex hull

Voronoi diagram and Delaunay triangulation (Fortune's algorithm)

Reducibility of problems and classes of time complexity:

Polynomial transformations and reductions between decision problems

Non-deterministic algorithms, classes P and NP

NP-completeness

Approximation algorithms

Use of approximation algorithms, relative errors

Examples of approximation algorithms: e.g., knapsack, bin packing, scheduling on parallel machines, including upper bounds of approximation errors

Probabilistic algorithms and cryptography

Monte Carlo algorithms (Rabin-Miller primality test)

Public key cryptography (RSA cryptosystem)

Optionally DES and similar cryptographic algorithms and protocols

Dynamic programming

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