Cvičení z Algoritmů

Ve školním roce 2003/2004 vedu cvičení z předmětu Algoritmy [NDMI026] v úterý od 17.20 v posluchárně T4.

Podmínkou k získání zápočtu je aktivní řešení příkladů na cvičení, případně naprogramování některého ze složitějších algoritmů, například:

• Maximální tok metodou Tří Indů (složitost O(n³))
• Maximální tok Goldbergovým algoritmem (složitost O(n³))
• Konstrukce Voroného diagramu pro zadanou množinu bodů a jeho nakreslení
• Simulátor komparátorových sítí s ukázkovou sítí na třídění
• Simulátor hradlových sítí s ukázkovou sítí na sčítání v logaritmické hloubce
• Efektivní implementace Dijkstrova algoritmu (třeba s Fibonacciho haldami)
• Maximální tok Dinicovým algoritmem optimalizovaný pro řídké sítě (dají se na to docela hezky použít Sleator-Tarjanovy stromy, na požádání vysvětlím nebo půjčím článek)
• Násobení polynomů pomocí FFT (v čase O(n*log n))
• Filtrace zvuku pomocí FFT