Cvičení z Pokročilé algoritmizace v LS16/17

Cvičení probíhá každou lichou středu od 14:30 v učebně 347 (nová budova).

Konzultace

Po předchozí domluvě emailem. Sídlím v budově A, 12.patro, místnost 1229.


Podmínky zápočtu

Zápočet lze získat za semestrální práci, která spočívá ve vypracování netriviálního úkolu. To může znamenat buďto implementaci nějakého algoritmu či datové struktury z přednášky či cvičení, nebo úlohu teoretického rázu.

Preferuji vaše vlastní nápady, některé mohou samozřejmě vyplynout z přednášky či cvičení. O každé úloze bych se s vámi však chtěl pobavit, zda ji schválím. Vypracování zápočťáku by mělo obsahovat následující věci:

Dále:

Inspirace pro semestrální práci

Zde je zdaleka nekompletní seznam inspirací pro zápočtovou práci, průběžně budou přibývat. Vlastní nápady jsou vítány. V případě nejasnosti zadání či jiných dotazů se mi ozvěte.

Vybraná témata prací

Seznam studentů
JménoSemestrálka
Marek Alexahousenka ve stromě
Miloslav Brožekpokročilé LCA OK
Radovan Červenýdoplnění grafu na 2-souvislý OK
Michal Čílavan Emde-Boasovy stromy
Tomáš Dejmeknásobení čísel přes FFT OK
Jakub Hummernejdelší úsečka v n-úhelníku
David Jiroutoddělení dvou množin bodů přímkou OK
Adam Kuglerčetníci a loupežníci OK
Jakub Kulíkrank-pairing heaps OK
Peter Mituraimplict treaps OK
Ivan RyšavýRtrees OK
Klára Schovánkováin-place merge OK
Gabriela Turcajováhollow heaps
Petr Urbanobsah a obvod sjednocení obdélníků OK

Obsah cvičení

1.3.2017

Ze souboru úloh jsme udělali 1--7 a 8 bez analýzy. Ostatní zbývají.

15.3.2017

Dořešení úloh z minulého souboru. Některé další úlohy.

29.3.2017

Stihli jsme jen pár věcí k rovinným grafům, geometrii vůbec.

12.4.2017

26.4.2017

Udělali jsme až do 5.7.

10.5.2017

Udělali jsme spíš věci z druhé poloviny papíru.