Zápis cvičení

• 8. 10.

  Diskuse o domácích úkolech, konstrukce staticky optimálního stromu, dvojrotace pomocí jednoduchých rotací.

  • PDF s příklady,
  • Doporučení k vypracovávní domácích úkolů (sesbírané cvičícími na základě loňského běhu cvičení),
  • Vzorové zadání a řešení 0. domácího úkolu (tento úkol neodevzdávejte, byl vypracován cvičícími pro ilustraci DÚ),
  • Původní článek o Splay stromech od Sleatora a Tarjana,
  • Lekce č. 5 popisující Splay stromy od Erika Demaine,

• 22. 10.

  Amortizace - dynamické pole s přidáváním a odebíráním prvků z obou konců, splayování na cestě (s jednoduchými rotacemi a dvojrotacemi) a částečně příklad, že dokonale vyvážené stromy nelze udržovat v čase o(n).

  • PDF s příklady,
  • Jednoduchý příklad na amortizaci: Zkuste spočítat amortizovanou cenu operace přičti 1 k číslu (na začátku dostanete n bitové číslo a poté opakovaně provádíte operace přičti 1). Rozmyslete si proč stejnou amortizaci nejde udělat pokud is povolíte i odečítání jedničky.

• 5. 11.

  Cache oblivious analýza. Nafukovací pole s přidáváním na obou stranách, k-cestný mergesort, Z-order indexace matice a její transpozice. Algoritmus z přednášky s obměnou prvně transponuji potom prohazuji je pomalejší.

• 19. 11.

  Rozbor prvních domácích úkolů a upozornění na nejčastější problémy v nich, zopakování hald z přednášky

• 3. 12.

  Fibonaciho haldy - hluboký příklad + protipříklad pro naivní interpretaci. Diskuse o implementaci Fibonacciho haldy.

Podmínky zápočtu

Užitečné odkazy

• Stránky přednášky: Jiří Fink se slidy a dalšími odkazy.
• Stránky přednášky z minulých let jsou k nalezení na: Michal Koucký a Martin Mareš. Obsahují ručně psané přípravy dalších přednášejících.
• Průvodce labyrintem algoritmů
• Zajímavý pokus o interaktivní učení: http://tutor.fi.muni.cz/. Po přihlášení zde jsou dostupné interaktivní příklady na lineární zobrazení v rovině (a také afinní zobrazení). Obsahuje celou řadu dalších typů úloh. Přihlášením podporujete výzkum učení!
• Jestli se chcete naučit psát hezky matematiku, zkuste se podívat na LaTeX. Pro kreslení obrázků se bude hodit například program ipe. LaTeX můžete psát i online například na sharelatex. V případě zájmu vytvořím nějaký ukázkový soubor.