Úloha 1 (Maximum): Navrhněte komparátorovou síť, která dostane-li $n$ prvků a vydá takovou permutaci, v níž bude poslední hodnota největší.

Úloha 2 (Zatřízení): Sestrojte komparátorovou síť, která dostane $(n-1)$-prvkovou setříděnou posloupnost a jeden prvek navíc, vydá setříděnou permutaci.

Úloha 3 (Nula-jedničkový princip): Dokažte, že když komparátorová síť třídí všechny vstupy, ji postačí otestovat na všech posloupnostech nul a jedniček.

Hint: Uvažte obecný vstup, na kterém to selže a najděte pro něj nevalidní 0/1 vstup.

Úloha 4 (Batcherovo třídění): Stejné složitosti paralelního třídění lze také dosáhnout následujícím rekurzivním algoritmem pro slévání setříděných posloupností:

Bmerge:

1. Vstup: Setřízené posloupnosti $(x_0, \dots, x_{n-1}), (y_0, \dots, y_{n-1})$
2. Je-li $n \leq 1$, vyřešíme triviálně.
3. $(a_0, \dots, a_{n-1}) \gets$ BMerge$((x_0, x_2, \dots, x_{n-2}), (y_0, y_2, \dots, y_{n-2}))$
4. $(b_0, \dots, \,b_{n-1}) \gets$ BMerge$((x_1, x_3, \dots, x_{n-1}), (y_1, y_3, \dots, y_{n-1}))$
5. Výstup: $(a_0, \min(a_1, b_0), \max(a_1, b_0), \min(a_2, b_1), \max(a_2, b_1), \dots, b_{n-1}) \hskip -1cm$

Pomocí předchozího cvičení dokažte, že tato procedura funguje. Zapište tento algoritmus ve formě třídicí sítě.

Úloha 5 (Závody formulí**): Sestrojte program (v polynomiálním čase vůči $n$), co na vstupu dostane formuli o $n$ hradlech složenou z and/or/not a na výstupu vygeneruje ekvivalentní hradlovou síť. Přitom chceme mít garanci, že vygenerovaná síť bude mít nějak omezenou hloubku – ideálně $\O(\log n)$, ale cokoliv v $o(n)$ je zajímavé. [KSP: 33-2-X1]

Úloha 6 (Porovnání): S pomocí předešlé úlohy vytvořte co nejmělčí hradlovou síť, která pro $n$-bitová čísla $a, b$ vydá $1$ právě když $a\leq b$.

Úloha 7 (Barevné body): V rovině je dána množina červených a množina zelených bodů. Sestrojte přímku, která obě množiny oddělí (nebo řekněte, že to nelze). Na jedné její straně tedy budou ležet všechny červené body, zatímco na druhé všechny zelené.

Úloha 8 (Dva ploty): Mějme $n$ jabloní, které chceme uchránit oplocením. Všimněte si, že pokud bychom netrvali na tom, aby byly oplocené jedním plotem, mohli bychom ušetřit pletivo. Sestrojte dva uzavřené ploty tak, aby každá jabloň byla oplocena a celkově jste spotřebovali nejméně pletiva.