Course Code : MCS-211

Course Title : Proiectare ș i analiză a algoritmilor

Numărul sarcinii : MCAOL(I)/211/Assign/2024
Maximum Marks : 100
Weightage : 30%
th
Ultimele date pentru depunere : 30 Aprilie 2024 (pentru sesiunea din ianuarie)
st
31 Octombrie 2024 (pentru sesiunea din iulie)

Această sarcină are douăsprezece întrebări (80 de puncte). Răspundeț i la toate întrebările. Restul de 20 de puncte sunt pentru
examinarea dumneavoastră orală. Pute ț i folosi ilustra ț ii ș i diagrame pentru a îmbunătă ț i
Vă rugăm să consultaț i orientările privind sarcinile date în Program.
ghid pentru formatul prezentării.

Q1: a) Dezvoltă un algoritm eficient pentru a găsi o listă de numere prime de (2

la puncte)
100 la
1000.

b) Diferentia ț i între algoritmii de timp polinomial ș i cei de timp exponen ț ial. (2

Oferi ț i
Puncte)
un exemplu de o problemă pentru fiecare dintre aceste două timpuri de rulare.

c) Folosind regula lui Horner, evalua ț i polinomul p(x) = 2x5-5x4-3x2+15 la (2x=2.

Puncte)
Analiza ț i timpul de calcul necesar pentru evaluarea polinoamelor folosind
Regula lui Horner împotriva metodei brute

ș i Aplică
d) Stabili ț i ș i explica ț i teoremele pentru calcularea limitelor O, (4 Puncte)
aceste teoreme pentru a găsi nota ț ia O, nota ț ia Ω ș i nota ț ia Θ pentru
function: ( = 10 3+18 2+1

e) Explica ț i exponentierea binară pentru calcularea valorii 519Scrie dreptul la- (4 Puncte)
algoritmul de exponentiere binară stângă ș i arată cum func ț ionează pentru
exponenț iere 519. De asemenea, găsiț i complexitatea în cel mai rău caz a acestui algoritm.

f) Scrie ț i ș i explica ț i algoritmul de căutare liniară ș i discuta ț i despre cel mai bun ș i cel mai rău caz.
(4 Puncte)
complexitatea timpului de caz. Arată funcț ionarea algoritmului de căutare liniară pentru
data: 12, 11, 3, 9, 15, 20, 18, 19, 13, 8, 2, 1, 16.

g) Ce este o rela ț ie de recuren ț ă? Rezolva ț i următoarele rela ț ii de recuren ț ă folosind

(2 Puncte)
metoda Masterului

a. ( =) 8T 2
( ) +
2
b. ( =) (3 ) + 1
4

Q2: a) Ce este o abordare lacomă în rezolvarea problemelor? Formulează frac ț ionar (4 Puncte)
Problema rucsacului ca problemă de optimizare ș i scrie un algoritm greedy pentru
rezolvă această problemă. Rezolvă următoarea problemă a rucsacului fracț ionar utilizând aceasta
algoritm. Arată toate etapele.
Să presupunem că există un rucsac cu o capacitate de 15 kg ș i 6 articole trebuie să fie ambalate în el.
Greutatea ș i profitul articolelor sunt după cum urmează:
(p1,p2,…,p6) = (3,2,4,5,1,6)
(w1,w2,…,w6) = (2,1,2,1,5,1)

b) Care este scopul utilizării codurilor Huffman? Explicaț i paș ii pentru construirea unui (4 Puncte)
arbore Huffman. Proiectaț i codurile Huffman pentru următorul set de caractere ș i

3
 their frequencies:a:15, e:19, s:5, d:6, f:4, g:7, h:8, t:10.

c) Explică procedura de Partajare a algoritmului Quick Sort. Folose ș te această procedură ș i

(4 Puncte)
algoritm quick sort pentru a sorta următorul array de dimensiune 8: [12, 9, 17, 15, 23, 19, 16,
24]. Compute the worst case and best case complexity of Quick sort algorithm.

d) Explicaț i abordarea divide ș i cucereș te pentru multiplicarea a două matrice de dimensiuni mari.
(4 Puncte)
De asemenea, explica algoritmul de înmul ț ire a matricei al lui Strassen. Găse ș te timpul
complexitatea ambelor abordări.

e) Care este utilizarea sortării topologice? Scrie ț i ș i explica ț i sortarea topologică. (4 Puncte)
algoritm. De asemenea, calculaț i complexitatea temporală pentru algoritmul de sortare topologică.

Q3: Consideraț i următorul graf:

Figura 1: Grafic pentru Problema 3(a) ș i 3(b)

a)Write the Kruskal’s algorithm and Prim’s algorithm to find the minimum cost (4 Puncte)
arborul de acoperire al graficului dat în Figura 1. Arătaț i toț i paș ii de calcul.
De asemenea, calculează complexitatea temporală a ambelor algoritmi.

(4 puncte)
b) În Figura 1, găsiț i cel mai scurt drum de la vârful 'a' folosind cel mai scurt drum Dijkstra.
algoritmul căii. Arată toț i paș ii de calcul. De asemenea, găseș te complexitatea temporală
al algoritmului.

c) Ce este programarea dinamică? Care este principiul optimalită ț ii? Folose ș te-l. (6 puncte)
abordarea programării dinamice pentru a găsi secven ț a optimă a lan ț ului
înmulț irea următoarelor matrice:

Matrice Dimensiune
A1 5 × 10
A2 10 × 20
A3 20 × 15
A4 15 × 8
A5 8 × 10

d) Faceț i toate arborii de căutare binară posibile pentru valorile cheie 25, 50, 75. (2 Puncte)

(4 Puncte)
e) Explica ț i algoritmul Knuth Morris Pratt pentru potrivirea ș irurilor. Folosi ț i acest algoritm.
a găsi un model "algo" în textul "De la alge la algoritmi". Arată toț i paș ii.
Care este complexitatea în timp a acestui algoritm.

Q4: a) Ce sunt problemele de decizie ș i problemele de optimizare? Diferen ț iază problemele de decizie.
(4 Puncte)
probleme ș i probleme de optimizare cu ajutorul a cel pu ț in două probleme
declaraț iile fiecăruia.

b) Defineț i clasele de probleme P ș i NP cu ajutorul exemplelor. Cum sunt clasele P de (4 Note)

problemă diferită de clasa NP de probleme.
4
c) Ce sunt problemele NP-Dificile ș i NP-Complet? Care este rolul reducerii? (4 Puncte)
Explicaț i cu ajutorul unui exemplu.

d) Definiț i următoarele probleme: (8 puncte)

(i) 3-CNF SAT
(ii) Problema clique
(iii) Problema acoperirii vârfului
(iv) Problema colorării grafului