Zaawansowane algorytmy i struktury danych/Ćwiczenia 13

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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


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


Zadanie 3

Uzasadnij, dlaczego algorytm $A_{k+1}$ liczenia minimum w tablicy n-elementowej działa w czasie O(1) używając procesorów, gdzie 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

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


Zadanie 5

Zmień algorytm ParallelMerger, tak aby scalał dwa ciągi w czasie logarytmicznym, używając tylko procesorów.

Rozwiązanie

Zadanie 6

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

Rozwiązanie

Zadanie 7

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

Rozwiązanie