Cvičenie č.1

01. Cvičenie č.1

Úlohy:

Úloha: Preštudujte priloženú dokumentáciu. Zopakujte si jazyk stroja RAM.

Úloha: Navrhnite algoritmus a odlaďte program pre stroj RAM.

02. Cvičenie č.2

Úlohy:

Úloha: Navrhnite algoritmus a odlaďte program pre stroj RAM.

Úloha: Stanovte asymptotickú časovú a priestorovú zložitosť RAM programu pre výpočet súčtu postupnosti 1,2,...,n. (cvičenie č.2). Použite uniformné aj logaritmické cenové kritérium (inštrukcia ADD).

03. Cvičenie č.3

Úlohy:

Úloha: Oboznámte sa s jednotlivými prvkami rozhrania vývojového prostredia.

Úloha: Vytvorte nový projekt (File->New->Project), vyberte konzolovú aplikáciu (Console Application) ako typ projektu, zvoľte jazyk C, zadajte meno projektu a jeho umiestnenie.

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte a výsledný program spustite (Build->Build and run).

Úloha: Oboznámte sa s možnosťami ladenia programu v prostredí Code::Blocks. Ladenie je možné spustiť z ponuky: Debug->Start (F8). Prakticky overte tvorbu bodu prerušenia (Breakpoint) a krokovanie behu programu.

Úloha: Dôkladne preštudujte dodaný kód. V prípade nejasností sa s konkrétnou otázkou obráťte na cvičiaceho.

Úloha: Pridajte podporu operácií Cat a Cut na ADT List. Význam operácií je jasný z obrázkov.

Úloha: Vytvorte implementáciu ADT List, ktorá umožňuje realizovať operácie Cut a Cat v čase O(1).

04. Cvičenie č.4

Úlohy:

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte.

Úloha: Pridajte podporu operácie TopAndPop, ktorá prečíta a zároveň odoberie prvok z vrcholu zásobníka (nie len zavolaním existujúcich operácií).

Úloha: Pridajte podporu operácie PrintStack, ktorá vypíše obsah zásobníka, bez jeho modifikácie.

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte.

Úloha: Pridajte podporu operácie Push pre vkladanie prvkov do zásobníka.

Úloha: Pridajte podporu operácie PrintStack, ktorá vypíše obsah zásobníka, bez jeho modifikácie.

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte.

Úloha: Pridajte podporu operácií Front, Dequeue, FrontAndDequeue.

Úloha: Pridajte podporu operácie PrintQueue, ktorá vypíše obsah frontu, bez jeho modifikácie.

Úloha: Využitie zásobníka pri vyhodnocovaní výrazov v postfixnom zápise (Postfixná notácia). Výhodou zápisu je jednoduché vyhodnocovanie - po zápise sa postupuje zľava doprava, ak je vstupom číslica - hodnota sa vloží do zásobníka, ak operátor - vyberie sa zo zásobníka potrebný počet hodnôt (binárne operátory +,-,*,/ vyberú dve hodnoty), vykoná požadovaná operácia a výsledok vloží do zásobníka. Ak je prečítaný celý vstup, výsledok vyhodnotenia výrazu je v zásobníku. Napr. VSTUP: 82/35*+ a VÝSTUP: 19

Úloha: Vytvorte ADT Stack, kde prvkami budú ADT Queue. Riešenie prezentujte vhodným testovacím modulom.

05. Cvičenie č.5

Úlohy:

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte.

Úloha: Pridajte podporu operácie PrintRow, ktorá vypíše hodnoty vrcholov na zadanej úrovni stromu.

Úloha: Pridajte podporu operácie PrintSubtree, ktorá vypíše hodnoty vrcholov podstromu, ktorého koreňom je prvok so zadaným indexom.

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte.

Úloha: Nájdite chybu a opravte ju v implementácii operácie pre prehľadávanie grafu do hĺbky dfs. Operácia dfs pre svoju činnosť využíva rekurzívnu funkciu dfsr().

Úloha: Pridajte podporu operácie dfsst, ktorá vypíše hrany tvoriace kostru grafu (spanning tree) získanú prehľadávaním do hĺbky. V prípade, že zadaný graf nie je súvislý, vypíšte všetky kostry (jeho súvislých komponentov) získané prehľadávaním do hĺbky (spanning forest).

Úloha: Vytvorte operáciu bfs realizujúcu prehľadávanie grafu do šírky. Implementujte operáciu bfsst, ktorá vypíše hrany tvoriace kostru grafu (spanning tree) získanú prehľadávaním do šírky. V prípade nesúvislého grafu vypíšte všetky kostry (jeho súvislých komponentov) získané prehľadávaním do šírky (spanning forest).

Úloha: Implementujte operáciu na binárnom strome BuildHeap(), ktorá preusporiada prvky tak, aby tvorili haldu ((max) heap).

06. Cvičenie č.6

Úlohy:

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte. Výsledný program spustite.

Úloha: Pridajte podporu nerekurzívneho prechodu stratégiou PREORDER.

Úloha: Pridajte podporu prechodu stratégiou LEVEL-ORDER. Zvážte využite ADT Queue (cvičenie č.4).

Úloha: Pridajte implementáciu operácie SetTT pre inicializáciu ternárneho stromu a podporu rekurzívneho prechodu ternárnym stromom operáciami preorderTT a postorderTT.

Úloha: Navrhnite a implementujte operáciu levelorderNQ prechodu LEVEL-ORDER binárnym stromom bez využitia ADT Queue, ak výška stromu je jej parametrom.

07. Tu napíšte názov cvičenia.

Úlohy:

Úloha: Tu napíšte konkrétne úlohy, ktoré ma študent vyriešiť.

Úloha: Tu napíšte úlohy ktoré sú pripravené nad základný rámec cvičenia.

08. Cvičenie č.8

Úlohy:

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte. Výsledný program spustite.

Úloha: Implementujte algoritmus MAXMIN podľa uvedeného pseudokódu (alebo prednášok).

Úloha: Implementujte CHAIN_MATRIX_MULTIPLICATION algoritmus podľa uvedeného pseudokódu (alebo prednášok).

Úloha: Implementujte algoritmus Coin Change Problem podľa nižšie uvedeného pseudokódu. Uvažujte riešenia pre rôzne vstupné sumy, ak dostupné sú mince s nominálnymi hodnotami: 100,25,20,5,1.

09. Cvičenie č.9

Úlohy:

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte a výsledný program spustite.

Úloha: Implementujte algoritmus BubbleSort (napr. podľa uvedeného pseudokódu).

Úloha: Postupne zobrazujte činnosť algoritmu (stav poľa) po každom prechode hlavným cyklom.

Úloha: Pridajte podporu utriedenia vstupnej postupnosti vzostupne a zostupne podľa hodnoty parametra funkcie realizujúcej triedenie (pozri obrázok).

Úloha: Implementujte algoritmus InsertionSort (napr. podľa uvedeného pseudokódu).

Úloha: Postupne zobrazujte činnosť algoritmu (stav poľa) po každom prechode hlavným cyklom.

Úloha: Pridajte podporu utriedenia vstupnej postupnosti vzostupne a zostupne podľa hodnoty parametra funkcie realizujúcej triedenie (pozri obrázok).

Úloha: Implementujte algoritmus MergeSort.

10. Cvičenie č.10

Úlohy:

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte. Výsledný program spustite.

Úloha: Postupne zobrazujte činnosť algoritmu pri každom prechode hlavnou slučkou (pozri obrázok).

Úloha: Doplňte do tela funkcie RadixSortQueue kód realizujúci samotné triednie.

Úloha: Postupne zobrazujte činnosť algoritmu pri každom prechode hlavnou slučkou (pozri obrázok).

Úloha: Implementujte triedenie k-tíc nerovnakej dĺžky algoritmom RadixSort.

11. Cvičenie č.11

Úlohy:

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte. Výsledný program spustite.

Úloha: Doplňte implementáciu funkcií HTprint a HTdelete podľa nasledujúceho vzoru.

Úloha: Vytvorte BVS postupným vkladaním prvkov (4, 5, 7, 2, 1, 3, 6).

Úloha: Odstráňte z uvedeného BVS postupne tieto vrcholy (4, 8, 6, 5, 2, 1, 7).

Úloha: Vytvorte AVL strom postupným vkladaním prvkov (4, 5, 7, 2, 1, 3, 6).

Úloha: Odstráňte z uvedeného AVL stromu postupne tieto vrcholy (4, 8, 6, 5, 2, 1, 7).

Úloha: Vytvorte 2-3 strom postupným vkladaním prvkov (1, 5, 8, 3, 6, 9, 7).

Úloha: Odstráňte z vytvoreného 2-3 stromu postupne tieto vrcholy (8, 5).

Úloha: Implementujte hašovaciu tabuľku s otvorenou adresáciou (lineárne, kvadratické hašovanie).

12. Cvičenie č.12

Úlohy:

Úloha: Nastavenie vývojového prostredia tak, aby bolo možné realizovať úhľadný výpis stromových údajových štruktúr.

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte.

Úloha: Pridajte podporu operácie Member, ktorá bude implementovaná ako nerekurzívna funkcia (rekurzívna už bola uvedená).

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte.

Úloha: Pridajte operáciu vyváženia jednotlivých podstromov pre operáciu Delete v prípade, že výška pravého podstromu vyvažovaného vrchola sa zmenší.

Úloha: Funkciu Insert pre pridávanie vrcholov do BVS implementujte ako nerekurzívnu.

Úloha: Vytvorte program pre vytvorenie dokonale vyváženého stromu (rovnomernej distribúcie známeho počtu n vrchov) rekurzívnym spôsobom.