Lectures ADS 2
Winter term 2019/20, Mon 10:40 S10
English lectures will be synchronized with Czech lectures regarding order of topics.
Slides (actual version) at: http://ktiml.mff.cuni.cz/%7Ehric/vyuka/ads_en/ADS2_en_nt.pdf
Slides (and their numbers) can be updated.
Lecture 1: Oct. 7th, 2019
Slides 1-8
Introduction.
Naive searching, Aho-Corasick search machine, Interpretation alg. 1
Lecture 2: Oct 14th, 2019
Slides 9-23
AC interpretation: correctness and complexity; construction of AC machine (alg. 2 and 3).
Alg. Knuth-Morris-Pratt (briefly).
Lecture 3: Oct 21th
Slides 23-37
Alg. Rabin-Karp. Flows in networks: introduction, alg. Ford-Fulkerson, properties
No lecture at Oct. 28th
L4: November 4th
Slides 37-48
Alg. Ford-Fulkerson - complexity, Dinic alg., introduction to Goldberg alg.
L5: November 11th
Slides 49-61
Goldberg alg., intro to FFT
L6: November 18th
Slides 61-72
FFT - fast Fourier transformation
L7: November 25th
Slides 73-96
FFT: Final remarks, Butterfly operation ; Sorting networks
L8: December 2nd
Slides 96-106
Carry look-ahead alg. for addition ;
NP-Complete problems, introduction
L9: December 9th
Slides 106-111
NP-Complete problems, continuation, examples
Planned:
L10: December 16th
Slides 112-119
NPC ; Approximation alg. - introduction
L11: January 6th, 2020
Slides 119-133
Approximation alg., examples