Algorithms and datastructures II (NTIN061)

Jan Hubička,

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

Topics covered

Mon Oct 05 2020
Welcome; string-searching (KMP algorithm). slides, recorded lecture, Wikipedia,
Donald Knuth on the algorithm.
Mon Oct 12 2020
string searching (Aho-Corasick) slides, recorded lecture, Wikipedia,
Alfred Aho lectures on Unix and on algorithms from Bell labs (he mentions automatons).
Mon Oct 19 2020
Network flows (Ford-Fulkerson, Dinic) slides, recorded lecture
Mon Oct 26 2020
Network flows (Goldberg) slides, recorded lecture, Goldberg algorithm
Mon Nov 2 2020
Parallel algorithms: boolean circuits, addition slides, recorded lecture
Mon Nov 9 2020
Parallel algorithms: bitonic sort slides, recorded lecture, sound of sorting
Mon Nov 16 2020
Fourier analysis: FFT algorithm and multiplication of polynomials slides, recorded lecture
Mon Nov 23 2020
Fourier analysis: parallel implementation, non-recursive implementation, FFT on real vectors. Selected applications (spectral analysis, DCT) will not be required for exam. Slides, recorded lecture. A visual introduction to Fourier transform, History of FFT with Cooley and Tukey
Mon Nov 30 2020
Introduction to complexity theory slides, recorded lecture.
Mon Dec 7 2020
NP completeness, Cook theorem slides, recorded lecture.
Mon Dec 14 2020
Approximation algorithms slides, recorded lecture..
Mon Dec 21 2020
Geometric algorithms: convex hull and reduction from sorting, vornoi diagrams slides, recorded lecture.
Mon Jan 4 2021
Randomised algorithms (Monte-carlo), Rabin's algorithm, cryptography (RSA). slides, recoded lecture.