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

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
Vztahy:
In order to register for the course BI-AVI.21, the student must have successfully completed the course BI-PA1 in a previous semester.
In order to register for the course BI-AVI.21, the student must have registered for the course BI-PA2 in a previous semester.
Garant předmětu:
Luděk Kučera
Lecturer:
Luděk Kučera
Tutor:
Luděk Kučera
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 2023/2024:
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
roomT9:348
Kučera L.
10:00–11:45
(lecture parallel1)
Dejvice
NBFIT PC ucebna
roomT9:348
Kučera L.
11:45–12:30
(lecture parallel1
parallel nr.101)

Dejvice
NBFIT PC ucebna
Tue
Wed
Thu
Fri
Time-table for summer semester 2023/2024:
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
roomTH:A-1247
Kučera L.
09:15–10:45
(lecture parallel1)
Thákurova 7 (budova FSv)
seminární místnost
roomTH:A-1247
Kučera L.
11:00–11:45
(lecture parallel1
parallel nr.101)

Thákurova 7 (budova FSv)
seminární místnost
Thu
Fri
The course is a part of the following study plans:
Data valid to 2024-07-13
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet6290306.html