SubjectsSubjects(version: 837)
Course, academic year 2018/2019
   Login via CAS
Extension seminar Algorithms and Data Structures II - NTIN108
Title in English: Rozšiřující seminář Algoritmy a datové struktury II
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:0/2 C [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: prof. RNDr. Luděk Kučera, DrSc.
Class: Informatika Bc.
Classification: Informatics > Theoretical Computer Science
Annotation -
Last update: Mgr. Jan Kynčl, Ph.D. (21.05.2018)
The course is a continuation of NTIN061 Algorithms and Data Structures II; algorithms taught in ADS II are shown under a different point of view and the course is directed to a detailed illustration of underlzing algorithmic ideas. Algorithms are presented using visualizations that are created so that the ideas are presented visually and algorithm invariants are visualized. The goal is to present algorithms as a creative part of the computer science and to teach students to think about the behavior and properties of algorithms in an exact way.
Literature -
Last update: Mgr. Jan Kynčl, Ph.D. (21.05.2018)

1. Visualizations are available at www.algovision.org, a web browser (Chrome, Mozilla) and pdf reader (e.g., Adobe Acrobat) suffice

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

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

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

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

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

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

Syllabus -
Last update: Mgr. Jan Kynčl, Ph.D. (21.05.2018)

Network flows: Fast implementations of Ford-Fulkerson algorithm (Dinitz a 3 Indiens) a Goldberg algorithm.

Arithmetic a algebraic algorithms: binary number addition (general method a implementations Kogge-Stone, Brent-Kung, Ladner-Fisher, Han-Carlson), Discrete Fourier transform (motivation and FFT algorithm).

Geometric algorithms: convex hull and Voronoi diagram (both in the plane)

String matching: Algorithm Knuth-Morris-Pratt and its generalization Aho-Corasick.

Simplex algorithm of linear programmming.

Detailed syllabus

1. Network flows - Dinitz algorithm.

2. Network flows - 3 Indien algorithm.

3. Network flows - Goldberg algorithm.

4. Binary number addition (general method a implementations Kogge-Stone, Brent-Kung, Ladner-Fisher, Han-Carlson).

5. Discrete Fourier transform - motivation.

6. Discrete Fourier transform - FFT algorithm.

7. Convex hull of a finite subset of the plane.

8. Voronoi diagram in the plane.

9. Voronoi diagram in the plane - cont'd.

10 String matching: Algorithm Knuth-Morris-Pratt.

11.String matching: Algorithm Aho-Corasick.

12. Simplex algorithm of linear programmming.

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