Zkouška 10.1.2014 Mareš

Pokračování přednášky TIN060 Algoritmy a datové struktury I
cvutak
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 12. 6. 2013 11:55
Typ studia: Informatika Bc.

Zkouška 10.1.2014 Mareš

Příspěvek od cvutak »

1. Goldberg -- popis, formulace všech lemmat a jak zajistit rychlou implementaci (stačí držet seznam vrcholů s nenulovým přebytkem a v každém vrcholu seznam vrcholů, kam jde převádět + vrcholy mají odkaz na své položky)
2. Maximální vlastní prefix, který je zároveň suffix stringu -- KMP lineárně
3. Máme červené a zelené body v rovině, jak najít přímku, která body rozdělí podle barvy? -- To bylo trochu tricky, jedno správné řešení: Najdu konvexní obaly barevných množin, konvexní obal všech. Ten druhý má jen 2 hrany, které nejsou ani v jednom barevném obalu. Od okraje jedné takové hrany posunuji přímku podél hrany barevného obalu. Koukám, kde mi případně vlezla do druhého barevného obalu a posunu ji do dalšího bodu po směru toho obalu. Tak se na každou hranu v "průřezu" podívám max. 1, takže celkem nlogn.
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“