Pro budoucí generace
Na zkoušce nás bylo "jak psů", takže jsme byli rozděleni do dvou skupin
skupina alfa:
A1. Je dáno N celých čísel v rozsahu 0...N^4 - 1. Popsat třídící algoritmus pracující v čase O(N)
A2. Červenočerné stromy - definice, důkaz logaritmické hloubky, a popsat insert (masochisti mohli i delete)
B1. Na vstupu donstaneme plán bludiště složený ze čtverečků (prázdné nebo zeď) a souřadnice dvou robotů v bludišti. Vymyslet algoritmus, který bude oboum robotům vždy v jednu chvíli dávat tentýž příkaz (jdi na sever, jih, západ, východ) a vyvede je co nejkratším počtem kroků z bludiště (za libovolný okraj). Pokud je před robotem zeď a má jít tím směrem, tak stojí na místě.
B2.V knihovně máme dlouhou řadu N knih seřazenou podle unikátních názvů. Někdo však K knih vyndal a vrátil na špatná místa. Popsat algoritmus, který řadu knih setřídí v co nejlepším čase. N>>K
C. Dokázat, že když máme algoritmus na invertování trojůleníkových matic, tak v tom samém čase umíme taky matice násobit (nebo něco na ten způsob :))
skupina beta měla cosi jako:
A1. Master Theorem, formulovat, dokázat.
A2. už nevím
B1.Najít v neorientovaném ohodnoceném grafu nejdražší čtyřcyklus
B2.Máme kabel plný vodičů a nevíme, které konce na jedné straně odpovídají těm na druhé a pomocí přivádění napětí na jedné straně a měření na druhé co nejmenším počtem operací (připojit na vodič, odpojit, změřit na druhé straně) přiřadit k sobě správně konce vodičů.
Celá zkouška probíhala ve velmi příjemné atmosféře, času jsme měli v podstatě, kolik jsme chtěli. Martin Mareš nás postupně obcházel a konzultoval řešení, takže většina lidí pak spíš už jen čekala, kdy na ně přijde řada.
možné řešení pro alfu:
a1- RadixSort na jehož začátku si převedu čisla do soustavy o základu N.
b1- prohledávání do šířky, roboti smějí jít daným směrem, pokud se alespoň jeden z nich pohne a pokud oba nevstoupí na políčko, na kterém již byli a zároveň tehdy stáli vzájemně na stejných pozicích.
b2- vyhodit ven knihy, které jsou špatně zařazené, setřídit zvlášť a provést Merge O(n+klogk).