Zaawansowane algorytmy i struktury danych/Ćwiczenia 13

Zadanie 1

Dany jest ciąg nawiasów otwierających i zamykających jednego rodzaju: ( lub ). Sprawdzić czy jest to ciąg poprawny nawiasowo w czasie log n z pracą liniową.

Rozwiązanie

Zasosować algorytm na sumy prefiksowe, lewy nawias +1, prawy nawias -1. sumy musza być nieujemne a nakońcu zero.

Zadanie 2

Dany jest ciąg nawiasów okrągłych lub kwadratowych ( , ), [ , ], sprawdzić czy jest to ciąg poprawny nawiasowo w czasie log n z pracą liniową.

Rozwiązanie

Podobnie jak w zadaniu 1.

Zadanie 3

Uzasadnić dlaczego algorytm $A_{k+1}$ liczenia minimum w tablicy n-elementowej działa w czasie O(1) używając $P_{k+1}(n))$ procesor"ow, gdzie $P_k(n)=n^{1+{ϵ}_k},{ϵ}_k=\frac{1}{2^k-1}$ Zakładamy, że dwa procesory nie mogą próbować wpisać jednocześnie dwie różne wartości w to samo miejsce (ale mogą jednocześnie tę samą wartość).

Rozwiązanie

$\max \{(\frac{n}{n^{\alpha }}{)}^{1+{ϵ}_k},\frac{n}{n^{\alpha }}\times (n^{\alpha }{)}^{1+{ϵ}_k}\}=O(P_{k+1}(n))$

gdzie $\alpha =\frac{1}{2^k+1}$

Zadanie 4

Oblicz na CRCW PRAM minimum w tablicy n-elementowej w czasie O(log log n) używając O(n / log log n) procesorów. Zakładamy, że dwa procesory nie mogą próbować wpisać jednocześnie dwie różne wartości w to samo miejsce (ale mogą jednocześnie tę samą wartość).

Rozwiązanie

Dzielimy tablicę na kawałki długości $\sqrt{n}$. Z otrzymanymi kawałkami robimy to samo, aż długość będzie pewną stałą.

Zadanie 5

Zmień algorytm ParallelMerger tak aby scalał dwa ciągi w czasie logarytmicznym używając tylko $O(\frac{n}{\log n})$ procesorów.

Rozwiązanie

Podziel ciągi które trzeba scalić na segmenty długości log n.

Zadanie 6

Jaka jest asymptotycznie liczba operacji w układzie arytmetycznym odpowiadającym algorytmowi PrefSums1.

Rozwiązanie

$O(n\log n)$

Zadanie 7

Jaka jest asymptotycznie liczba operacji w układzie arytmetycznym odpowiadającym algorytmowi PrefSums2.

Rozwiązanie

$O(n)$