Doplňující domácí úloha z ADS I

Pokud se vám nepodařilo nasbírat dostatečné množství bodů za normální domácí úkoly (které můžete stále ještě řešit za poloviční počet bodů, s výjimkou úlohy Path pro ty, co byli na cvičení, kde se předvádělo jeho řešení), můžete získat body za následující praktické úkoly. U těchto úkolů platí ještě více než u ostatních, že nezaručuju včasné opravení – posílat je v posledních 2 týdnech září je skutečně velmi riskantní počin který nikomu nedoporučuju.

Kompletní domácí úkol obsahuje 4 složky:

1. Kód vašeho programu.
2. Zkompilovaný program (tento bod vynechejte pouze v případě, že úkol píšete v Pythonu nebo jiném interpretovaném jazyce).
3. Návod, jak váš program zkompilovat, pokud se jedná o kompilovaný jazyk (pokud víte, co je to makefile, odevzdejte ten), nebo spustit, pokud o interpretovaný.
4. Sadu vstupů. U topologického třídění by alespoň jeden z dodaných vstupů měl mít řádově sto tisíc vrcholů a řádově vyšší miliony hran.

Dokumentaci po vás nechci, neb uživatelská dokumentace by měl být přepis tohoto zadání, a programátorská dokumentace by měly být vaše zápisky z přednášky a zbytek by měl být vidět z vhodně okomentovanáho kódu.

• Topologické třídění. Dostanete graf zadaný tak, že na prvním řádku jsou dvě čísla, a to počet vrcholů a počet hran, a poté za každou hranu jeden řádek, kde je číslo startovního a číslo cílového vrcholu. Na výstupu je na jednom řádku permutace čísel 1 až [počet vrcholů], která odpovídá topologickému uspořádání (první vypsaný vrchol je ten, který musí mít vstupní stupeň 0 ale výstupní ne). (5 bodů)
• AB strom. Váš program by měl umět následující příkazy:
  • I n Vloží do AB stromu číslo n, nebo zahlásí chybu, pokud tam n už je.
  • D n Odstraní z AB stromu číslo n, nebo zahlásí chybu, pokud tam n není.
  • F n Vyhledá v AB stromu číslo n.
  • P Vypíše strom na výstup, a to tak, že vykoná inorder průchod, a vždy, když najde prvek, vypíše tolik mezer, v jaké hloubce ho našel, a poté jeho hodnotu.
  Program by neměl spadnout na nevalidním vstupu, pouze vypsat chybu. (15 bodů za verzi s prvky pouze v listech, 20 za prvky i ve vnitřních vrcholech)
• BVS. Opět operace jako AB strom. K tomuto úkolu existuje několik bonusů. (5 bodů)
  • Vyvažování. (+5 bodů AVL, +10 bodů RB) (vyberte si nejvýše jedno; u RB by příkaz P měl vypisovat i barvu.)
  • B Převod na perfektně vyvážený BVS. (+5 bodů)
  • Následník: Implementujte trojici příkazů G n, S n, A a X n. Zaveďte něco jako pointery na vrcholy (doporučená implementace: pořiďte si pole pointerů na vrcholy (v jazycích typu C# nebo java pole vrcholů), každý vrchol si bude pamatovat, jaký je jeho index v tomto poli, a tyto indexy používejte jako "něco jako pointery"), kde A vrát nejmenší hodnotu ve stromě, X n dostane hodnotu vrcholu, nalezne ho ve stromě a vypíše jeho hodnotu pointeru, G n dostane pointer na vrchol a vypíše jeho hodnotu a S n dostane pointer na vrchol a vypíše pointer na jeho následníka (nebo chybu pokud neexistuje; nesmí spadnout). Příkaz P by měl vypisovat i pointery na vrcholy. Všechny tyto příkazy by měly být naimplementované tak, aby volání A, X na jeho výstup a pak n-1 volání S vždy na výstup předchozího příkazu dohromady trvalo O(n). (+5 bodů; +10 bodů pokud si na pole pointerů napíšete vlastní nafukovací pole (jinak ho můžete udělat velké nějakou dostatečně vysokou konstantu)
  • K n vypíše k-tou nejmenší hodnotu ve stromě v duch domácího úkolu k-tý. (+2 body; +5 bodů, bude-li současně naimplementováno jakékoli vyvažování).

Povolené jazyky jsou Pascal, C, C#, Java, Python a po konzultaci případně další. Z vašeho vybraného jazyka však nesmíte použít žádnou datovou strukturu, kterou nabízí více či méně standardní knihovny, která je složitější, než běžné nenafukovací pole (teda krom pythonu, ale v něm zkuste nafukovacích vlastností listu, který zastupuje pro běžné účely plo, příliš nevyužívat). Jediná výjimka je čtení a parsování vstupu, tam si používejte co chcete.