Zbytek Fibonacciho hald (viz zápis minulého cvičení).
Range-trees. Dávejte pozor na body, které jsou nad sebou. Rozmyslete si, jestli držíte polouzavřené intervaly nebo otevřené (a pak máte ještě strukturu pro body, které mají stejnou x-ovou souřadnici). Viz poznámky Martina Mareše z minulého roku.
Použil jsem definici BB[α] stromů ze slidů přednášky (předchozí odkaz a slidy se trochu liší).
Koukněte se na článek "Replacing Mark Bits with Randomness in Fibonacci Heaps" Jerry Li and John Peebles, MIT citovaný ve zdrojácích generátoru. Je tam hezký obrázek toho, co se děje v generovaném testu (ve zdrojáku generátoru i s poznámkou o složitosti).
Fibonacciho haldy. Malinko o Splay stromech a malinko o transpozici matice.
Fibonacciho haldy: přemýšlení nad implementací, tvorba hluboké haldy -- jen cesta, všechny prvky označené.
Jak si rozmyslet a naprogramovat a nezbláznit se z toho:
Program dot je naistalován v labu. Stačí mít uložený soubor graf.dot s obsahem jako na https://en.wikipedia.org/wiki/DOT_(graph_description_language)
například:
digraph graphname { 3 -> 1; 3 -> 5; 5 -> 4; }
dot -Tpdf graf.dot > graf.pdf
Dobré zdroje v náhodném pořadí:
Nabízím konzultace (po dohodě, ideálně víc lidí) přímo nad vaším kódem.
Výsledky splay stromů, začátek Fibonacciho hald. Příště budou Fibonacciho haldy.
Amortizovaná analýza nafukovacího pole, pokud můžeme přidávat a odebírat na i z konce a na i ze začátku.
Rekurzivní mergesort a jeho cache oblivious analýza. k-cestný merge.
Z-order indexace -- prokládání bitů, cache oblivious analýza, že nepotřebuje štíhlou cache (tall cache assumption), transpozice matice a násobení matice.
Transpozice matice, pokud nepoužíváme swap_and_transpose, tak je logaritmicky pomalejší. Pro správnou implementaci koukněte na https://ktiml.mff.cuni.cz/~fink/teaching/data_structures_I/handout.pdf
V domácím úkolu opravdu matici držte v jednodimenzionálním poli bez Z-orderu a nedoplňujte rozměry nulami. Koukněte se na rady ohledně měření času.
Pro kompilaci generátoru u druhého domácího úkolu se může hodit flag -fpermissive
Pro první domácí úkol se může hodit článek: Donald E. Knuth. Optimum binary search trees. Acta informatica, 1(1):14–25, 1971. Případně i anglická Wikipedie. Použité zdroje nezapomeňte citovat!
Stromy, Splay stromy příklady 1, 3, 4 z 1.pdf a ještě jednou staticky optimální stromy z minula (viz slides přednášky).
Program dot je naistalován v labu. Stačí mít uložený soubor graf.dot s obsahem jako na https://en.wikipedia.org/wiki/DOT_(graph_description_language)
například:
digraph graphname { 3 -> 1; 3 -> 5; 5 -> 4; }
dot -Tpdf graf.dot > graf.pdf
Odevzdávátko by mělo fungovat. Zkuste ho a pokud nefunguje, hlaste chyby!
Pokud máte problémy s getopts na windows, můžete zkusit https://github.com/alex85k/wingetopt
Domácí úkol 0 (ten neodevzdáváte, to udělali vaši cvičící). Změněno 15.10. aby fungoval i na počítačích v labu.
Rady jak vypracovávat domácí úkoly.
Konstrukce staticky optimálního BVS.
Existuje implementační seminář k datovým strukturám (Jiří Fink).
Existuje i teoretičtější seminář (Martin Mareš).
Další zdroje informací:
Viz SIS, případně stránka přednášejícího.