Cvičení z algoritmů a datových struktur II, TIN061

Podmínky k získání zápočtu

1. V termínu odevzdat první a druhý domácí úkol. Úkoly budou oznámeny na cvičení a na webových stránkách alespon s měsíčním předstihem.
2. Domluvit se se mnou do konce semestru, tj. do 15. 1. 2010 mailem na tématu zápočtové práce. Inspirace například v seznamu Martina Mareše. Pokud jsme nějaké téma dopodrobna rozebrali na cvičení, tak se mi nejspíš nebude líbit.
3. Poslat mi zápočťák. Většinou po krátké iteraci dostanete zápočet, ale mohu požadovat i osobní předvedení.

Témata by se neměla moc opakovat, takže jedno téma povoluji nanejvýš třem lidem.

Seznam domácích úkolů

• První domácí úkol je úloha Taneční seance. Musíte ji odevzdat do 14. prosince 23:59. Pro opravdu velké opozdilce jsem termín naposledy posunul na 20. prosince 23:59. Pro uznání úkolu musíte získat 90 ze 100 bodů (tj. na devět z deseti testovacích vstupů odpovíte správně). Pokud chcete svůj program testovat sami, zde si můžete stáhnout ukázková data. Tato data jsou přesně tak velká, jako ostrá testovací data, ale nejsou samozřejmě stejná. Časové limity v CodExu jsou 1s 1s 1s 1s 2s 3s 4s 4s 5s 5s, paměťový limit je 64MB.
• Druhý domácí úkol je úloha Debordelizace. Musíte ji odevzdat do 18. ledna 23:59. Pro uznání úkolu musíte získat 100 ze 100 bodů (tj. na všech deset z deseti testovacích vstupů odpovíte správně). Pokud chcete svůj program testovat sami, zde si můžete stáhnout ukázková data. Tato data jsou přesně tak velká, jako ostrá testovací data, ale nejsou samozřejmě stejná. Časový limit v CodExu je 1s na každý vstup, paměťový je 64MB. Časový limit je 10-krát víc než nejlepší řešení v C++ a více než 2-krát více než nejlepší řešení v C#.

Načítání vstupu v C# v CodExu

Seznam přidělených zápočtových prací.

Obsah cvičení (12. 01. 2010)

Datum	Obsah
29. září 2009	Cviko odpadá.
6. října 2009	Řešené příklady: Dlaždičkování šachovnice s dírami dominovými kostkami 2x1. Hledání maximálního párování pomocí toků v síti, jeho složitost. Síť, na které FF nikdy neskončí (a dokonce konverguje k špatnému výsledku).
13. října 2009	Řešené příklady: Nalezněte co nejvíce vrcholově a hranově disjunktních cest mezi dvěma danými vrcholy. Umístěte na šachovnici, která má na některých políčkách zeď, co nejvíce navzájem se neohrožujících věží. Pokud je mezi dvěma věžemi zeď, tyto věže se neohrožují. Ukažte, že následující hladový algoritmus neřeší předchozí úlohu. Pro každé políčko si spočítám následující hodnotu: pokud bych na toto políčko položil věž, na kolik jiných políček už nebudu kvůli tomu moct položit věž. (Jinak řečeno, pro každé políčko si spočítám, kolik dosud neohrozených políček ohrozím, když na toto políčko položím věž.) Poté vyberu libovolné políčko s nejnižší hodnotou a tam věž položím. Algoritmus se opakuje, dokud zbývají neohrožená políčka. První tři lidé, kteří mi pošlou mailem protipříklad, tím splní první úkol. Ukažte, že složitost nalezení maximálního párování pomocí Dinicova algoritmu je Ο(N1/2M).
20. října 2009	Cvičení suploval Martin Mareš, díky :–)
27. října 2009	Cvičení suploval Tomáš Gavenčiak, děkuji :–)
3. listopadu 2009	Řešené příklady: Každý booleovská funkce jde vyjádřit hradlovou sítí ... ... i když ta musí být někdy exponenciálně veliká. Binární přičítačka jedničky nemůže být rychlejší než logaritmická v nejhorším případě. Opakování sčítačky s logaritmickou hloubkou. Binární odčítačka s logaritmickou hloubkou. Hradlová síť pro spočítání zbytku po dělení 3. Komparátorová síť pro nalezení maxima. Komparátorová síť, která zatřiďuje hodnotu do seřazené posloupnosti.
10. listopadu 2009	Řešené příklady: Napište program, který pro danou permutaci sestrojí komparátorovou síť s Ο(log N) vrstvami, která tuto permutaci setřídí. Dokažte, že pokud máme monotónní funkci (x≤y ⇒ f(x)≤y), můžeme ji se stejným výsledkem aplikovat jak před, tak po provedení libovolné komparátorové sítě. Dokažte, že pokud komparátorová síť korektně setřídí všechny posloupnosti nul a jedniček, tak už korektně setřídí libovolný vstup. Dostanete vstup a zakázané slovo. V lineárním čase vyškrtejte z tohoto vstupu všechna zakázaná slova. Pozor na to, že vyškrtnutím jednoho zakázaného slova může další vzniknout, jako například při odstraňování bug ze slova bubugga.
17. listopadu 2009	Cvičení odpadá
24. listopadu 2009	Řešené příklady: V textu délky N najděte nejčastější podslovo dané délky K. V textu délky N najděte nejdelší opakující se podslovo. Co nejjednodušeji zjistěte, jestli dva vektory svírají úhel méně nebo více než 180 stupňů. Vymyslete způsob, jak počítat konvexní obal inkrementálně. Tedy když máte spočítaný konvexní obal N bodů a dostanete další, dokážete obal upravit, aby bral v úvahu i přidaný bod. Spočtěte obsah daného konvexního mnohoúhelníku. Spočtěte obsah daného nekonvexního mnohoúhelníku.
1. prosince	Řešené příklady: Spočtěte obsah sjednocení osově souběžných obdélníků v čase O(N log N). Procvičte si FFT: kolik je DFT(0, 0, ..., 0) Procvičte si FFT: kolik je DFT(ω0, ω1, ..., ωn-1) Procvičte si FFT: kolik je DFT(ω0*j, ω1*j, ..., ω(n-1)*j) Procvičte si FFT: kolik je DFT(cos(0*2π/n), cos(1*2π/n), ..., cos((n-1)*2π/n)) Procvičte si FFT: kolik je DFT(sin(0*2π/n), sin(1*2π/n), ..., sin((n-1)*2π/n))
8. prosince	Řešené příklady: Máte dané body v rovině a číslo K. Vaším úkolem je najít kruh o poloměru K takový, že obsahuje co nejvíce ze zadaných bodů. Procvičte si FFT: kolik je DFT(1,0,1,0,1,0,1,0)? Procvičte si FFT: kolik je DFT(1,1,0,0,1,1,0,0)? Procvičte si FFT: kolik je DFT(cos(0*2jπ/n+φ), cos(1*2jπ/n+φ), ..., cos((n-1)*2jπ/n+φ)) Jak co nejrychleji obrátit bity v uint32_t? Implementujte FFT iterativně.
15. prosince	Řešené příklady: Ukažte, že (E3,E3)-SAT (SAT, každá klauzule má přesně tři literály a každá proměnná se vyskytuje v přesně třech literálech) má vždy řešení. Vyřešte 2-SAT v polynomiálním čase. Ukažte, že nalezené minimální vrcholové pokrytí je NP-úplné. Ukažte, že ZOE je NP-úplné.
5. prosince	Řešené příklady: Dokažte, že v bipartitním grafu je velikost minimálního vrcholového pokrytí rovna velikosti maximálního párování. Ukažte, že problém součtu podmnožiny (dostanete N čísel a1, ..., aN, dále číslo K a máte říct, zda existuje podmnožina čísel ai se součtem K) je ekvivalentní s problémem loupežníků (dostanete N čísel a1, ..., aN a máte říct, jestli jdou rozdělit na dvě skupiny o stejném součtu). Vyřešte problém součtu podmnožiny pomocí problému batohu. Ukažte, že problém součtu podmnožiny je NP-úplný.
12. prosince	Řešené příklady: Pomocí minimální kostry a nejmenšího váženého párování (jeho cílem je v úplném ohodnoceném grafu se sudým počtem vrcholů najít perfektní párování s nejmenším součtem ohodnocení hran) vytvořte 1.5-aproximaci problému obchodního cestujícího. Navrhněte 2-aproximaci minimálního vrcholového pokrytí [stačí hladový algoritmus + fakt, že minimální vrcholové pokrytí je alespoň tak velké jako maximální párování]. Navrhněte 2-aproximaci maximálního řezu. Dostanete graf a vaším cílem je rozdělit vrcholy do dvou skupin tak, aby mezi nimi vedlo co nejvíc hran. Dostanete E3-SAT formuli, čili každá její klauzule obsahuje právě tři literály. Najděte ohodnocení, se kterým bude splněno co nejvíc klauzulí [jde splnit 7/8 klauzulí].

Zápočtové práce (25. 05. 2018)

Výsledky úkolů se aktualizují z CodExu jednou nočně.

Jméno	Úkol 1	Úkol 2	Specifikace	Zápočťák	Zápočet

Pokud byste něco potřebovali, napište mi na fox {zavináč} ucw {tečka} cz.