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. Znaleźć rekurencyjnie minimalny i maksymalny element tablicy. Zastosować technikę

„dziel i rządź”. 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 ≥ 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) + n

3

15. Uporządkować pod względem tempa wzrostu następujące funkcje:

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 Θ(n

2

), 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/2

h+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 wskaź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ą (wskaźnikową) przechowującą w sposób efektywny (pod względem
wykorzystania pamięci) zawartość tablicy.

;

;

;

;

lg

/

;

lg

;

;

2

;

;

lg

lg

lg

)

2

/

3

(

)

2

/

(

2

2

n

n

n

n

n

n

n

n

n

n

n

n

n

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 znaleźć reprezentację listową.

34. Wyznaczyć rekurencyjnie długość listy.

35. Dla danych wskaź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.