SubjectsSubjects(version: 804)
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
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

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


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 |