Cvičení - Datové struktury 1
ZS 2021/2022
NTIN066 - 2/2 Zk/Z
Michal Koucký
<koucky@iuuk.mff.cuni.cz>
Nyní opět prezenčně.
Čas konání: St 10:40-12:10
Místo konání: S11, Malá Strana.
Cvičení jsou dvouhodinová. Na cvičeních se probírají řešení domácích úkolů, zadávání nových a probírání příkladů k látce z přednášky.
Účast na cvičeních není povinná. Zápočet se udílí za získání alespoň 90 bodů ze 140 za domácí úkoly řešené během semestru, viz níže.
Cvičení
29.9. - Nekoná se.
6.9. - úvod k domácím úkolům, zkracování natahovacího pole, zlepšení využití místa pro natahovací pole, binární čítač
13.9. - úvod do operací Splay stromů, analýza binárního čítače pomocí potenciálové metody, přičítání a odčítání binárního čítače, čítač s ciframi z {-1,0,1}, operace mazání vrcholu u líně vyvažovaných stromů
20.10. - (Suplování O. Mička) Splay stromy - potenciál příklady stromů, operace Insert a Delete.
27.10. - Alternativní varianta (a,b)-stromů s hodnotami i ve vnitřních uzlech. Amortizovaná analýza štěpení a slévání v (a,b)-stromech pomocí potenciálu.
3.11. - Třídění, třídění předtříděných posloupností pomocí (a,b)-stromů, tzv. A-sort.
10.11. - Cache-oblivious transpozice matice a jeho varianty, třídění z hlediska cache.
24.11. - Příklad kukačkové hešování, narozeninový paradox.
1.12. - Směrodatná odchylka, vyhodnocení experimentálních dat.
8.12. - Cache CPU, její skutečné pamatery, hledání podřetězce, Karp-Rabinovo hešování.
15.12. - Třídění velkých souborů.
22.12. - Bloomův filter pro řetezce a hešování řetezců.
Domácí úkoly
- Tree successor - do 20.10.2021, 10:40.
- Splay trees - do 27.10.2021, 10:40.
- Splay tree experiment - do 3.11.2021, 10:40.
- (a,b)-trees - do 10.11.2021, 10:40.
- (a,b)-tree experiment - do 17.11.2021, 10:40.
- Transpozice matice - do 24.11.2021, 10:40.
- Transpozice matice experiment - do 1.12.2021, 10:40.
- Kukačkové hešování - do 8.12.2021, 10:40.
- Hešovací experiment - do 22.12.2021, 10:40.
- Hledání duplikátů - do 5.1.2022, 10:40.
- Počítání k-gramů - do 13.2.2022, 10:40.
- Zádání jednotlivých úkolů naleznete v ReCodExu.
- Úkoly včetně experimentálních se přes ReCodEx i odevzdávají.
- Prosím přidejte se do příslušné ReCodExové skupiny.
- Zpětná vazba k řešení bude též v ReCodExu. Může být užitečné nastavit si e-mailové notifikace.
- Materiály k úkolům (zdrojové kódy) naleznete v gitovém repozitáři.
Požadavky na zápočet
Požadavky:
- Alespoň 8 programovacích (implementačních) úkolů, 10 bodů za kus
- Alespoň 4 experimentální úkoly, 15 bodů za kus
- Na zápočet je třeba získat alespoň 90 bodů.
- Termíny: 2 týdny od zadání (na konci semestru obvykle více)
Programovací úkoly:
- Dostanete částečnou implementaci datové struktury.
- Máte za úkol implementovat chybějící části. Původní části můžete upravovat.
- Úkol je nejprve testován automaticky, testovací data jsou veřejná.
- Cvičící si prohlédne váš program a případně koriguje bodové ohodnocení.
- Automatické testy jsou pouze nutnou podmínkou. Řešení musí mít správnou složitost, udržovat potřebné invarianty atp.
- Lze řešit v C++ a v Pythonu.
Experimentální úkoly
- Cílem je změřit chování zadané datové struktury.
- Odevzdáváte zprávu s naměřenými hodnotami a diskusí (jako PDF).
- Výsledky je třeba zdůvodnit teorií z přednášek (jde-li to).
Všeobecná pravidla
- O úkolech můžete diskutovat s ostatními, ale nesdílejte s nimi
své programy ani zprávy (ukázat je přednášejícímu nebo cvičícímu
samozřejmě můžete).
- Nesdílejte vzorová řešení úkolů s lidmi mimo vaši skupinu.
- Termíny jsou pevné.
- Před termínem můžete své řešení odevzdávat vícekrát, platí maximum
získaných bodů.
- Program musí projít všemi testy.
- Kvalita vašich programů a zpráv se promítá do hodnocení.
- V programovacích úkolech nepoužívejte netriviální kód, který jste nenapsali sami.
To zahrnuje cizí implementace datových struktur a jiné než zřejmé knihovní funkce.
Základní použití natahovacích polí (vkládání na konec
std::vector v C++ nebo list.append() v Pythonu) je povoleno,
nic složitějšího už ne.
Pokud si nejste jistí, poraďte se s cvičícím.
- Předchozí pravidlo zahrnuje také kód stažený z internetu, např. ze StackOverflow.
Zjistit si, jak se používá Pythoní
list je pravděpodobně v neškodné.
Hledat, jak se implementuje splay strom už pravděpodobně ne — raději použijte poznámky z
přednášky. Nejste-li si jistí, zeptejte se cvičícího.
- Citujte všechny zdroje! Všechny převzaté výsledky (věty z literatury, výsledky
experimentů z cizích článků, ...) musí být řádně formulovány a citovány.
Chybějící citace jsou (nejen zde) považovány za významný prohřešek proti akademické etice.
- Pokud se rozhodnete použít jinou verzi datové struktury, než zazněla
na přednášce, čeká se od vás důkaz, že také má požadované vlastnosti.
Citace: Část textu převzatá od Ondřeje Mičky.