Datum
cvičení | ID | Body | Popis
|
|---|
| 23. února | Nafu | 2 | Implementujte nafukovací pole, které jsme popisovali na cvičení. Musí umět přidávat a odebírat prvky a časová složitost přidání nebo odebrání N prvků musí být O(N). Paměť alokujte samozřejmě dynamicky, použijte funkce GetMem a FreeMem. |
| 2. března | NPru | 1 | Na vstupu dostanete 2 setříděné jednosmerné spojové seznamy. Máte za úkol v lineárním čase vytvořit nový setříděný 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 v lineárním čase vytvořit nový setříděný 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 v lineárním čase vytvořit nový setříděný 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 v lineárním čase vytvořit nový setříděný 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.
|
| Cykl | 2 | Na vstupu dostanete jednosměrný spojový seznam, možná zacyklený. Vaším úkolem je v lineárním čase a konstantní paměti spočítat, kolik má prvků. |
| 9. 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. Váš program musí fungovat v lineárním čase.
|
| 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(N2).
|
| 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 a v nejhorším případě by měla být O(N3).
|
| CMer | 1-5 | Napište mergesort pro pole čísel. Časová složitost musí být O(N log N), paměťová musí být konstantní, takže nemůžete použít pomocné pole na mergeování! Součástí je i osobně mi vysvětlit, jak algoritmus funguje.
|
| RMQ | 1-5 | Napište algoritmus, který dostane na vstupu pole N čísel A a po nějakém předzpracováním bude umět odpovídat na dotazy "jaké je minimum z prvků A[i] až A[j] pro i<=j". Body dostanete podle složitosti algoritmus.
| Předzpracování | Dotaz | Body |
|---|
| O(N2) | O(1) | 1 | | O(N) | O(log N) | 2 | | O(N log N) | O(1) | 2 | | O(N) | O(1) | 5 |
|
| 16. března | 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). |
| 23. března | Perf | 1 | Ze zadaného spojáku setříděných prvků zkonstruujte v lineárním čase perfektně vyvážený strom.
|
| BB-α | 3 | Implementujte pro BB-α stromy operace insert, find a delete.
Použijte buď obecné α nebo α=2.
V případě, že odevzdáte tuto úlohu, nedostanete žádné body za předchozí úlohu Perf.
|
| Pis1A | 1 | Písemka, není to domácí úkol. Cílem bylo napsat proceduru obrat pro obrácení jednosměrného spojového seznamu v lineárním čase a konstantní pomocné paměti.
|
| Pis1B | 2 | Písemka, není to domácí úkol. Cílem bylo napsat proceduru dalsi, která pro zadaný vrchol binárního stromu (s ukazateli na rodiče) našla jeho následovníka v infixovém uspořádání vrcholů. |
| 30. března | 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.
|
| BTree | 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. |
| 6. dubna | | | Suplování cvičení |
| 13. dubna | 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). |
| 20. dubna | Hano | 2 | Na vstupu dostanete nějakou korektní situaci Hanojských věží. Zjistěte, na jaký kolík a za kolik tahů lze disky ze zadané situace přeskládat, aby to šlo na co nejmenší počet přesunů.
|
| Posl | 2 | Na vstupu dostanete dvě posloupnosti délky N a M. Najděte jejich nejdelší společnou podposloupnost v čase O(NM). |
| 27. dubna | Topo | 2 | Na vstupu dostane neohodnocený orientovaný graf s n vrcholy a m hranami. V čase O(n+m) ho musíte načíst, zpracovat a vypsat tolopogické uspořádání vrcholů. Pro něj platí, že každá hrana grafu musí vést z vrcholu s nižším číslem do vrcholu s vyšším číslem. Použít můžete jak algoritmus z přednášky (odtrhávání vrcholů), tak algoritmus ze cvičení (prohledávání do hloubky).
|
| Eulr | 2 | Na vstupu dostane neohodnocený neorientovaný graf s n vrcholy a m hranami. V čase O(n+m) ho musíte načíst, zpracovat a vypsat jeho Eulerovský tah (tzv. nakreslení jednou čarou). Pokud ho graf nemá, vypište příslušné varování. |
| 5. května | Dijk | 2 | Na vstupu dostanete orientovaný graf s nezáporným ohodnocením hran a dva vrcholy s a t. Najděte a vypište nejkratší cestu z vrcholu s do vrcholu t. Váš program musí pracovat buď v čase O(n2+m) nebo O(n log n + m), kde n je počet vrcholů grafu a m je počet hran. |