Datum
cvičení | ID | Body | Popis
|
|---|
| 23. února | NPru | 1 | Na vstupu dostanete 2 setříděné jednosmerné spojové seznamy. Máte za úkol vytvořit nový spojový seznam, který bude průnikem těchto seznamů. Původní seznamy musíte nechat nezměněné.
|
| DPru | 1 | Na vstupu dostanete 2 setříděné jednosmerné spojové seznamy. Máte za úkol vytvořit nový spojový seznam, který bude průnikem těchto seznamů. Nesmíte alokovat žádnou paměť a zadané seznamy musíte uvolnit, přičemž některé části této paměti můžete použít k uložení výsledného spojáčku.
|
| NSje | 1 | Na vstupu dostanete 2 setříděné jednosmerné spojové seznamy. Máte za úkol vytvořit nový spojový seznam, který bude sjednocením těchto seznamů. Původní seznamy musíte nechat nezměněné.
|
| DSje | 1 | Na vstupu dostanete 2 setříděné jednosmerné spojové seznamy. Máte za úkol vytvořit nový spojový seznam, který bude sjednocením těchto seznamů. Nesmíte alokovat žádnou paměť a zadané seznamy musíte uvolnit, přičemž některé části této paměti můžete použít k uložení výsledného spojáčku.
|
| P1 | | Za čtyři výše uvedené úlohy lze získat maximálně dva body.
|
| KOba | 2 | Na vstupu dostanete N bodů v rovině a vaším úkolem je najít a vypsat konvexní obal, a to jako posloupnost jeho bodů proti směru hodinových ručiček. Časová složitost nesmí být horší než O(N2). |
| 3. března | PAdd | 1 | Na vstupu dostanete dva řídké polynomy, čili takové jednosměrné spojové seznamy dvojic (stupeň, koeficient) seřazené podle stupně od nejmenšího, že každý koeficient je nenulový a každý stupeň je uveden nanejvýš jednou. Takový spojový seznam reprezentuje polynom, který má koeficienty uvedené ve spojovém seznamu shodné a ostatní koeficienty má nulové. Vaším úkolem je tyto dva řídké polynomy sečíst, čili vytvořit nový řídký polynom reprezentující jejich součet. Původní polynomy nechejte beze změny.
|
| PMul | 2 | Na vstupu dostanete stejně jako v předchozím případě dva řídké polynomy. Vaším úkolem je tentokrát zadané polynomy vynásobit, čili vytvořit příslušný řídký polynom odpovídající jejich součinu. Původní polynomy opět neměňte.
Časová složitost NESMÍ záviset na hodnotách stupňů, jenom na počtu nenulových koeficientů v zadaných polynomech, a musí být v nejhorším O(N3).
|
| MMul | 3 | Na vstupu tentokrát dostanete dvě řídké matice, opět jednosměrný seznam nenulových koeficientů maticem, přesně trojic (řádka, sloupec, koeficient), který je setříděn podle řádek a v případě stejných řádek podle sloupce. Vaším úkolem je dané matice vynásobit a výsledek reprezentovat jako další řídkou matici.
Časová složitost by opět neměla záviset na skutečných rozměrech matice.
|
| Cykl | 2 | Na vstupu dostanete jednosměrný spojový seznam neznámé délky. Vaším úkolem je říci, zda je či není zacyklený. Časová složitost vašeho řešení by měla být lineární vzhledem k počtu různých prvků zadaného seznamu a paměťová složitost by měla být konstantní. |
| 17. března | HSrt | 2 | Jako vstup dostanete N prvkové pole reálných čísel. Setřiďte ho pomocí heapsortu přímo v tomto poli a použitou haldu vystavějte v lineárním čase.
|
| Perf | 2 | Na vstupu dostanete setříděný seznam N prvků. Vystavějte z něho v lineárním čase perfektně vyvážený strom (pro každý vrchol se velikost levého a pravého podstromu liší maximálně o jedna).
|
| BinT | 1 | Implementujte operace Find, Insert a Delete nad normálním binárním vyhledávacím stromem.
|
| AVL | 3 | Implementujte operace Find, Insert a Delete nad AVL stromem.
|
| RedB | 3 | Implementujte operace Find, Insert a Delete nad červenočerným stromem.
|
| BTre | 3 | Implementujte operace Find, Insert a Delete nad B-stromem (stačí 2-3 strom).
|
| P2 | | Za čtyři výše uvedené úlohy lze získat maximálně čtyři body. |
| 24. března | Bnka | 3 | Pomocí hešování implementujte jednoduchou banku. Vstupem bude textový soubor, na každém řádku jeden příkaz NOVÝ_KLIENT, DESTRUHUJ_KLIENTA, ZMĚŇ_HOTOVOST_KLIENTA (pojmenujte si je jak chcete). Program vsechno zpracuje a při destrukci zákazníka a na konci u všech existujících zákazníků vypíše jejich hotovost. Počet zákazníků v bance by neměl být omezen žádnou konstantou (čili byste měli přehešovávat). |
| 14. dubna | QMed | 1 | Naprogramujte proceduru, která najde medián v poli v průměrně lineárním čase pomocí upraveného Quicksortu.
|
| LMed | 3 | Naprogramujte proceduru, která najde medián v poli v lineárním čase i v nejhorším případě.
|
| AQue | 3 | Navrhněte a naprogramujte datovou strukturu, do které se dají vkládat libovolná data, a která bude podporovat následující operace:
PUSH přidává položku na konec, TAIL vrací poslední položku, POP odebírá položku z konce.
RPUSH přidává položku na začátek, HEAD vrací první, RPOP odebírá položku ze začátku.
EMPTY celou strukturu vyprázdní. Pozor na to, že musíte správně uvolnit všechny položky, které ve struktuře právě jsou (například vložené soubory musíte uzavřít, vložená pole uvolnit atd... Požadovanou uvolňovací proceduru může/musí uživatel zadat.)
Omezeno do půlnoci mezi 20. a 21. dubnem. |
| 21. dubna | OptT | 2 | Vytvořte program, který vytvoří optimální strom ze zadaných prvků a1,...,an, když se na každý prvek budete dotazovat p1,...,pn-krát. Optimálním stromem myslíme takový strom, že čas na zpracování p1 dotazů na a1, p2 dotazů na a2, ... , pn dotazů na an byl co nejmenší. Očekáváná složitost je O(N^3).
Za O(N^2) dostanete bonusový bod.
|
| Ruck | 2 | Máte K předmětů, každý má celočíselnou hmotnost mi a reálnou nezápornou cenu ci. Napište program, který v polynomiálním čase vybere takovou podmnožinu těchto předmětů, že jejich váha nebude v součtu větší než zadané M a jejich cena bude maximální. |
| 28. dubna | Dijk | 2 | Naprogramujte hledání všech nejkratších cest ze startovního vrcholu v grafu s nezáporným ohodnocením hran pomocí Dijsktrova algoritmu bez haldy, čili složitost bude v nejhorším O(N^2).
|
| DijH | 2 | Naprogramujte hledání všech nejkratších cest ze startovního vrcholu v grafu s nezáporným ohodnocením hran pomocí Dijsktrova algoritmu s haldou, čili složitost bude v nejhorším O(M log N).
|
| DHeu | 2 | Naprogramujte hledání nejkratší cesty mezi startovním a cílovým vrcholem v grafu s nezáporným ohodnocením hran, pokud znáte zeměpisné souřadnice všech vrcholů. Použijte příslušnou heuristiku.
|
| P3 | | Za tři výše uvedené příklady lze získat maximálně čtyři body. |
| 5. května | ZCyk | 2 | Vytvořte program, který zjistí, zda se v zadaném grafu nachází záporný cyklus. Formát vstupu si vyberte libovolný. Program musí fungovat se složitostí nejvýš O(N^3).
|
| Floy | 3 | Napište program, který dostane matici vzdáleností grafu, a spočtě všechny nejkratší cesty v zadaném grafu. Pozor na to, že tento graf může obsahovat i záporné cykly. Program musí fungovat se složitostí nejvýš O(N^3).
|
| P4 | | Za dva výše uvedené příklady lze získat maximálně tři body. |