Zestaw zadań.
1. Określić niezmienniki pętli i dokonaj analizy poprawności (częściowej, całkowitej)
algorytmu, liniowego przeszukiwania tablicy ze względu na wystąpienie elementu o
kluczu x. Wyznaczyć wrażliwość pesymistyczną i oczekiwaną algorytmu.
2. Dokonać analizy poprawności algorytmu Euklidesa wyznaczania WD ( ajwiększego
Wspólnego Dzielnika) dwóch liczb naturalnych a, b. Do zbudowania niezmienników
iteracji skorzystaj z następujących własności: WD(a,b)= WD(a-b,b); WD(a,b)=
WD(b,a); WD(a,a)=a
3. Zbudować stabilny algorytm sortowania  przez wybór oraz algorytm sortowania
 bąbelkowego o optymistycznej złożoności obliczeniowej.
4. Znalez
ć rekurencyjnie minimalny i maksymalny element tablicy. Zastosować technikę
 dziel i rządz
 . Dokonać analizy złożoności obliczeniowej algorytmu.
5. Obliczyć rekurencyjnie wartość log(n!).
6. Wyznaczyć wartość n-tego wyrazu ciągu Fibonacciego metodą programowania
dynamicznego. Wyznaczyć złożoność obliczeniową algorytmu.
7. Zbudować rekurencyjny algorytm, który dla danego znaku sprawdzi czy występuje w
danym napisie, obliczy liczbę jego wystąpień oraz usunie jego wystąpienia.
8. Wypełnić  po spirali dwuwymiarową tablicę wartościami tworzącymi ciąg arytmetyczny
o zadanym wyrazie początkowym i zadanej różnicy ciągu. Rozpatrzyć przypadek
wypełnienia zaczynając od dowolnego elementu skrajnego oraz środkowego. Zbudować
algorytm iteracyjny i rekurencyjny.
9. Sprawdzić rekurencyjnie, czy określone słowo i zdanie są palindromami.
10. Zaprojektować algorytm działający w czasie O(n), który dla danego zbioru S parami
różnych n kluczy oraz liczby dodatniej k<=n wyznacza k liczb w S, które są najbliższe
medianie zbioru S.
11. Zastosować rekurencję do wygenerowania wszystkich n! permutacji zbioru X={1, 2, ...,
n} w porządku leksykograficznym (antyleksykograficznym).
12. Zbudować algorytm rekurencyjny do rozwiązania tzw. problemu  wież Hanoi .
13. Metodą podstawiania rozwiązać równania rekurencyjne. Za pomocą indukcji udowodnić
ich poprawność:
T(n) = 2T(n-1) + 1 dla n e" 2, T(1) = 2
T(n) = 2T(n-1) + n dla n > 1, T(1) = 1
14. Rozwiązać równania rekurencyjne zakładając, że T(1)=1, natomiast dla n>1zachodzi:
T(n) = 2T(n/2) + (n-1)
T(n) = nT(n-1) + n!
T(n) = 8T(n/2) + n3
15. Uporządkować pod względem tempa wzrostu następujące funkcje:
lg n n
lg n n lg n
n ; ; 2 n ; n ; lg n ; n / lg n ; ; ; ;
(n / 2 ) (3 / 2 )
2 2 n
16. Dla rekurencyjnego algorytmu sortowania  szybkiego (Quick_sort) podać i rozwiązać
równanie rekurencyjne. Określić złożoność pesymistyczną i optymistyczną algorytmu.
17. Udowodnić, że złożoność obliczeniowa procedury podziału (Partition) algorytmu
Quick_sort jest rzędu O(n).
18. Wykazać, że złożoność algorytmu Quick_sort wynosi Ś(nlgn), gdy wszystkie elementy
tablicy mają taką samą wartość oraz Ś(n2), gdy uporządkowanie początkowe jest
odwrotne względem kryterium sortowania.
19. Udowodnić, że złożoność obliczeniowa algorytmu sortowania kopcowego Heap_sort
wynosi O(nlgn).
20. Wykazać, że n-elementowy kopiec ma wysokość lgn oraz, że istnieje co najwyżej n/2h+1
węzłów o wysokości h.
21. Przedstawić tablicową reprezentację kopca. Utworzyć algorytmy (oraz podać ich
złożoność obliczeniową) do realizacji operacji: Insert, DeleteMax, Max.
22. Utworzyć procedury poprawiające kopiec  w dół i  w górę .
23. Zbudować algorytm sortowania przez scalanie (Merge_sort) i zastosować do
posortowania elementów tablicy. Podać równanie rekurencyjne i złożoność obliczeniową
algorytmu.
24. Przedstawić algorytm o liniowej złożoności obliczeniowej, który dwa ciągi liczb
posortowanych niemalejąco łączy w jeden posortowany ciąg.
25. Zastosować ideę algorytmu Shella do posortowania elementów tablicy, wykorzystać
elementy algorytmu Insert_Sort. Przedstawić analizę złożoności obliczeniowej algorytmu
sortowania Shella.
26. Dokonać analizy algorytmu sortowania Shella pod kątem stabilności.
27. Wstawić na n-tą pozycję listy nowy element. Założyć można, że lista posiada co najmniej
n elementów.
28. Pojedyncza, niepusta lista jednokierunkowa zakończona jest cyklem. Wyznaczyć ilość
elementów w cyklu.
29. Wyznaczyć liczbę elementów listy cyklicznej, mając wskaz
nik do jednego z elementów
listy.
30. Dwie pojedyncze listy jednokierunkowe zawierają niepowtarzające się liczby naturalne
posortowane rosnąco. Przekształcić te listy w jedną listę, której elementy są posortowane
rosnąco. Listy wejściowe są usuwane z pamięci.
31. W liście jednokierunkowej usunąć powtarzające się elementy. Założyć można, ze lista jest
niepusta.
32. W dwuwymiarowej tablicy większość elementów jest równa zero. Utworzyć strukturę
dynamiczną (wskaz
nikową) przechowującą w sposób efektywny (pod względem
wykorzystania pamięci) zawartość tablicy.
33. Lista jednokierunkowa reprezentuje wielomian zadanego stopnia o współczynnikach
całkowitych. Elementy na liście ułożone są według rosnących potęg. Obliczyć różnicę
dwóch wielomianów zadanego stopnia i znalez
ć reprezentację listową.
34. Wyznaczyć rekurencyjnie długość listy.
35. Dla danych wskaz
ników x, y wskazujących elementy dwóch rozłącznych list cyklicznych
wstawić listę wskazywaną przez y do listy po elemencie wskazywanym przez x.
36. W liście dwukierunkowej zwolnić każdy parzysty węzeł.
37. Złączyć dwie posortowane listy wykorzystując pojęcie wartownika.
38. Odwróć kolejność elementów listy dwukierunkowej.
39. Ustawić elementy na stosie w porządku rosnącym, używając jednego pomocniczego stosu
i kilku zmiennych.
40. Podać rekurencyjne algorytmy przechodzenia drzewa BST w porządku preorder, inorder
oraz postorder.
41. Utworzyć drzewo BST z uporządkowanej tablicy.
42. Wyznaczyć liczbę węzłów w drzewie binarnym, liczbę liści i wysokość drzewa.
43. Usunąć wszystkie liście z drzewa binarnego.
44. Zbudować algorytm, który dla danej pary kluczy przejrzy drzewo BST i wypisze
wszystkie klucze znajdujące się między nimi.
45. Przekształć drzewo BST w linię oraz linię w drzewo zrównoważone.