Zaawansowane algorytmy i struktury danych/Ćwiczenia 13

Zadanie 1

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

Rozwiązanie

Zastosuj algorytm na sumy prefiksowe, lewy nawias +1, prawy nawias -1. Sumy musza być nieujemne, a na końcu musi być zero.

Zadanie 2

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

Rozwiązanie

Podobnie jak w zadaniu 1.

Zadanie 3

Uzasadnij, 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ów, 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 dwóch różnych 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 dwóch różnych 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)$