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