Algorithms and datastructures II (NTIN061)
Consultations by email arrangement. Use ADS2020 in subjects of emails.
- Lecture: Mon 9:00, zoom (943 9157 1202, ADSfun)
- practicals: Pankaj Kumar via zoom
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.
Literature