zoradene prednasky

Návrat na detail prednášky / Stiahnuť prednášku / Univerzita Komenského / Fakulta matematiky, fyziky a informatiky / Algoritmy a dátove štruktúry

 

Skúšky (algoritmy.doc)

Datum a cas:   12-JAN-1998 10:48

Vec:           Algoritmy, 8.1.

 

Skuska z algoritmov vyzera nasledovne:

 1. pisomka - dve hodiny, 10 prikladov

 2. posle vas domov, uda termin vysledkov

 3. o jeden - dva dni su vysledky - posedenie u neho v kancelarii, vidite

    obodovanu pisomku, nestacite sa cudovat, kolko mate bodov (viac ako si

    myslite), kratky priatelsky rozhovor (od temy) a zapisana znamka.

 

A tu su zadania nasich uloh:

1. Dokaz vetu: f(n) = theta(g(n)) <=> f(n) = O(g(n)) && f(n) = omega(g(n))

2. Pouzi master theorem na T(n) = 4T(n/2) + n^3

3. Dokaz, ze heapsort je omega(n lg n)

4. Dokaz, ze counting-sort je stabilne triedenie.

5. Implementuj dva zasobniky v jednom poli s casmi O(1)

6. Uvazujme metodu delenia pri hasovani zretazenim, kde h(k) = k mod m,

   kde m=2^p-1 a k je znakovy retazec interpretovany v ciselnom zaklade 2^p.

   Ukaz, ze ak retazec x moze byt odvodeny z retazca y permutaciou jeho

   znakov, potom sa x a y hasuju na tu istu poziciu. Ukaz priklad aplikacie,

   kedy tato vlastnost hasovacej funkcie je nanajvys nevhodna.

7. Casy vypoctu algoritmu, ktory cisla najskor insertuje do binarneho stromu a

   potom ich vypise v usporiadanom poradi (inorder) v najlepsom a najhorsom

   pripade.

8. Dokaz, ze v matrix-chain-order algoritme je

    suma(i,j od 1 po n) R(i,j) = (n^3-n)/3

   vyuzitim suma(i od 1 po n) i^2 = n*(n+1)*(2n+1)/6

   R(i,j) je pocet odvolani sa na miesto tabulky (i,j)

9. Nie kazdy greedy pristup k problemu vyberu aktivit nam dava najvacsiu

   mnozinu vzajomne kompatibilnych aktivit. Ukaz priklad, kedy vyber aktivit

   na zaklade najkratsieho trvania z tych, ktore su kompatibilne

   s predchadzajucimi nefunguje.

10. Najdi co najtesnejsie asymptoticke ohranicenia:

    T(n) = 7*T(n/2) + n^2

    T(n) = 2*T(n/4) + sqrt(n)

    T(n) = T(n-1) + lg n

    T(n) = sqrt(n)*T(sqrt(n)) + n

 

Povodna sprava:

 

Datum a cas:    4-JAN-1997 10:06

Vec:           Algoritmy - skuska 3.1.

 

Ahojte,

 

na prosbu viacerych z Vas pisem znenie zadani skusky z algoritmov (v zatvorke

za priklodom je vzdy pocet bodov zan).

Nebolo to az take tazke tazke, ale casovo pomerne narocne, tak sa na to

pripravte. Napriklad pri siestich maticiach je MATRIX-CHAIN v case O(n^3)...

Takze tak:

 

1. Nech f(n), g(n) su asymptoticky nezaporne fcie. Pomocou zakladnej definicie

theta-notacie dokazte, ze

                                max{f(n),g(n)} = theta(f(n)+g(N))         (8)

 

2. Pouzite metodu master theorem (hlavna veta) na zistenie tesnych

asymptotickych ohraniceni pre rekurenciu

                                                T(N) = 4 T(n/2) + n^2    (10)

 

3. Ukazte, ze cas vypoctu algoritmu HEAPIFY je v nojhorsom pripade

omega(lg n). (Pomoc: Pre haldu s n uzlami zadaj take hodnoty uzlov, ktore

sposobia, ze HEAPIFY bude volane rekurzivne v kazdom uzle na ceste od korena

k listu.)                                                                (10)

 

4. Cas vypoctu algoritmu quicksort je mozne v praxi vylepsit, ak vezmeme

do uvahy, ze insertsort triedi velmi rychlo postupnosti, ktore su uz "skoro"

utriedene. Ak volame quicksort na podpoli s mensim poctom prvkov nez k prvkov,

tak ich nechame nezmenene a vratime sa bez triedenia. Ked skonci praca alg.

quicksort, tak spustime alg. insertsort na ukoncenie triedenia. Zdovodnite, ze

ocakavany cas vypoctu tohto triediaceho algoritmu je O(nk + n log(n/k)).

Ako vybrat vhodne k teoreticky a prakticky?                              (10)

 

5. Nech a=<a0,a1,...,ar> oznacuje postupnost r+1 prvkov vybratych nahodne

z mnoziny {0,1,...,m-1}. Definujme prislusnu hasovaciu funkciu ha z H

 

        ha(x) = suma od i=0 po r ( ai*xi) mod m                        (*)

 

kde x=<x0,x1,...,xr> je rozpis x do r+1 bitovych retazcov rovnakej dlzky.

Ukazte, ze ak bude kazda zlozka ai z a v rovnici (*) rozna od nuly, potom

mnozina H z definicie

                        H = zjednotenie cez a ({ha})

nie je univerzalna.                                                      (12)

 

6. Prehladavanie BP-stromu metodou INORDER mozno vykonat tak, ze najdeme

minimalny prvok pomocou algoritmu TREE-MINIMUM a potom pouzitim n-1 volani

algoritmu TREE-SUCCESSOR. Dokazte, ze tento algoritmus bezi v case theta(n).

                                                                         (9)

 

7. Najdite optimalne uzatvorkovanie sucinu maticoveho retazca, ktoreho

postupnost rozmerov je <15,12,40,25,7,30,10>.                            (10)

 

8. Dokazte, ze zlomkovy problem batohu ma vlastnost greedy vyberu.        (8)

 

9. Zostrojte RB-strom, ktory bude vysledkom po postupnom vkladani klucov

87,93,58,129,27,81,138,72 do povodne prazdneho RB-stromu.                (10)

 

10. PREMIA - PRIKLADY REKURENCII

 

Odvodte asymptoticky horne a dolne ohranicenia pre T(n) v kazdej

z nasledujucich rekurentnych rovnic. Predpokladajme, ze T(n) je konstanta

pre n<=2. Najdite co najtesnejsie ohranicenia a zdovodnite vase riesenie:

 

a)   T(n) = 7 T(n/2) + n^2

b)   T(n) = 2 T(n/4) + sqrt(n)

c)   T(n) = T(n-1) + lg n

d)   T(n) = sqrt(n) * T(sqrt(n)) + n                                     (13)

 

Povodna sprava:

 

Datum a cas:   21-JAN-1997 13:38

Vec:           algoritmy 21.1.

 

1. klasika: max(f(n),g(n))=theta(f(n)+g(n))

                               

2. Ukazte (pomocou substitucnej metody), ze riesenie T(n)=2T(n/2)+n je

omega(n.lg n). Mozno z toho urolbit zaver, ze riesenie je theta(n lgn)?

 

3. Kde v halde je najmensi prvok?

 

4. h(k)=k mod 9, kolizie zretazenim. Ukazte vkladanie klucov 5, 28,

19, 15, 20, 33, 12, 17, 10

 

5. Napiste NErekurzivnu proceduru pracujucu v case O(n), ktora pre

dany n uzlovy binarny strom vypise hodnotu kazdeho kluca (pouzit

zasobnik).

 

6. Bol nakresleny RB-strom. Ukazat postupne vymazavanie vsetkych

vrcholov v danom poradi.

 

7. Optimalne uzatvorkovanie sucinu matic...

 

8. Popiste datovu strukturu, ktora bude vbysledkom po absorbovani

cervenych deti do ich ciernych rodicov v RB-strome, pricom cierny

rodicia akceptuju za svoje: deti svojich cervenych deti (podla mojho

skromneho nazoru to bude B-strom).

 

9. Dokazte, ze pri optimalnom kode, ak su znaky usporiadane tak, ze

ich frekvencie su nerastuce, potom dlzky ich kodov su v nerastucom

poradi.

 

10. PREMIA priklady rekurencii:

a) T(n)=16T(n/4)+n^2

b) T(n)=7T(n/3)+n^2

c) T(n)=T(n-1)+n

d) T(n)=2T(sqrt(n))+1.

 

Sent:        5. januára 2000 17:54

Subject:        DSA 5.1.2000

 

2h pisomka

Odporucam preratat si priklady z minulych rokov ...

 

1. Nech f(n) a g(n) su asymptoticky nezaporne fcie. Pomocou zakladnej

definicie

   Theta - notacie dokazte, ze

   max (f(n),g(n))= Theta (f(n)+g(n))

 

2. Najdite riesenie rekurentnej rovnice

   T(n) = 2T( sqrt(n)) + 1

   pouzitim zmeny premennej; netrap sa teraz tym, ci su argumenty cele

cisla

 

3. Ukazte, ze najvecsi prvok v podstrome haldy lezi v koreni tohto

podstromu.

 

4. Popis algoritmus, ktory ma na vstupe n celych cisel z intervalu <1..k>,

tieto cisla

   najprv predspracuje aby potom mohol odpovedat na lubovolnu otazku typu:

  "Kolko z n celych cisel padne do intervalu <a..b> ?" v case O(1). Tento

   algoritmus by mal fazu predspracovania spocitat v case O(n+k)

 

5. Ktore z nasledujucich triediacich algoritmov su stabilne: insertsort,

mergesort,

   heapsort, quicksort a countingsort ? Nacrtnite jednoduchy sposob, ako

urobit

   lubovolne triedenie stabilnym.

 

6. Nakresli postupnost medzivysledkov na ilustraciu operacie Quick-sort

   aplikovanej na pole.

   A=<5,3,17,10,84,19,6,22,9>.

 

7. Vyuzi vlastnost BP-stromu na rigorozny (presny) dokaz toho, ze kod

algoritmu

   Tree-Successor je spravny.

 

8. Nech R(i,j) je pocet odvolani sa na prvok m[i,j] algoritmom

   MATRIX-CHAIN-ORDER pri vypocte dalsich prvkov tabulky. Ukaz, ze

   celkovy pocet odvolani sa pre celu tabulku je

   n         n

  Suma  Suma  R(i,j) = (n^3-n) / 3

   i=1      j=1

                                   n

   Skus vyuzit identitu  Suma i^2 = n (n+1) (2n+1) / 6

                                   i=1

 

9. Zostrojte RB-strom, ktory bude vysledkom po postupnom vkladani klucov

  17,41,38,31,12,19,8,35,10 do povodneho prazdneho RB-stromu

 

10. Premia - Priklady Rekurencii

  Odvod asymptoticke horne a dolne ohranicenie pre T(n) v kazdej z

nasledujucich

  rekurentnych rovnic. Predpokladajme, ze T(n) je konstanta pre n<=2. Najdi

co

  najtesnejsie ohranicenia, a zdovodni tvoje riesenie:

  a) T(n) = 7 T(n/2) + n^2

  b) T(n) = 2 T(n/4) + sqrt(n)

  c) T(n) = T(n-1) + lg n

  d) T(n) = sqrt(n) T(sqrt(n)) + n

 

Tot vsjo, byeeeeeee

                                       Pichtik

 

 

Sent:        14. januára 2000 13:16

Subject:        algoritmy 14. 1. 19100

 

1. dokaz, ze pre lub. konstanty a, b, kde b>0, plati (n+a)^b=theta(n^b)

 

2. cas vypoctu je theta(g(n)) <-> najhorsi pripad je O(g(n)) a najlepsi

  OMEGA(g(n))

 

3. ukaz, ze heapsort je OMEGA(g(n))

 

4. cas vypoctu quicksort sa da vylepsit, ak netriedime podpolia mensie ako k

  a nakoniec pouzijeme insert sort. O(nk+log2(n/k)). dokaz a vyber vhodne k.

  (ja som si povedal T(n)=c1*nk+c2*n*log2(n/k) a minimum som nasiel derivaciou)

 

5. n-prvkova halde ma vysku (int) log2(n)

 

6. hashing zretazenim, h(k)=k mod m, m=2^p-1. k je retazec znakov pri zaklade

  2^p. dokaz, ze permutacie znakov k maju rovnaku h(k).

  (dokazete, ze h(k) je kongruentna so suctom znakov modulo 2^p-1. presne ako

  dokaz kriteria delitelnosti 9)

 

7. triedenie: vkladame postupne do stromu a nakoniec vypiseme cez inorder.

  najdi najlepsi a najhorsi pripad.

 

8. najdi optimalne ozatvorkovanie matic s rozmermi <5, 10, 3, 12, 5, 50, 6>

  (tieto priklady fakt preskakujte, trva to asi hodinu)

 

9. ukaz, ze greedy postup vyberania co najkratsich aktivit nie je optimalny.

  (napr. aktivity (0,5) (4,7) (6, 12))

 

10. utried kopu funkcii podla radu rastu. najzaujimavejsie boli podla mna

   (lg n)! a n^(1/lg n). ostatne boli v pohode.

 

m.