Zaproponuj algorytm, który w czasie liniowym sortuje \( n \) liczb całkowitych z przedziału \( [0..n^3] \).
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.
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ń.
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ń.
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.
Dokonaj analizy oczekiwanej złożoności obliczeniowej algorytmu selekcji Hoare'a w modelu losowej permutacji.