Cvičení z programování II, PRG031


Cvičení se koná ve čtvrtek v 9:00 v T6 v Tróji.

Podmínky k získání zápočtu

Informace o zápočtovém programu

Domácí úkoly (16. 06. 2006)

Datum
cvičení
IDBodyPopis
23. únoraNafu2Implementujte 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řeznaNPru1Na 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é.
DPru1Na 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.
NSje1Na 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é.
DSje1Na 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.
Cykl2Na 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řeznaPAdd1Na 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.
PMul2Na 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).
MMul3Na 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).
CMer1-5Napiš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.
RMQ1-5Napiš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[j] pro i<=j". Body dostanete podle složitosti algoritmus.
PředzpracováníDotazBody
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řeznaKOba2Na 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řeznaPerf1Ze zadaného spojáku setříděných prvků zkonstruujte v lineárním čase perfektně vyvážený strom.
BB-α3Implementujte 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.
Pis1A1Pí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.
Pis1B2Pí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řeznaBinT1Implementujte operace Find, Insert a Delete nad normálním binárním vyhledávacím stromem.
AVL3Implementujte operace Find, Insert a Delete nad AVL stromem.
RedB3Implementujte operace Find, Insert a Delete nad červenočerným stromem.
BTree3Implementujte 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. dubnaBnka3Pomocí 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. dubnaHano2Na 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ů.
Posl2Na vstupu dostanete dvě posloupnosti délky N a M. Najděte jejich nejdelší společnou podposloupnost v čase O(NM).
27. dubnaTopo2Na 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).
Eulr2Na 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ětnaDijk2Na 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.

Stav (01. 10. 2006)

JménoÚkolyZápočťákZápočet
OdevzdanéBodů
celkem
SpecifikaceHodnocení
Jan CísařNSje(1), NPru(1), AVL(3), Topo(1), Nafu(2)8EfektovátkoOdevzdáno, OKAno
Lukáš Malý 0ŽádnáNeodevzdánoNe
Maryna MarchenkoPAdd(1), PMul(2), Topo(2), Hano(1), KOba(1), Posl(1)8PexesoOdevzdáno, OKAno
Kuba MarekPis1A(1), Pis1B(2), Nafu(2), AVL(3), NPru(1), DSje(1)10EngineOdevzdáno, OKAno
Michal MarkoBinT(1), AVL(3), Cykl(1), Dijk(1), PMul(1), Topo(1)8GrafovátkoOdevzdáno, OKAno
Petr Mašek 0ŽádnáNeodevzdánoNe
Vladimír MikušPAdd(1), BinT(1), AVL(3), NPru(1), NSje(1), Cykl(2)9SeeLogOdevzdáno, OKAno
Karel Němejc 0ŽádnáNeodevzdánoNe
Ondřej OdcházelBinT(0.5), Nafu(1), PAdd(0.5), PMul(1), MMul(1.5), Cykl(1), NPru(0.5), NSje(0.5), BB-α(1.5)8Rozpoznávátko strikes backOdevzdáno, OKAno
Michal PapežPis1A(1), Pis1B(2), BB-α(3), RMQ(4)103D šachyOdevzdáno, OKAno
Jan PavlíkPis1A(0.5), BinT(1), AVL(3), Cykl(2), NSje(0.5), PAdd(0.5), NPru(0.5)8Kaasl of da uindsOdevzdáno, OKAno
Pavlína Pecoldová 0CaptureAudioNeodevzdánoNe
Šimon RajčanAVL(1.5), NPru(0.5), DPru(0.5), Cykl(1), Posl(1), Dijk(1), Topo(1), NSje(0.5), DSje(0.5), PAdd(0.5)8GameskaOdevzdáno, OKAno
Václav RemešPis1A(1), Nafu(2), BB-α(3), KOba(1), Dijk(1)83D šachyOdevzdáno, OKAno
Jan SequensPis1A(0.5), AVL(3), Topo(1), Dijk(1), RMQ(1), Bnka(1.5)8BatchResOdevzdáno, OKAno
Tomáš SkalickýPis1A(0.5), NPru(1), DPru(1), PAdd(1), PMul(2), BinT(1), AVL(3)9.5ZobrazovadloOdevzdáno, OKAno
Lukáš SlivkaPis1A(1), AVL(3), BinT(1), NPru(1), Perf(1), Topo(1)8Dáma advancedOdevzdáno, OKAno
Petr SobotkaPis1A(1), PAdd(1), PMul(2), AVL(3), BB-α(1.5)8.5KALKULAJDAOdevzdáno, OKAno
Tomáš StarýBinT(1), AVL(3), Dijk(2), NSje(1), NPru(1)8SudokuOdevzdáno, OKAno
Radomir TarabicCMer(4), Dijk(2), Topo(2)8ŽádnáNeodevzdánoNe

Pokud byste něco potřebovali, napište mi na fox {zavináč} ucw {tečka} cz.


Zpět