Consultations by email arrangement. Use ADS2020 in subjects of emails.
Lecture: Tue 12:20, S9
Practicals: In English Thu 10:40, T10. The lectures will be synchronized with parallel Czech lectures and thus it is possible to visit other practicals in Czech language.
Topics covered
Mon Feb 17 2020
What is an algorithm? Random Access Machine (RAM) as the model of computation. Time and space complexity. Analysis of selectsoft. Notation O(f), Ω(f), Θ(f).
Tue Feb 18 2020
Graph algorithms: Breadth-first search: review from last semmester; basic
properties with proofs. Depth-first search: algorithm, classification of edges
in a directed graph.
Tue Feb 25 2020
DFS classification on undirected graphs. Discovering bridges. Directed acyclic graphs.
Tue Mar 3 2020
Linear algebra by Jirka Fiala (replacing the class from Mon Feb 17)
Tue Mar 10 2020
Topological sorting and strongly connected components (the variant of algorithm I presented is known as Kosaraju–Sharir algorithm). You may also look as Tarjan's algorithm which is, in a way, more similar to algorithm for discovering bridges and is also more commonly implemented because it has additional useful properties.
Tue Mar 17 2020
Shortest paths in labelled graphs and Dijsktra's algorithm. Because school was closed, this class was done in form of lecture notes for self-study.
Next class is planned to take on-line form using Zoom.
Tue Mar 24 2020
Shortest paths with negative edges: Bellman-Ford, Floyd-Washall. Minimum spaning tree algorithms (Jarník, Borůvka, Kruskal). First online lecture broadcast by zoom. Slides, Video
First online class using zoom and bitaper. You should have received passwords by email. Please review Excercises in advance. I would welcome volunteers who will try to present solutions for this and past excercises.
Thu Feb 26 2020
Online using zoom and bitaper. You should have received passwords by email. Please review Excercises in advance.