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


Cvičení se koná ve čtvrtek v 10:40 v S7 na Malé Straně.

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

Informace o zápočtovém programu

Domácí úkoly (14. 01. 2008)

Datum
cvičení
IDBodyPopis
23. únoraNPru1Na 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é.
DPru1Na 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.
NSje1Na 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é.
DSje1Na 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.
KOba2Na 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ř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.
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(N3).
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.
Cykl2Na 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řeznaHSrt2Jako 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.
Perf2Na 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).
BinT1Implementujte 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.
BTre3Implementujte 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řeznaBnka3Pomocí 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. dubnaQMed1Naprogramujte proceduru, která najde medián v poli v průměrně lineárním čase pomocí upraveného Quicksortu.
LMed3Naprogramujte proceduru, která najde medián v poli v lineárním čase i v nejhorším případě.
AQue3Navrhně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. dubnaOptT2Vytvoř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.
Ruck2Má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. dubnaDijk2Naprogramujte 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).
DijH2Naprogramujte 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).
DHeu2Naprogramujte 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ětnaZCyk2Vytvoř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).
Floy3Napiš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.

Stav (29. 09. 2005)

JménoÚkolyZápočťákZápočet
OdevzdanéBodů
celkem
SpecifikaceHodnocení
Filip KittnarBinT(1)1KalkulajdaNeodevzdánoNe
Jaroslav KlímaNPru(1), NSje(1), DPru(1), DSje(1), P1(-2), KOba(2), PAdd(1), AQue(3), Cykl(2)10Button barOdevzdáno, OKAno
Martin KontsekNPru(1), NSje(1), Cykl(2), BinT(1), AVL(3), PAdd(1), PMul(2)11Chaostools 2Odevzdáno, OKAno
Martin KonířNPru(1), NSje(1), PAdd(1), PMul(2), Dijk(2), Floy(3)10Vláčky 2Odevzdáno, OKAno
Honza KoteraCykl(2), NPru(1), DPru(1), PAdd(1), PMul(2), BinT(1), QMed(1), LMed(3)12SokobanOdevzdáno, OKAno
Jana KravalováNPru(1), DPru(1), KOba(2), PAdd(1), PMul(2), BinT(1), AVL(3), Perf(2), QMed(1)14GraphlibOdevzdáno, OKAno
Standa KuříkNPru(1), NSje(1), PAdd(1), PMul(2), Cykl(2), HSrt(2), BinT(1)10Pretty printing 2Odevzdáno, OKAno
Tomáš KyptaNSje(1), DSje(1), Cykl(2), PAdd(1), PMul(2), BinT(1), AVL(3)11HTMLViewOdevzdáno, OKAno
Petr LasákDSje(1), DPru(1), Cykl(2), PAdd(1), PMul(2), QMed(1), Dijk(2)10PexesoOdevzdáno, OKAno
Petr Maixner 0ŽádnáNeodevzdánoNe
Radek MladaBinT(1), HSrt(2)3MalováníNeodevzdánoNe
Ondřej Moravčík 0MatovátkoNeodevzdánoNe
Pavlína Pecoldová 0ČelistolamNeodevzdánoNe
Martin PilátCykl(2), QMed(1), PAdd(1), NSje(1), NPru(1), PMul(2), Dijk(2)10Mail klientOdevzdáno, OKAno
Jiří TäuberDSje(1), DPru(1), PAdd(1), PMul(2), MMul(3), RedB(2)103D PisqOdevzdáno, OKAno

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


Zpět