ALGORITMI SI STRUCTURI DE DATE

PROBLEME PROPUSE I. Elemente de teoria analizei algoritmilor I.1. Aspecte generale privind analiza şi complexitatea unui algoritm; I.2. Evaluarea complexităţii. Exemple de analiză a unor algoritmi. Clase de complexitate. I.3. Algoritmi iterativi si algoritmi recursivi. Avantaje si dezavantaje. I.4. Introducere in proiectarea algoritmilor. 1. Complexitatea algoritmului pentru determinarea minimului/maximului separat/simultan dintr-un tablou nevid. 2. Complexitatea algoritmului de cautare liniara a unui element intr-un tablou unidimensional cu n elemente. 3. Complexitatea algoritmului de cautare binara a unui element intr-un tablou unidimensional cu n elemente sortate. 4. Complexitatea algoritmilor de explorare a tablourilor bidimensionale 5. Sa se rezolve urmatoarele relatii de recurenta:

a) f(n) = nf(n-1), f(0)=1, n>0. b) f(n) = f(n-1)+1, f(0)=0, n>0. c) f(n) = cf(n-1), c constanta, f(0) = k, n>0. d) f(n) = f(n-1) + f(n-2), f(0)=0, f(1) = 1, n>1. e) f(n)=bn f(n-1), n>0, (bn) este un sir dat, iar f(0) = k. f) Sa se determine f(n), daca (f(n))2 = c (f(n-1))2, unde c este o constanta data, iar f(0) = k. g) f(n) = f(n-1) + 9n2, f(0) = 0, n>0. h) f(n) = 7f(n-1) + 9 (5n), f(0) = 3, n>0. i) f(n) = 7f(n-1) +9 (7n), f(0) = 3, n>0. j) f(n) = 6f(n-1) – 9f(n-2), f(0) = 1, f(1) = 2, n>1. k) f(n) = 2f(n-1) -4f(n-2), f(0)=1, f(1) = 3, n>1.

6. Complexitatea algoritmului pentru simularea unui circuit combinational cu n intrari (Evaluarea unei functii booleene simple pentru toate cele 2n combinatii posibile). 7. Complexitatea algoritmilor pentru calculul determinantului unei matrice patratica. 8. Complexitatea algoritmilor pentru generarea tuturor permutarilor. 9. Complexitatea algoritmului pentru evaluarea functiei Ackermann. 10. Complexitatea algoritmilor de sortare: selectie, insertie (directa/ prin cautare binara), interclasare, partitionare binara (qsort), heapsort (sortarea folosind structuri heap). II. Metode de sortare: interschimbare, interclasare, insertie, sortare rapida, alte metode

• Metoda interschimbarii (Bubble sort) [1, pag 11], [3, pag. 64-69]; 11. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare pentru o structura de date tablou alocat static 12. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare pentru o structura de date tablou alocat dinamic (folosind malloc). 13. Implementati metoda de sortare folosind numai structuri de control for.

14. Implementati metoda de sortare folosind numai structuri de control while si do…while. 15. Analizati complexitatea metodei in cazul cel mai defavorabil. 16. Aplicati metoda de sortare asupra unui sir specificat si pe baza functiei C descrise vedeti ce rezultat se obtine la pasul k (k fiind cel putin 2).

• Metoda selectiei (min, max, min-max, heap) [3, pag. 69-74], [1, pag. 97-98, 192-196];

17. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare sel_min pentru o structura de date tablou alocat static 18. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare sel_min pentru o structura de date tablou alocat dinamic (folosind malloc). 19. Implementati metoda de sortare sel_min folosind numai structuri de control for. 20. Implementati metoda de sortare sel_min folosind numai structuri de control while si do…while. 21. Analizati complexitatea metodei sel_min in cazul cel mai defavorabil. 22. Aplicati metoda de sortare sel_min asupra unui sir specificat si pe baza functiei C descrise vedeti ce rezultat se obtine la pasul k (k fiind cel putin 2). 23. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare sel_max pentru o structura de date tablou alocat static 24. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare sel_max pentru o structura de date tablou alocat dinamic (folosind malloc). 25. Implementati metoda de sortare sel_max folosind numai structuri de control for. 26. Implementati metoda de sortare sel_max folosind numai structuri de control while si do…while. 27. Analizati complexitatea metodei sel_max in cazul cel mai defavorabil. 28. Aplicati metoda de sortare sel_max asupra unui sir specificat si pe baza functiei C descrise vedeti ce rezultat se obtine la pasul k (k fiind cel putin 2). 29. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare sel_min_max pentru o structura de date tablou alocat static 30. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare sel_min_max pentru o structura de date tablou alocat dinamic (folosind malloc). 31. Implementati metoda de sortare sel_min_max folosind numai structuri de control for. 32. Implementati metoda de sortare sel_min_max folosind numai structuri de control while si do…while. 33. Analizati complexitatea metodei sel_min_max in cazul cel mai defavorabil. 34. Aplicati metoda de sortare sel_min_max asupra unui sir specificat si pe baza functiei C descrise vedeti ce rezultat se obtine la pasul k (k fiind cel putin 2). 35. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare sel_heap pentru o structura de date tablou alocat static 36. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare sel_heap pentru o structura de date tablou alocat dinamic (folosind malloc). 37. Implementati metoda de sortare sel_heap folosind numai structuri de control for. 38. Implementati metoda de sortare sel_heap folosind numai structuri de control while si do…while. 39. Analizati complexitatea metodei sel_heap in cazul cel mai defavorabil. 40. Aplicati metoda de sortare sel_heap asupra unui sir specificat si pe baza functiei C descrise vedeti ce rezultat se obtine la pasul k (k fiind cel putin 2).

• Metoda insertiei directe [3, pag. 63, 64], [1, pag. 64-65]. O varianta mai rapida

a metodei foloseste cautarea binara [1, pag. 98] pentru a stabili locul insertiei. Se obtine algoritmul descris in [1, pag. 136];

41. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare ins_dir pentru o structura de date tablou alocat static 42. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare ins_dir pentru o structura de date tablou alocat dinamic (folosind malloc). 43. Implementati metoda de sortare ins_dir folosind numai structuri de control for. 44. Implementati metoda de sortare ins_dir folosind numai structuri de control while si do…while. 45. Analizati complexitatea metodei ins_dir in cazul cel mai defavorabil. 46. Aplicati metoda de sortare ins_dir asupra unui sir specificat si pe baza functiei C descrise vedeti ce rezultat se obtine la pasul k (k fiind cel putin 2). 47. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare ins_bin pentru o structura de date tablou alocat static 48. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare ins_bin pentru o structura de date tablou alocat dinamic (folosind malloc). 49. Implementati metoda de sortare ins_bin folosind numai structuri de control for. 50. Implementati metoda de sortare ins_bin folosind numai structuri de control while si do…while. 51. Analizati complexitatea metodei ins_bin in cazul cel mai defavorabil. 52. Aplicati metoda de sortare ins_bin asupra unui sir specificat si pe baza functiei C descrise vedeti ce rezultat se obtine la pasul k (k fiind cel putin 2).

• Sortare prin numarare [3, pag. 61-62]; 53. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare sort_num pentru o structura de date tablou alocat static 54. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare sort_num pentru o structura de date tablou alocat dinamic (folosind malloc). 55. Implementati metoda de sortare sort_num folosind numai structuri de control for. 56. Implementati metoda de sortare sort_num folosind numai structuri de control while si do…while. 57. Analizati complexitatea metodei sort_num in cazul cel mai defavorabil. 58. Aplicati metoda de sortare sort_num asupra unui sir specificat si pe baza functiei C descrise vedeti ce rezultat se obtine la pasul k (k fiind cel putin 2).

• Sortare prin interclasare [3, pag. 74-77], [1, pag. 213-214]; 59. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare isort pentru o structura de date tablou alocat static 60. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare isort pentru o structura de date tablou alocat dinamic (folosind malloc). 61. Implementati metoda de sortare isort folosind numai structuri de control for. 62. Implementati metoda de sortare isort folosind numai structuri de control while si do…while. 63. Analizati complexitatea metodei isort in cazul cel mai defavorabil.

64. Aplicati metoda de sortare isort asupra unui sir specificat si pe baza functiei C descrise vedeti ce rezultat se obtine la pasul k (k fiind cel putin 2).

• Sortare prin partitionare (numita si sortare rapida… qsort) [1, pag. 214-215], [3, pag. 65-69].

65. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare qsort pentru o structura de date tablou alocat static 66. Scrieti o functie C sau metoda C++/Java care implementeaza metoda de sortare qsort pentru o structura de date tablou alocat dinamic (folosind malloc). 67. Implementati metoda de sortare qsort folosind numai structuri de control for. 68. Implementati metoda de sortare qsort folosind numai structuri de control while si do…while. 69. Analizati complexitatea metodei qsort in cazul cel mai defavorabil, pivotul fiind elementul de la mijloc al secventei de partitionat. 70. Analizati complexitatea metodei qsort in cazul cel mai defavorabil, pivotul fiind intotdeauna primul element al secventei de partitionat. 71. Analizati complexitatea metodei qsort in cazul cel mai defavorabil. 72. Aplicati metoda de sortare ins_dir asupra unui sir specificat si pe baza functiei C descrise vedeti ce rezultat se obtine la pasul k (k fiind cel putin 2). III. Structuri de date fundamentale - Tablouri. a) Tablouri alocate static 73. [Transpusa unei matrice-1] Fie A un tablou patratic, alocat static, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se construiasca tabloul B care contine elementele transpusei matricei stocate in A. 73. [Transpusa unei matrice-2] Fie A un tablou patratic, alocat static, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se modifice tabloul A pentru a contine elementele transpusei matricei A, fara a folosi un tablou suplimentar. 74. [Explorare pe linii] Fie A un tablou patratic, alocat static, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se parcurga elementele tabloului, linie cu linie, si sa se calculeze, pentru fiecare linie suma elementelor. Sa se memoreze elementele tabloului A, in ordinea vizitarii, in tabloul unidimensional B. 75. [Explorare pe coloane] Fie A un tablou patratic, alocat static, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se parcurga elementele tabloului, coloana cu coloana, si sa se calculeze, pentru fiecare coloana, suma elementelor. Sa se memoreze elementele tabloului A, in ordinea vizitarii, in tabloul unidimensional B. 76. [Explorare Dia] Fie A un tablou patratic, alocat static, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se calculeze suma elementelor de pe diagonala tabloului. Sa se memoreze elementele de pe diagonala tabloului A in tabloul unidimensional B. 77. [Explorare TriD] 76. Fie A un tablou patratic, alocat static, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se calculeze suma elementelor din regiunea TriD. Sa se memoreze elementele din

regiunea TriD a tabloului A (intai elementele situate deasupra diagonalei principale, apoi elementele de pe diagonala principala, iar in final cele situate sub diagonala principala) in tabloul unidimensional B. 78. [Explorare Banda(r,s)] Fie A un tablou patratic, alocat static, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se calculeze suma elementelor din regiunea Banda(r, s), pentru r si s specificate. Sa se memoreze elementele din regiunea Banda(r, s) a tabloului A (incepand din partea superioara) in tabloul unidimensional B. 79. [Explorare Inf3] Fie A un tablou patratic, alocat static, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se calculeze suma elementelor din regiunea Inf3. Sa se memoreze elementele din regiunea Inf3 a tabloului A (incepand din partea superioara) in tabloul unidimensional B. 80. [Explorare Sup3] Fie A un tablou patratic, alocat static, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se calculeze suma elementelor din regiunea Sup3. Sa se memoreze elementele din regiunea Sup3 a tabloului A (incepand din partea superioara) in tabloul unidimensional B. b) Tablouri alocate dinamic 81. [Transpusa unei matrice-3] Fie A un tablou patratic, alocat dinamic, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se construiasca tabloul B care contine elementele transpusei matricei stocate in A. 82. [Transpusa unei matrice-4] Fie A un tablou patratic, alocat dinamic, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se modifice tabloul A pentru a contine elementele transpusei matricei A, fara a folosi un tablou suplimentar. 83. [Explorare pe linii] Fie A un tablou patratic, alocat dinamic, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se parcurga elementele tabloului, linie cu linie, si sa se calculeze, pentru fiecare linie suma elementelor. Sa se memoreze elementele tabloului A, in ordinea vizitarii, in tabloul unidimensional B, alocat dinamic. 84. [Explorare pe coloane] Fie A un tablou patratic, alocat dinamic, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se parcurga elementele tabloului, coloana cu coloana, si sa se calculeze, pentru fiecare coloana, suma elementelor. Sa se memoreze elementele tabloului A, in ordinea vizitarii, in tabloul unidimensional B, alocat dinamic. 85. [Explorare Dia] Fie A un tablou patratic, alocat dinamic, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se calculeze suma elementelor de pe diagonala tabloului. Sa se memoreze elementele de pe diagonala tabloului A in tabloul unidimensional B, alocat dinamic. 86. [Explorare TriD] 76. Fie A un tablou patratic, alocat dinamic, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se calculeze suma elementelor din regiunea TriD. Sa se memoreze elementele din regiunea TriD a tabloului A (intai elementele situate deasupra diagonalei principale, apoi elementele de pe diagonala principala, iar in final cele situate sub diagonala principala) in tabloul unidimensional B, alocat dinamic. 87. [Explorare Banda(r,s)] Fie A un tablou patratic, alocat dinamic, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se calculeze suma elementelor din regiunea Banda(r, s), pentru r si s specificate. Sa se

memoreze elementele din regiunea Banda(r, s) a tabloului A (incepand din partea superioara) in tabloul unidimensional B, alocat dinamic. 88. [Explorare Inf3] Fie A un tablou patratic, alocat dinamic, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se calculeze suma elementelor din regiunea Inf3. Sa se memoreze elementele din regiunea Inf3 a tabloului A (incepand din partea superioara) in tabloul unidimensional B, alocat dinamic. 89. [Explorare Sup3] Fie A un tablou patratic, alocat dinamic, care contine elementele unei matrice cu n randuri si n coloane (acestea fiind de tip float). Sa se calculeze suma elementelor din regiunea Sup3. Sa se memoreze elementele din regiunea Sup3 a tabloului A (incepand din partea superioara) in tabloul unidimensional B, alocat dinamic. - Liste simple, duble, liniare, circulare, generalizate: operatii, implementari, aplicatii a) Liste simple in alocare statica 90. Scrieti functia C sau metoda C++/Java pentru concatenarea a n liste simple, alocate static. 91. Scrieti functia C sau metoda C++/Java pentru cautarea unui element dupa cheie, intr-un grup de liste simple, alocate static. 92. Scrieti functia C sau metoda C++/Java pentru inserarea unui element dupa cheie (inaintea primului element mai mic/mare decit cel specificat, dupa primul element mai mic/mare decat cel specificat), intr-o lista simpla, alocata static. 93. Scrieti functia C sau metoda C++/Java pentru inserarea unui element dupa pozitie (inaintea unui element, dupa un element, la inceput, la sfarsit), intr-o lista simpla, alocata static. 94. Scrieti functia C sau metoda C++/Java care realizeaza interclasarea a doua liste simple, sortate crescator, alocate static, astfel incat lista rezultat sa ocupe acelasi spatiu. b) Liste simple in alocare dinamica 95. Scrieti functia C sau metoda C++/Java pentru concatenarea a n liste simple, alocate dinamic. 96. Scrieti functia C sau metoda C++/Java pentru cautarea unui element dupa cheie, intr-un grup de liste simple, alocate dinamic. 97. Scrieti functia C sau metoda C++/Java pentru inserarea unui element dupa cheie (inaintea primului element mai mic/mare decit cel specificat, dupa primul element mai mic/mare decat cel specificat), intr-o lista simpla, alocata dinamic. 98. Scrieti functia C sau metoda C++/Java pentru inserarea unui element dupa pozitie (inaintea unui element, dupa un element, la inceput, la sfarsit), intr-o lista simpla, alocata dinamic. 99. Scrieti functia C sau metoda C++/Java care realizeaza interclasarea a doua liste simple sortate crescator, alocate dinamic, astfel incat lista rezultat sa ocupe acelasi spatiu. c) Liste duble 100. Scrieti functia C sau metoda C++/Java pentru concatenarea a n liste duble, alocate static/dinamic.

101. Scrieti functia C sau metoda C++/Java pentru cautarea unui element dupa cheie, intr-un grup de liste duble, alocate static/dinamic. 102. Scrieti functia C sau metoda C++/Java pentru inserarea unui element dupa cheie (inaintea primului element mai mic/mare decit cel specificat, dupa primul element mai mic/mare decat cel specificat), intr-o lista dubla, alocata static/dinamic. 103. Scrieti functia C sau metoda C++/Java pentru inserarea unui element dupa pozitie (inaintea unui element, dupa un element, la inceput, la sfarsit), intr-o lista dubla, alocata static/dinamic. 104. Scrieti functia C sau metoda C++/Java care realizeaza interclasarea a doua liste duble, sortate crescator, alocate static/dinamic, astfel incat lista rezultat sa ocupe acelasi spatiu. d) Liste circulare 105. Scrieti o functie C sau metoda C++/Java corespunzatoare pentru transformarea unei liste liniare inlantuite intr-o lista circulara. Se vor considera implementari statice/dinamice pentru liste liniare simple/duble. 106. Scrieti o functie C sau metoda C++/Java corespunzatoare care verifica daca lista este sortata. Se vor considera implementari statice/dinamice pentru liste circulare simple/duble, pentru sortare de tip crescator/descrescator. 107. [Problema lui Josephus] In Masada (Galileea) s-a decis ca erau prea multi prizonieri si ei trebuie executati. 1000 prizonieri (numerotati de la 1 la 1000) au fost asezati in cerc, iar celui cu numarul 1 i s-a dat o sabie. El a fost instruit sa omoare cu ea prizonierul situat la stanga, dupa care sa dea sabia urmatorului prizonier viu (din stanga); acesta va trebui sa faca aceleasi operatii. Procedeul se repeta pana ramane un singur prizonier, care va fi eliberat. Din Masada a iesit Josephus. a) Ce pozitie ocupa el in cercul celor 1000 prizonieri ? b) Deoarece ultima miscare genereaza controverse (raman doi prizonieri si unul ii da sabia celuilalt sa il omoare), se decide sa fie lasati liberi ultimii doi prizonieri. Pe ce loc era camaradul lui Josephus, care a scapat din Masada ? Sa se implementeze algoritmul pentru rezolvarea acestei probleme folosind liste circulare simple/duble in alocare statica/dinamica, in cazul in care fiecare nod al listei contine un numar intreg de la 1 la n, n fiind numarul nodurilor initiale. - Stive si cozi : operatii, implementari, aplicatii. 108. Sa se implementeze, folosind o stiva in alocare statica, metoda de evaluare a functiei lui Ackermann [1, pag. 209]. 109. Sa se implementeze, folosind o stiva in alocare statica, metoda de evaluare a functiei Manna-Pnueli [1, pag. 210] 110. Se se implementeze metodele de inserare/stergere intr-o coada alocata static in maniera circulara. 111. Sa se implementeze algoritmului de rezolvare a problemei turnurilor din Hanoi1 indicand evolutia continutului celor trei stive.

1 Se dă un număr de trei turnuri, identificate cu a, b si c. Turnul a contine n discuri de dimensiuni diferite aranjate în ordine crescatoare în raport cu dimensiunea lor.

- Arbori : clase de arbori (oarecare, binari, de sortare/cautare, AVL, heap, B si

B+), metode de reprezentare, metode de explorare, aplicatii. 112. Sa se scrie o functie C sau o metoda C++/Java pentru parcurgerea in inordine a unui arbore binar in reprezentare statica/dinamica folosind o implementare iterativa/recursiva. 113. Sa se scrie o functie C sau o metoda C++/Java pentru parcurgerea in preordine a unui arbore binar in reprezentare statica/dinamica folosind o implementare iterativa/recursiva. 114. Sa se scrie o functie C sau o metoda C++/Java pentru parcurgerea in postordine a unui arbore binar in reprezentare statica/dinamica folosind o implementare iterativa/recursiva. 115. Sa se scrie o functie C sau o metoda C++/Java pentru a determina inaltimea unui arbore binar. 116. Sa se scrie o functie C sau o metoda C++/Java pentru a determina frunzele (nodurile terminale ale) unui arbore binar. 117. Se considera un arbore oarecare in reprezentare dinamica folosind legaturile FIU, FRATE, PARINTE. Sa se scrie o functie C sau o metoda C++/Java pentru a traversa arborele in adancime cu vizitarea intai a radacinii si apoi a descendentilor (A-preordine). 118. Se considera un arbore oarecare in reprezentare dinamica folosind legaturile FIU, FRATE, PARINTE. Sa se scrie o functie C sau o metoda C++/Java pentru a traversa arborele in adancime cu vizitarea intai a descendentilor si apoi a radacinii (A-postordine). 119. Se considera un arbore oarecare in reprezentare dinamica folosind legaturile FIU, FRATE, PARINTE. Sa se scrie o functie C sau o metoda C++/Java pentru a traversa arborele in latime (pe niveluri – breath first). 120. Sa se scrie o functie C sau o metoda C++/Java care insereaza un nou nod intr-un arbore binar de sortare. 121. Sa se scrie o functie C sau o metoda C++/Java care sterge un nod intr-un arbore binar de sortare, cu pastrarea proprietatii arborelui. 122. Construiti un arbore de decizie pentru problema cautarii binare in cazul unui n dat.

Problema consta în a transfera discurile de pe a pe c pastrând ordinea de asezare a discurilor. Discurile se pot transfera de pe un turn pe altul dupa urmatoarele reguli:

1. Transferul consta din mai multe mutari de discuri. La o mutare se ia un singur disc de pe un turn si se muta pe altul.

2. Nu poate fi plasat un disc de dimensiune mare pe unul de dimensiune mai mica.

3. Pentru transferarea discurilor de pe un turn pe altul se poate folosi cel de-al treilea turn pentru manevra.

http://www.ginfo.ro/8_3/hanoi.shtml

123. Sa se scrie o functie C sau o metoda C++/Java care insereaza un nou nod intr-un arbore echilibrat2 (AVL). 124. Sa se scrie o functie C sau o metoda C++/Java care sterge un nod intr-un arbore echilibrat (AVL), cu pastrarea proprietatii arborelui. 125. Sa se scrie o functie C sau o metoda C++/Java care insereaza unei chei noi intr-un arbore heap cu pastrarea proprietatii arborelui. 126. Sa se scrie o functie C sau o metoda C++/Java care sterge o cheie dintr-un arbore heap cu pastrarea proprietatii arborelui. 127. Pentru un sir de chei se cere sa se verifice daca este un heap (ansamblu). 128. Pentru o expresie aritmetica se cere forma poloneza prefix (parcurgerea arborelui binar asociat in preordine) 129. Pentru o expresie aritmetica se cere forma poloneza inversa (parcurgerea arborelui binar asociat in postordine) 130. Pentru un text cu n caractere se cere sa se construiasca arborele Huffman si codul sirului (algoritmul de compresie Huffman). IV. Algoritmi de cautare : liniara, binara, arborescenta, functii hash, cautare in siruri 131. Sa se scrie o functie sau metoda C++/Java pentru cautarea unei chei intr-un arbore oarecare specificat prin legaturi FIU, FRATE, PARINTE. 132. Sa se scrie o functie sau metoda C++/Java pentru cautarea unei chei intr-un arbore binar de sortare. 133. Sa se scrie o functie sau metoda C++/Java pentru cautarea unei chei intr-un arbore echilibrat (AVL). 134. Sa se scrie o functie sau o metoda C++/Java pentru inserare unei chei intr-o tabela de dispersie. 135. Sa se scrie o functie sau o metoda C++/Java pentru stergerea unei chei dintr-o tabela de dispersie. 136. Pentru o anumita functie se cere verificarea proprietatilor acesteia pentru a vedea daca poate fi folosita ca functie de dispersie (hash). a) Functii hash simple: Cormen (h(k) = k mod m), Knuth (h(k) = k(k+3) mod m) b) Functii de dispersie pentru siruri 137. Sa se scrie o functie sau metoda C++/Java pentru implementarea algoritmului Knuth-Morris-Pratt. V. Clase speciale de algoritmi: probabilisti, evolutionisti 138. Generarea unui sir de numerelor pseudo-aleatoare pentru a fi utilizat in testarea complexitatii algoritmilor de sortare, pentru a se studia timpul mediu de sortare. 139. Generarea unui sir de numerelor pseudo-aleatoare pentru a fi utilizat in testarea complexitatii algoritmilor de cautare liniara, pentru a se studia timpul mediu de cautare. 140. Generarea unui sir de numerelor pseudo-aleatoare pentru a fi utilizat in testarea complexitatii algoritmului de cautare/sortare bazat pe arbori AVL. 141. Sa se scrie functii sau metode C++/Java pentru implementarea operatiilor de baza cu care lucreaza algoritmii genetici (selectie, incrucisare, mutatie).

2 http://frankeman.sitesfree.com/licenta/tdaarbori1.html

142. [Jocul vietii] Se consideră o matrice de dimensiune NxM (N linii, M coloane). Matricea are în total NxM celule. În unele din aceste celule se găsesc viruşi, maxim un virus în celulă. O celulă se învecinează cu 8 alte celule. Celulele de pe marginea matricii se învecinează doar cu 5 alte celule, iar celulele din colţurile matricii se învecinează doar cu 3 alte celule. Populaţia de viruşi evoluează în etape, după următoarele reguli:

1. O celulă care la etapa K este goală şi are exact trei viruşi vecini, va da naştere unui virus în etapa K+1. 2. O celulă care la etapa K conţine un virus şi are doi sau trei vecini viruşi, va păstra virusul şi la etapa K+1. 3. În orice altă situaţie o celulă care la etapa K conţine sau nu virus, la etapa K+1 va deveni goală.

Scrieţi un program C care citeşte de la tastatură dimensiunea matricii (N şi M), generează o configuraţie iniţială aleatoare a populaţiei de viruşi şi pe urmă afişează evoluţia populaţiei de viruşi, aşteptând afişarea unei taste după fiecare etapă. Programul îşi va încheia execuţia în momentul când utilizatorul va apăsa tasta 'x'. VI. Structuri de date multidimensionale3

143. Sa se scrie functii C sau metode C++/Java pentru parcurgerea masivelor tridimensionale pe inaltime, lungime, respectiv latime. 144. Sa se stocheze intr-un tablou unidimensional datele stocate intr-un tablou tridimensional respectand ordinea lexicografica a indicilor. 145. Sa se realizeze un program C/C++/Java pentru manipularea imaginilor cu ajutorul arborilor cu 0 sau 4 descendenti (quad tree). 146. Sa se realizeze un program C/C++/Java pentru manipularea structurilor spatiale cu ajutorul arborilor cu 0 sau 8 descendenti (oct tree). Bibliografie

1. G. Albeanu, Algoritmi si limbaje de programare, Editura FRM 2000. 2. S. Barză, Luciana-Maria Morogan, Structuri de date, Ed. FRM., Bucureşti,

2007 3. I. Tomescu, Data Structures, Editura Universitatii din Bucuresti, 1997. 4. A. Carabineanu, Structuri de date, Editura Universitatii din Bucuresti, Editura

MATRIX ROM, Bucuresti, 2006: (disponibila in format electronic la http://ebooks.unibuc.ro/informatica/carabineanu/CARA_STR.pdf )

3 Numai pentru proiecte de laborator