Algorithms visually
| Code | Completion | Credits | Range | Language |
|---|---|---|---|---|
| BI-AVI.21 | Z,ZK | 4 | 2P+1C | Czech |
- 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 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 Thu Fri - The course is a part of the following study plans:
-
- Bachelor program Informatics, unspecified branch, in Czech, 2015-2020 (elective course)
- Bachelor branch Security and Information Technology, in Czech, 2015-2020 (elective course)
- Bachelor branch Computer Science, in Czech, 2015-2020 (elective course)
- Bachelor branch Computer Engineering, in Czech, 2015-2020 (elective course)
- Bachelor branch Information Systems and Management, in Czech, 2015-2020 (elective course)
- Bachelor branch Web and Software Engineering, spec. Software Engineering, in Czech, 2015-2020 (elective course)
- Bachelor branch Web and Software Engineering, spec. Web Engineering, in Czech, 2015-2020 (elective course)
- Bachelor branch Web and Software Engineering, spec. Computer Graphics, in Czech, 2015-2020 (elective course)
- Bachelor branch Knowledge Engineering, in Czech, 2018-2020 (elective course)
- Bachelor specialization Information Security, in Czech, 2021 (elective course)
- Bachelor specialization Management Informatics, in Czech, 2021 (elective course)
- Bachelor specialization Computer Graphics, in Czech, 2021 (elective course)
- Bachelor specialization Computer Engineering, in Czech, 2021 (elective course)
- Bachelor program, unspecified specialization, in Czech, 2021 (elective course)
- Bachelor specialization Web Engineering, in Czech, 2021 (elective course)
- Bachelor specialization Artificial Intelligence, in Czech, 2021 (elective course)
- Bachelor specialization Computer Science, in Czech, 2021 (elective course)
- Bachelor specialization Software Engineering, in Czech, 2021 (elective course)
- Bachelor specialization Computer Systems and Virtualization, in Czech, 2021 (elective course)
- Bachelor specialization Computer Networks and Internet, in Czech, 2021 (elective course)
- Study plan for Ukrainian refugees (elective course)