- Lista 1 Pewien wykładowca przydzielił studentom na egzaminie numery od 1 do N. Studenci, którzy kończyli pisanie egzaminu (losowa kolejność) odkładali kartki (format A4) na stos znajdujący się na jednej z ławek i wychodzili. Wykładowca po sprawdzeniu każdej z prac odkładał pracę o numerze k na sąsiednie biurko w następujący sposób:
- jeżeli na biurku nie było prac o numerach k-1 i k+1, to praca o numerze k tworzyła nowy "stos";
- jeżeli na biurku był stos zaczynający się od pracy nr k+1 (praca nr k+1 leży na wierzchu stosu) i nie było pracy k-1, to pracę o numerze k kładł na pracę o numerze k+1;
- jeżeli na biurku był stos kończący się na pracy k-1 i nie było pracy nr k+1, to pracę nr k kładł na spód tego stosu;
- jeżeli na biurku były prace o nr k-1 i k+1, to pracę nr k, kładł na wierzch stosu zaczynającego się od pracy nr k+1, a na nią kładł stos zawierający pracę nr k-1
Zaimplementuj powyższy algorytm sortowania, sprawdź jaka powinna być powierzchnia biurka, aby w ten sposób sprawdzać 100, 1000, 10 000 prac. Sporządź statystyki: średnia liczba stosów, max liczba stosów. Porównaj wydajność czasową i pamięciową QUICKSortem. Sporządź tabele zawierające wyniki symulacji (dla każdego rozmiaru danych co najmniej 1000 prób)
Spróbuj znaleźć funkcję opisującą złożoność obliczeniową (dodatkowe)
- Lista 3 (14 pkt) Niech S będzie zbiorem n punktów na płaszczyźnie. Każdy punkt tego zbioru ma określoną wagę mi - liczbę rzeczywistą określającą rozmiar kropki.
Dla każdego punktu p = (x, y) ze zbioru S = {p1, ..., pn} określono
funkcję f(p) = f(x, y, m) = m (x+y)2. Dla podzbioru T zawartego w S definiujemy F(T) jako sumę
f(pi) po punktach należących do T.
Zaproponuj i zaimplementuj algorytm, który będzie miał następujące właściwości:
- będzie wyliczać w czasie O(lg n) wartość funkcji
F(T(xmin)) = F({pi należą do S : xi >= xmin})
- Dodawanie i usuwanie punktów do zbioru S będzie wykonywane
w czasie O(lg n)
Podpowiedź: wykorzystaj drzewa czerwono-czarne
- Lista dodatkowa (5 pkt) Zaimplementuj algorytm obliczający dla podanego zbioru punktów płaszczyzny R2 otoczkę wypukłą w czasie O(n lg n), gdzie n jest liczbą punktów zbioru.
|