Zaawansowane algorytmy i struktury danych/Ćwiczenia 13

From Studia Informatyczne

Spis treści

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+\epsilon_k}, \epsilon_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+\epsilon_k},\  \frac{n}{n^{\alpha}} \times (n^{\alpha})^{1+\epsilon_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 )