Algorithms and datastructures I (NTIN060)

Webpage moved to Moodle

Jan Hubička, hubicka@kam.mff.cuni.cz

Consultations by email arrangement. Use ADS2020 in subjects of emails.

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
Tue Mar 30 2020
Slides
Tue Apr 7 2020
Slides

Practicals

Thu Feb 20 2020
Random Access Machine. Determining time and space complexity. handout.
Thu Feb 27 2020
Graph algorithms (BFS and DFS). handout, homework 1.
Thu Mar 5 2020
Graph algorithms (DFS applications). handout.
Thu Feb 12 2020
Class cancelled (due to government regulations). Here are excercises and new homework for individual study.

Solutions were also partly discussed at Feb 29.

Thu Feb 19 2020
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.

Links