Informatyka MIMUW

Zadanie 1 (sortowanie liczb całkowitych z ograniczonego przedziału)

Zaproponuj algorytm, który w czasie liniowym sortuje $n$ liczb całkowitych z przedziału $[0..n^3]$.

Zadanie 2 (izomorfizm drzew)

Zaproponuj algorytm, który w czasie liniowym sprawdzi, czy dane dwa $n$-wierzchołkowe drzewa są izomorficzne.
Wskazówka: udowodnij, że zadanie to można w czasie liniowym zredukować do zadania testowania izomorfizmu drzew ukorzenionych. Mając dwa drzewa z korzeniami przetwarzaj je poziomami, poczynając od poziomu na największej głębokości, sprawdzając, czy na każdym poziomie jest taka sama liczba drzew parami izomorficznych.

Zadanie 3 (wyznaczanie minimum)

Udowodnij, że każdy algorytm wyznaczający minimum w zbiorze $n$-elementowym za pomocą porównań, wymaga wykonania w pesymistycznym przypadku co najmniej $n-1$ porównań.

Zadanie 4 ($k$-ty co do wielkości )

Zaproponuj algorytm wyznaczania elementu drugiego co do wielkości w zbiorze $n$-elementowym za pomocą co najwyżej $n + \lceil \log n \rceil - 2$ porównań. Uogólnij ten algorytm na algorytm znajdowania elementu $k$-tego co do wielkości za pomocą co najwyżej $n- k + (k-1)\lceil \log (n-k+2) \rceil$ porównań.

Zadanie 5 (drugi co do wielkości - dolna granica)

Udowodnij, że każdy algorytm wyznaczający element drugi co do wielkości w zbiorze $n$-elementowym za pomocą porównań, wymaga wykonania w pesymistycznym przypadku co najmniej $n + \lceil \log n \rceil - 2$ porównań.
Wskazówka: pokaż, że każdy algorytm wyznaczający element drugi co do wielkości w pesymistycznym przypadku porównuje element minimalny z innymi co najmniej $\lceil \log n \rceil$ razy.

Zadanie 6 (selekcja Hoare'a - analiza, model losowej permutacji)

Dokonaj analizy oczekiwanej złożoności obliczeniowej algorytmu selekcji Hoare'a w modelu losowej permutacji.