Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2022/2023

Algorithms visually

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
BI-AVI.21 Z,ZK 4 2P+1C Czech
Enrollement in the course requires an successful completion of the following courses:
Programming and Algorithmics 1 (BI-PA1)
Prerequisite:
Programming and Algorithmics 2 (BI-PA2)
Lecturer:
Luděk Kučera (guarantor)
Tutor:
Luděk Kučera (guarantor)
Supervisor:
Department of Theoretical Computer Science
Synopsis:

The course complements other algorithm courses at FIT. It brings knowledge about particular important algorithms from different fields of the computer science that extend substantially knowledge presented in BI-AG1 and BI-AG2. A wide scope of covered subject is made possible due to using visualization bz Algovision (www.algovision.org<http://www.algovision.org>) that make understanding the principles of algorithms easy.

Requirements:

There are no input knowledge requirements.

Syllabus of lectures:

1. Tree data structures (general methods and algorithms that are not included in AG1 and AG2, e.g., red-black trees)

2. Shortest paths (algorithm invariant view of Dijkstra and Bellman-Ford algorithms)

3. Efficient network flow algorithms - augmenting path methods (Dinitz and 3 Indiens)

4. Efficient network flow algorithms - preflow methods (Goldberg)

5. Discrete Fourier transform, cosine transform and the FFT algorithm

6. Binary number addition algorithms (Kogge-Stone, Ladner-Fischer, Brent-Kung)

7. Geometric algorithms (convex hull, Voronoi diagram - Fortune)

8. Sorting and switching networks (bitonic sort, odd-even sort)

9. Conjugated gradients method

10. Eigenvector and eigenvalue applications (graph min-cut spectral algorithm)

11. Linear programming (simplex method and duality)

12. Quantum algorithms (basic notions - qubit, entanglement)

13. Quantum algorithms (Algorithms of Groover and Simon with a light outline of Shor factorization)

Syllabus of tutorials:

1. Tree data structures (general methods and algorithms that are not included in AG1 and AG2, e.g., red-black trees)

2. Shortest paths (algorithm invariant view of Dijkstra and Bellman-Ford algorithms)

3. Efficient network flow algorithms - augmenting path methods (Dinitz and 3 Indiens)

4. Efficient network flow algorithms - preflow methods (Goldberg)

5. Discrete Fourier transform, cosine transform and the FFT algorithm

6. Binary number addition algorithms (Kogge-Stone, Ladner-Fischer, Brent-Kung)

7. Geometric algorithms (convex hull, Voronoi diagram - Fortune)

8. Sorting and switching networks (bitonic sort, odd-even sort)

9. Conjugated gradients method

10. Eigenvector and eigenvalue applications (graph min-cut spectral algorithm)

11. Linear programming (simplex method and duality)

12. Quantum algorithms (basic notions - qubit, entanglement)

13. Quantum algorithms (Algorithms of Groover and Simon with a light outline of Shor factorization)

Study Objective:
Study materials:

1. L. Kučera: Algovize, aneb procházka krajinou algoritmů, Blatenská tiskárna, 2009, ISBN 8090293859, 9788090293854. Dostupné z http://www.algovision.org

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, MIT Press, 1990, 2009, ISBN 978-0-262-03384-8

3. B. Barak, S. Arora: Computational Complexity: A Modern Approach, 2007, Cambridge Univ. Press, ISBN 978-0521424264

Note:
Further information:
http://www.algovision.org/FIT-BI-AVI.html
Time-table for winter semester 2022/2023:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
roomT9:351
Kučera L.
14:30–16:00
(lecture parallel1)
Dejvice
NBFIT PC ucebna
roomT9:351
Kučera L.
16:15–17:00
(lecture parallel1
parallel nr.101)

Dejvice
NBFIT PC ucebna
Wed
Thu
Fri
Time-table for summer semester 2022/2023:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
Wed
roomT9:346
Kučera L.
09:15–10:45
(lecture parallel1)
Dejvice
NBFIT učebna
roomT9:346
Kučera L.
11:00–11:45
(lecture parallel1
parallel nr.101)

Dejvice
NBFIT učebna
Thu
Fri
The course is a part of the following study plans:
Data valid to 2023-01-28
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet6290306.html