Cvičení - Datové struktury 1

ZS 2021/2022
NTIN066 - 2/2 Zk/Z

Michal Koucký
<koucky@iuuk.mff.cuni.cz>

Od středy, 1. prosince, se cvičení až do odvolání koná přes Zoom.

Čas konání: St 10:40-12:10
Místo konání: S11, Malá Strana. Zoom: https://cesnet.zoom.us/j/4042155019.

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.

Domácí úkoly

  1. Tree successor - do 20.10.2021, ​10:40.
  2. Splay trees - do 27.10.2021, ​10:40.
  3. Splay tree experiment - do 3.11.2021, ​10:40.
  4. (a,b)-trees - do 10.11.2021, ​10:40.
  5. (a,b)-tree experiment - do 17.11.2021, ​10:40.
  6. Transpozice matice - do 24.11.2021, ​10:40.
  7. Transpozice matice experiment - do 1.12.2021, ​10:40.
  8. Kukačkové hešování - do 8.12.2021, 10:40.

Požadavky na zápočet

Požadavky:

Programovací úkoly:

Experimentální úkoly

Všeobecná pravidla

Citace: Část textu převzatá od Ondřeje Mičky.