Algoritmy a datové struktury I (NTIN060) LS 2009/2010

• Vedl jsem dvě cvičení z ADS I. Jedno se konalo v učebně S7 v pondělí 9:00 a bylo určené pro kruh 32. Druhé hned potom v S6 v pondělí v 10:40 pro kruh 31. Obě patřily k přednášce Luďka Kučery.
• Podmínkou získání zápočtu bylo sepsání zápočtové práce na téma nějakého zajímavého algoritmu a složené z:
  • programu implementujícího tento algoritmus, pokud možno včetně pár testovacích vstupů - z nich je snadno vidět formát vstupu
  • popisu algoritmu, důkazu jeho správnosti a analýzy časové a paměťové složitosti
  • program můžete psát v jazycích C, C++, Java, C#, Pascal; pokud byste rádi nějaký jiný, můžete se na tom se mnou zkusit dohodnout
• Při výběru tématu se můžete inspirovat z loňské nabídky témat na stránce Martina Mareše.
• Další témata:
  • BVS vyvažované přestavbou podstromů
  • Insert a Delete v BB-alpha stromech
  • Očíslování neuspořádaných k-tic. Každé k-tici prvků množiny {1,2,...,n} lze jednoznačně přiřadit celé číslo mezi 1 a (n nad k). Říkejme mu identifikátor k-tice. Na vstupu je n, k a neuspořádaná k-tice čísel z {1,2, .. ,n}. Vypište její identifikátor. Čas O(n + k log(n)).
  • Rozhodněte, zda v zadané posloupnosti má nějaké číslo alespoň n/k výskytů (např využijte hledání mediánů v lineárním čase). Čas O(n log(k)).
• Zadaná témata: skupina pondělí 09:00, skupina pondělí 10:40 (v rámci 1 skupiny musí být témata navzájem různá).
• Termín pro výběr tématu: 21.5.2010.
• Termín pro odevzdání: není. Ale rozhodně počítejte s dostatečnou rezervou (minimálně týden, v době prázdnin raději dva) před tím, než zápočet budete potřebovat.