HycY1

Zadania

1.1- 1. Zilustruj (podobnie jak na rys. 1.2) działanie procedury INSERTION--SORT dla tablicy A « <31, 41, 59, 26, 41, 58).

1.1- 2. Zmodyfikuj procedurę INSERTION-SORT tak, żeby sortowała w porządku nierosnącym.

1.1- 3. Rozważmy następujący problem wyszukiwania:

Dane wejściowe: Ciąg n liczb A = <a _l3 a₂, a„y i wartość v.

Wynik: Indeks i taki, że v = A[i] lub Nil, jeśli v nie jest zawarte w A.

Napisz algorytm wyszukiwania liniowego, który przegląda ciąg A od strony lewej do prawej, szukając v.

1.1- 4. Rozważmy problem dodawania dwóch n-bitowych liczb binarnych, pamiętanych jako n-elementowe tablice A i B. Wynik ma być w postaci (n + l)-elementowej tablicy C. Sformułuj problem formalnie i napisz w przyjętym tu pseudojęzyku procedurę sumownia dwóch liczb tego typu.

1.2- 1. Rozważmy sortowanie n liczb z tablicy A następującą metodą. Znajdujemy najmniejszy element tablicy A i wstawiamy na pierwsze miejsce w pewnej tablicy B. Następnie znajdujemy drugi najmniejszy element z A i wstawiamy na drugie miejsce w B. W ten sposób postępujemy dla wszystkich n elementów tablicy A. Napisz dla tego algorytmu - który jest znany jako sortowanie przez selekcję - program. Podaj pesymistyczny i optymistyczny czas działania tego algorytmu, używając notacji ©.

1.2- 2. Rozważmy znowu wyszukiwanie liniowe (patrz zad. 1.1-3). Ile elementów ciągu wejściowego trzeba średnio sprawdzić przy szukaniu losowego elementu w tablicy? Jak to wygląda w przypadku pesymistycznym? Jaki jest średni i pesymistyczny czas działania tego algorytmu wyrażony za pomocą notacji 0? Odpowiedź uzasadnij.

1.2- 3. Rozważmy problem wykrywania powtarzających się elementów w ciągu n liczb <jc_t, x_2t ..., *„>. Pokaż, że można rozwiązać ten problem w czasie ©(nlgn), gdzie lgn oznacza log₂n.

1.2- 4. Rozważmy problem obliczania wartości wielomianów. Mamy danych n współczynników a₀, a_ls a„^₁ i liczbę rzeczywistą x, chcemy obliczyć

n 1

£ a_}x^l. Opisz bezpośredni algorytm rozwiązujący ten problem w czasie

ż=°

®(n²). Opisz algorytm działający w czasie ©(w), w którym do obliczania wielomianów jest zastosowana następująca metoda (zwana metodą Homera):

n - 1

Z a;*^f = (...(fl^-ijc + a„-₂)x + ... + fli)* + o₀ 1 = 0

1.2- 5. Wyraź funkcję n³/1000 - 100n² — 100« + 3, używając notacji ©.

1.2- 6. Jak zmodyfikować (prawie każdy) algorytm, aby polepszyć jego czas działania w przypadku optymistycznym?

1.3- 1. Zilustruj (podobnie jak na rys. 1.3) działanie procedury Merge-Sort dla tablicy A = <3, 41, 52, 26, 38, 57, 9, 49>.

1.3- 2. Napisz program dla Merge(^4, p, q, r).

1.3- 3. Pokaż, stosując metodę indukcji matematycznej, że rozwiązaniem równania rekurencyjnego

(2,    jeśli n = 2,

7t«)H    1

\2IXnj2) + n, jeśli n = 2*, k > 1

jest 7X«) = nlgn.

1.3- 4. Sortowanie przez wstawianie może być wyrażone jako procedura reku-rencyjna, jak następuje. Aby posortować A[ 1.. n], rekurencyjnie sortujemy A[ 1.. n — 1], po czym wstawiamy A[ń\ w posortowaną tablicę A[ 1.. n — 1], Napisz równanie rekurencyjne na czas sortowania przez wstawianie.

1.3- 5. Wróćmy jeszcze do problemu wyszukiwania (patrz zad. 1.1-3). Zauważmy, że jeśli ciąg A jest posortowany, to możemy porównać środkowy element z elementem v, pomijając dzięki temu przeszukiwanie połowy tablicy. Wyszukiwanie binarne polega na powtarzaniu tej operacji rekurencyjnie. Napisz program, rekurencyjny lub nie, wyszukiwania binarnego. Uzasadnij, że jego czas działania wynosi ©(lg n).

1.3- 6. Zauważmy, że w pętli while w wierszach 5-7 procedury INSERTION--Sort w podrozdz. 1.1 jest zastosowane szukanie liniowe (do tyłu) w posortowanej podtablicy A[ 1 ..j — 1], Czy można skorzystać z wyszukiwania binarnego (patrz zad. 1.3-5), aby zmniejszyć czas działania do ©(nlgn)?

* 1.3-7. Opisz algorytm działający w czasie ©(nlgn), który dla danego zbioru S złożonego z n liczb rzeczywistych i liczby rzeczywistej x sprawdza, czy istnieją dwa elementy w S, których suma jest równa dokładnie x.

Problemy

2-2. Względny rząd asymptotyczny

Dla każdej pary wyrażeń (A, B) w poniższej tabeli napisz, czy A jest O, o, O, tu lub © od B. Załóżmy, żefc^l,e>Oic>l są stałymi. Twoja odpowiedź powinna brzmieć „tak” lub „nie”.

	A	B	O	0	n	(O	O
(a)	lg*n	n'
(b)	n*	<*				L
(c)	V"	pjSin u				i
(d)	2"	2"^/2
(<0	n^km	nł**
(0		lg(«")

2-3. Porządkowanie ze względu na rząd wielkości funkcji

(a) Uporządkuj następujące funkcje ze względu na ich rząd wielkości; to znaczy znajdź uporządkowanie g_u g₂,g₃₀ tych funkcji, spełniające zależności g_t = 0{g₂), g₂ = Cl(g₂),    g₂₉ = lifeao). Podziel swoją listę na klasy

równoważności takie, że/(n) i g(n) należą do tej samej klasy wtedy i tylko wtedy, gdy /(») = ©(#(«))■

IgOg^)	21g*n	(yfl)^1*"	n^2	n!	Ogn>!
(U	n^3	lg^2"	lg(n!)	2^2'
In Inn	lg*n	n-2"	fjlglgn	Inn	1
2^lB"		e"		(n + 1)!	\j\gn
lg*0g«)	2-/Zlgn	n	2"	nlgn	2^2" ‘

(b) Podaj przykład jednej nieujemnej funkcji f(n) takiej, że dla wszystkich funkcji gi(n) z części (a) funkcja f(n) nie jest ani 0(gj(n)), ani Q(gj(n)).

4.1.    Przykłady rekurencji

Podaj asymptotyczne górne oraz dolne oszacowanie dla T(ri) w każdej z danych poniżej rekurencji. Załóż, że T(n) jest stałą dla n < 2. Twoje oszacowania powinny być tak dokładne, jak to możliwe. Odpowiedzi uzasadnij.

(a)    T(n) = 2T(nj2) + n³

(b)    T(n) = T(9njl0) + n

(c)    T(n) *= 16T(n/4) 4- n²

(d)    T(n) = 7T(n/3) + n²

(e)    T(n) = lT(njl) + n²

(f)    T(n) = 2T(njA) + V*

(g)    T(n) = T(n^\) + n

(h)    T(n) = T(V«) + 1

4.2.    Szukanie brakującej liczby całkowitej

Tablica A[ 1 ..n] zawiera wszystkie liczby całkowite z przedziału 0..n oprócz jednej. Można łatwo wyznaczyć brakującą liczbę całkowitą w czasie 0(n), używając pomocniczej tablicy 5[0.. n] w celu zapamiętania liczb występujących w A. Jednakże w problemie tym nie mamy dostępu do całych liczb całkowitych wiw stałym czasie. Elementy tablicy A są reprezentowane binarnie i możemy jedynie korzystać z operacji typu „pobierz j-ty bit A[i]'\ która jest wykonywana w stałym czasie.

Pokaż, że jeśli używamy jedynie tego typu operacji dostępu do danych, to możemy jednak wyznaczyć brakującą liczbę w czasie 0(n).

4.3.    Koszty przekazywania parametrów

Zasadniczo w całej książce przyjmujemy, że przekazanie parametru w wywołaniu rekurencyjnym zajmuje stały czas, nawet jeśli przekazujemy N-elementową tablicę. Założenie takie jest słuszne w większości systemów, ponieważ przekazywany jest wskaźnik, a nie cala tablica. W tym problemie rozważamy konsekwencje trzech strategii przekazywania parametrów:

1.    Tablica jest przekazywana przez wskaźnik. Czas = ©(1).

2.    Tablica jest przekazywana przez kopiowanie. Czas = &(N), gdzie N jest rozmiarem tablicy.

3.    Tablica jest przekazywana przez kopiowanie części tablicy potrzebnej w danym wywołaniu. Czas = &(p — q + 1), jeśli jest przekazywana podtablica A[p,.q],

(a)    Rozważmy rekurencyjny algorytm wyszukiwania binarnego zadanej liczby w posortowanej tablicy (patrz zad. 1.3-5). Podaj rekurencję dla pesymistycznego czasu działania wyszukiwania binarnego, gdy tablice są przekazywane przy użyciu każdej z trzech wymienionych powyżej strategii, oraz podaj górne oszacowania na rozwiązanie rekurencji. Niech N będzie rozmiarem oryginalnego problemu, a n - rozmiarem podproblemu.

(b)    Wykonaj jeszcze raz to co w części (a) dla algorytmu Merge-Sort z podrozdz. 1.3.1.

4.4.    Więcej przykładów rekurencji

Podaj asymptotyczne górne oraz dolne oszacowanie dla T(ń) w każdej z danych poniżej rekurencji. Załóż, że T(ń) jest stałą dla n < 2. Twoje oszacowania powinny być tak dokładne, jak to możliwe. Odpowiedzi uzasadnij.

(a)    T(n) = 37\n/2) -f nlgn

(b)    T(ń) = 37’(n/3 + 5) + n/2

(c)    T(n) = 2T(n/2) + n/lgn

(d)    T(ń) = Tin - 1) + 1/n

(e)    T{n) = Tin - i)_+ Ign

(f)    T(ń) = yjnTiJn) + n

Zadania

7.1- 1. Podaj największą i najmniejszą możliwą liczbę elementów w kopcu o wysokości h.

7.1- 2. Pokaż, że n-elementowy kopiec ma wysokość |_lgnj.

7.1- 3. Pokaż, że największy element w poddrzewie kopca znajduje się w korzeniu poddrzewa.

7.1- 4. Gdzie w kopcu można znaleźć element najmniejszy?

7.1- 5. Czy tablica, która jest odwrotnie posortowana, jest kopcem?

7.1- 6. Czy ciąg <23, 17, 14, 6, 13, 10, 1, 5, 7, 12> jest kopcem?

7.2- 1. Zilustruj (podobnie jak na rys. 7.2) działanie procedury Heapify(^,3) dla tablicy A = <27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0>.

7.2- 2. Jaki jest skutek wywołania Heapify(K i), kiedy element A[i] jest większy niż jego synowie?

7.2- 3. Jaki jest skutek wywołania Heapify(z(, i) dla i > heap-size[A]/2?

7.2- 4. Kod dla procedury Heapify jest efektywny, jeśli chodzi o stałe. Jedynie wywołanie rekurencyjne w wierszu 10 może spowodować, że niektóre kompilatory wytworzą nieefektywny kod. Napisz efektywną wersję Heapify, która będzie używać iteracji (pętli) zamiast rekursji.

7.2- 5. Wykaż, że czas działania procedury Heapify na kopcu rozmiaru n w najgorszym przypadku wynosi D(lgn). (Wskazówka: Dla kopca o n węzłach nadaj węzłom wartości, które spowodują rekurencyjne wywołania Heapify dla każdego węzła na ścieżce od korzenia do liścia).

7.3- 1. Zilustruj (podobnie jak na rys. 7.3) działanie procedury Bim.n-HF.AP dla tablicy A = <5, 3, 17, 10, 84, 19, 6, 22, 9>.

7.3- 2. Dlaczego chcemy, żeby indeks i pętli w wierszu 2 procedury Build--Heap zmniejsza! się od \JengtfĄA\j2\ do 1, zamiast zwiększać się od 1 do \Jength[A]l2j ?

7.3- 3. Pokaż, że w n-elementowym kopcu istnieje najwyżej \nj2^h+T\ węzłów o wysokości h.

7.4- 1. Zilustruj (podobnie jak na rys. 7.4) działanie procedury Heapsort dla tablicy A = <5, 13, 2, 25, 7, 17, 20, 8, 4>.

7.4- 2. Jaki jest czas działania algorytmu heapsort dla tablicy A o długości n, która jest już posortowana rosnąco (malejąco)?

7.4- 3. Pokaż, że czas działania algorytmu heapsort wynosi Q{n\gń).

7.5-1. Zilustruj (podobnie jak na rys. 7,5) działanie procedury HEAP--INSERTC4, 3) dla kopca A = <15, 13, 9, 5, 12, 8, 7,4, 0, 6,2,1>.

Rys. 75. Działanie procedury Heap-Insert. (a) Kopiec zrys. 7.4(a) zanim wstawimy do niego węzeł z kluczem 15. (b) Nowy l&ć zostaje dodany do kopca, (c) WartoŚd na śdcżce z nowego Kicia do korzenia są kopiowane w dół, aż znajdzie się miejsce na klucz 15. (d) Klucz 15 jest wstawiony

7.5- 2. Opisz działanie procedury HEAP-E?rrRACT-MAX dla kopca A = <15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1>.

7.5- 3. Pokaż, jak za pomocą kolejki priorytetowej zaimplementować zwykłą kolejkę (FIFO) i jak zaimplementować stos. (Kolejki FIFO i stosy są zdefiniowane w podrozdz. 11.1).

7.5- 4. Podaj działającą w czasie O(lgn) implementację procedury Heap--INCREase-KEY(^, i, k), która podstawia A[i] <- max(/i[i], k) i odpowiednio zmienia strukturę kopca.

7.5- 5. Procedura Heap-Delete(.4, i) usuwa element w węźle i z kopca A. Podaj implementację Heap-Delete, która działa w czasie 0(lgń) dla n-elementowego kopca.

7.5- 6. Podaj algorytm działający w czasie 0(n lg k) służący do scalania k posortowanych list, gdzie n jest łączną liczbą elementów na Ustach. (Wskazówka: Użyj kopca do k-krotnego scalania).

8.1- 1. Zilustruj (podobnie jak na rys. 8.1) działanie procedury Partition dla tablicy A = <13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21>.

8.1- 2. Jaką wartość ą zwraca procedura PARTITION, gdy wszystkie elementy A[p.. r] mają taką samą wartość?

8.1- 3. Podaj krótkie uzasadnienie faktu, że czas działania procedury Partition dla podtablicy o rozmiarze n wynosi ©(«).

8.1- 4. Jak zmienić procedurę QuiCKSORT, żeby sortowała w porządku nierosnącym?

8.2- 1. Pokaż, że czas działania procedury Quicksort wynosi ©(nlgn), gdy wszystkie elementy tablicy A mają taką samą wartość,

8.2- 2. Pokaż, że czas działania procedury QuiCKSORT wynosi 0(n²), kiedy tablica A jest posortowana w porządku nierosnącym,

8.2- 3. Banki często zapisują operacje dokonywane na rachunku w kolejności ich przeprowadzania, ale wiele osób lubi otrzymywać swoje wyciągi bankowe z wydatkami zapisanymi w kolejności numerów zrealizowanych czeków, Ludzie na ogól wypisują czek za czekiem z książeczki, a sprzedawcy realizują je dość szybko. Problem zamiany kolejności zgodnej z czasem przeprowadzania operacji na kolejność zgodną z numerami czeków jest zatem problemem sortowania prawie posortowanych danych. Uzasadnij, że procedura INSERTION-SORT lepiej niż Quicksort nadaje się do rozwiązywania tego problemu,

8.2- 4. Załóżmy, że podziały na każdym poziomie algorytmu ąuicksort są dokonywane w stosunku 1 — a do a, gdzie 0 < a ^ 1/2 jest stalą. Pokaż, że najmniejsza głębokość liścia w drzewie rekursji wynosi około — lgn/lg(l — a). (Nie przejmuj się zaokrąglaniem do liczb całkowitych).

B.2-5. Pokaż, że dla każdego stałego 0 < a < 1/2 prawdopodobieństwo tego, że dla dowolnej tablicy danych wejściowych procedura Partition utworzy podział bardziej zrównoważony niż 1 — a do a, wynosi około 1 — 2a. Dla jakiej wartości a prawdopodobieństwo otrzymania zrównoważonego podziału wynosi 1 /2?

8.3- 1. Dlaczego analizujemy średni czas działania algorytmu probabilistycznego, a nie jego pesymistyczny czas?

8.3- 2. Ile wywołań generatora liczb losowych Random jest wykonywanych podczas działania Randomized-Quicksort w przypadku najgorszym? Jak zmieni się odpowiedź, gdy rozpatrzymy przypadek najlepszy?

*    8.3-3. Napisz implementację procedury Random(o, b), która korzysta tylko

z rzutów symetryczną monetą. Jaki jest oczekiwany czas działania Twojej procedury?

*    8.3-4. Podaj probabilistyczną procedurę, działającą w czasie ©(n), której dane

wejściowe stanowi tablica A[l.. n] i która wykonuje losową permutację elementów tablicy.

9.1- 1. Jaka jest najmniejsza możliwa głębokość liścia w drzewie decyzyjnym odpowiadającym algorytmowi sortującemu za pomocą porównań?

9.1- 2. Wyprowadź dokładne oszacowanie asymptotyczne na lg(n!), nie korzys-

n

tając ze wzoru Stirlinga. Oblicz w tym celu sumę ^ Igjt, używając metod

* = i

z podrozdz. 3.2.

9.1- 3. Wykaż, że nie istnieje algorytm sortujący za pomocą porównań, który działa w czasie liniowym dla co najmniej połowy z «! możliwych, istotnie różnych danych długości n. Czy odpowiedź ulegnie zmianie, jeśli zapytamy o ułamek l/n(l/2ⁿ) wszystkich danych długości n?

9.1- 4. Profesor Solomon twierdzi, że dolna granica D(«lg«) na sortowanie n liczb nie dotyczy jego komputera, w którym sterowanie w programie może podjąć jedną z trzech dróg po każdym porównaniu a_t: a_p w zależności od tego, który z trzech możliwych wyników został stwierdzony: a_t < a a_{ = Oj czy a. > a_y Wykaż, że profesor nie ma racji. W tym celu udowodnij, że liczba nowego rodzaju porównań, potrzebnych do posortowania n elementów, wynosi D(nlgn).

9.1- 5. Udowodnij, że w pesymistycznym przypadku potrzeba 2n — 1 porównań, aby scalić dwie posortowane listy zawierające po n elementów.

9.1- 6. Niech dany będzie ciąg n elementów do posortowania. Ciąg wejściowy składa się n/k podciągów, po k elementów w każdym. Elementy w każdym podciągu są mniejsze niż elementy w następnym podciągu oraz większe od elementów w poprzednim podciągu. Aby więc posortować cały ciąg o długości n, wystarczy posortować każde k elementów we wszystkich n/k podciągach. Wykaż, że dolna granica na liczbę porównań wykonywanych w tym wariancie problemu sortowania wynosi D(nlg£). (Wskazówka: Proste zsumowanie dolnych ograniczeń na posortowanie poszczególnych podciągów nie jest poprawnym dowodem tego dolnego ograniczenia).

9.2- 1. Zilustruj (podobnie jak na rys. 9.2) działanie procedury Counting--Sort dla tablicy A — <7, 1, 3, 1, 2, 4, 5, 7, 2, 4, 3).

9.2- 2. Wykaż, że procedura COUNTING-SORT sortuje stabilnie.

9.2- 3. Zmodyfikujmy pętlę for w wierszu 9 procedury Counting-Sort w następujący sposób:

9 for j <- 1 to length[A]

Wykaż, że algorytm nadal działa poprawnie. Czy nowa wersja algorytmu zapewnia stabilność?

9.2- 4. Załóżmy, że algorytm sortowania powinien umieszczać posortowany ciąg bezpośrednio na wyjściu. Zmodyfikuj procedurę COUNTING-SORT tak, aby wypisywała posortowany ciąg, nie zajmując więcej pamięci niż potrzeba dla tablic A i C. (Wskazówka: Połącz elementy z A o tej samej wartości klucza w listy. Gdzie można znaleźć „wolne” miejsce na przechowywanie wskaźników listy z dowiązaniami?)

9.2- 5. Zaprojektuj algorytm, który dla danych n liczb z przedziału od 1 do k wykonuje wstępne obliczenia, a następnie na podstawie obliczonych danych pozwala w czasie 0(1) określić, ile z danych « liczb leży w przedziale [a..b]. Twój algorytm powinien wykonywać wszystkie potrzebne obliczenia wstępne w czasie 0(n + k).

9.3-1. Zilustruj (podobnie jak na rys. 9.3) działanie procedury Radix-Sort dla następującego ciągu angielskich słów: COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOK

9.3- 2. Które z następujących algorytmów sortujących są stabilne: sortowanie przez wstawianie, sortowanie przez scalanie, sortowanie przez kopcowa-nie, sortowanie szybkie? Podaj metodę, która z dowolnego algorytmu sortującego tworzy stabilny algorytm sortujący. Ile dodatkowej pamięci i czasu wymaga zastosowanie Twojej metody?

9.3- 3. Udowodnij przez indukcję poprawność sortowania pozycyjnego.

W którym miejscu dowodu potrzebne jest założenie, że pomocniczy algorytm sortowania jest stabilny?

9.3- 4. Skonstruuj algorytm, który pozwala posortować n liczb całkowitych z przedziału od 1 do n² w czasie 0(n).

*9.3-5. Ile faz potrzeba w najgorszym przypadku do posortowania ^-cyfrowych liczb, jeśli zastosujemy pierwszy z opisanych algorytm sortujący karty? Ile może się w tym czasie pojawić tymczasowych plików kart?