Untitled

1) In what follows, let v be an n-size vector of integers, and let S be an n-size vector of empty
stacks. Consider the following algorithm:
for i=0...n-1 do:
compute the smallest index j s.t. all elements in stack S[j] are strictly smaller than v[i]
S[j].push(v[i])
done
a. Propose an O(n*log(n))-time implementation of the above algorithm. /1
b. A decreasing sequence of v is a sequence of indices i1 < i2 < ... < ik such that v[i1] ≥
v[i2] ≥ ... ≥ v[ik]. Propose an O(n*log(n))-time algorithm for computing a longest
decreasing sequence in v. /1

2) In the 2-sum problem, we are given an n-size vector v of integers, and we must answer
whether there exist indices i < j such that v[i]+v[j] = 0. Propose an algorithm for solving the
2-sum problem in expected O(n) time. /1
-- Simpler variant: propose an algorithm for solving this problem in O(n*log(n)) time. /.5
3) In what follows, let T be a binary search tree with n nodes.
a. Show that we can sort all values in T in O(n) time. /1
b. Deduce from the previous question what is the optimum time for inserting n elements
in a (possibly non-balanced) binary search tree. /1

4) Consider an n-size vector v. A strong inversion is a pair (i,j) such that i < j but 5*v[i] > v[j].
a. Propose an O(n*log(n))-time algorithm for computing the number of inversions in a
vector. /1
b. Is the algorithm for the previous question optimal? Justify. /1
5) Let u,v be two n-size vectors of integers. Propose an algorithm in expected O(n) time in order
to decide whether u,v contain the exact same elements (counted with multiplicity), but
possibly in a different order. /1
-- Simpler variant: Propose an algorithm for this problem in O(n*log(n)) time. /.5
6) Let a[] be a vector of size n and i an index between 0 and n-1.
a. Propose an algorithm in O(n) time in order to output the sum of all elements
between two indices i and j (i < j). /1

b. Show that if we pre-process vector a[] in O(n) time, then we can find the sum of all
elements between any two indices i and j in O(1) time. /1



1
a
Avem n stackuri, inseram elementul i in primul stack care are top < i, 
facem o cautare binara pe acele stack.top() ca sa putem insera in log n
inserarea a n elemente => nlogn, ba chiar n log (s) unde s e numarul de stackuri 
negoale, avand in vedere ca putem tine minte numarul actual de stackuri
!!!Daca nu exista niciun stack negol care sa aiaba stack.top< i => creeam unul nou
b
Numarul de stackuri, pentru ca stim ca o sa creeam un stack nou doar atunci cand niciunul 
dintre cele precendente indeplinteste conditia 

2
Parcurgem vectorul de la 0 la n-1 cu i, introducem v[i] in hastable 
verificam daca exista un element -v[i] in hastable, daca da raspundem
daca pana la final nu putem raspunde => nu exista

3
a.DFS in order output 
b.Sa deducem e mai greu, eu aici as baga niste abureli, ca si daca luam prin random un elemetn avem sansa de 1/n 
sa fie ales corect, as aduce vorba si de creeare unui arbore pe baza unui vector care e deja sortat

4.
n are treaba ca 5*... e acelasi algoritm
Modificare merge sort. Merge sort reprezinta sortarea unui vector prin unificarea jumatatilor deja sortate
Impartim vectorul la jumatate astfel mid=st+(dr-st)/2 pana cand putem rezolva cel mai usor caz <=> 
lungimea subvectorului este 1, comparam cele doua elemente si le interschimba la nevoie, insemnand ca avem o inversiune => 
unificarea subvectorilor astfel k=st => parcugem cei doi subvectori de la st cu i si de la mid cu j pentru a decide cine ocupa
locul k in subvectorul curent, daca un element din subvectorul drept < un element din subvectorul stang => avem mid-i inversiuni
ptc elementul[j] are in stanga lui mid-i elemente mai mari decat element
Acest algoritm este optim deoarece putem avea 2^n inversiuni si abureala

5.
parcurgem vectorul de la 0 la n-1 cu i, daca daca in hashtable avem deja v[i] facem v[i]++, daca nu inseram cu valoarea 1
dupa aceea comparam hashtable celor doi vectori

6.
parcurgem vecotrul de la i la j si facem sum + = v[k]

b. facem suma partiala pt toatele elemente din v intr un vector sum [n], astfel sum[i]= sum[i-1]+v[v]
pentru a raspunde la query suma dintre i si j, vom calcula sum[j]-sum[i]+v[i]