kolp1

AISDE - Kolokwium 23 listopada 2009 - godz. 16	Podpis:
Zadanie 1 (5p)
Dane: liczba całkowita nicujcmna n Wynik: liczba całkowita s function s = alg(n) s=n; while s>0 s=s-1; end Dla podanego algorytmu określić wzorami analitycznymi złożoności czasowe t-(n), t.(n), t>(n), jeśli operacją dominującą jest odpowiednio przypisanie, odejmowanie i porównanie. Niech m będzie długością bitową n i t_(m)= ®(g(m)). Określić najprostszą postać g(m).	t-(n)=.............................................(lp) t(n)=,.........V)............................................(lp) t>(n)=............................................(lp) g(rn)=.........oh...........................................(^2P)
Zadanie 2 (5p)
Pewien algorytm ma złożoność czasową: , . (n-2)^ dla 0 < n < 2 t(n) = I n-2 dla n> 2 Określić takie najprostsze g(n), że t(n)= 0(g(n)). Udowodnić prawdziwość tego oszacowania asymptotycznie dokładnego za pomocą twierdzenia o granicy.	8(n)=...........V.)................... Hm - 4
Zadanie 3 (5p)
Mamy dwa ciągi: a, b, stanowiące pewne permutacje ciągu {1,2,3,4}. Sortujemy je algorytmem insertionsort z wartownikiem. Sortowanie a wymaga 9 porównań, sortowanie b wymaga 3 porównania. Określić ciągi a, b. Tle porównań wymaga sortowanie tych ciągów- algorytmem selectionsort?	a = .............(i.5p) b - Ą.AA..2.+3..i..hh........(i.5P) c tsclcctionsort(^a)^—..................................Op) G tsclcctionsort(b)^- ..................................(1 P)
Zadanie 4 (5p) , _ . *>,
a=[l,2,3,4,5]. Operacja b=buildheap(a) wymaga // porównań elementów tablicy. Operacja c^ąuicksort(a) wymaga ^-krotnego wy- • wołania partition. Pierwszy przebieg radix-sort(a) przetwarza tablicę a w tablicę t. Ciąg a/10 posortowano za pomocą bucketsort: liczba pustych kubełków wynosi p, a maksymalna liczba elementów w^r kubełku q. Określić b, //, k, typ, q.	n=........................................(ip) k=,........hl................................(lp) kiH(4 ź---i -t=Ą .......(lp) p=.........—..................................(lp) <r.......4L...................................(^[p)_