23 decembrie 2015

"Disable yama" in Ubuntu

 cat /proc/sys/kernel/yama/ptrace_scope 

As Linux grows in popularity, it will become a larger target for malware. One particularly troubling weakness of the Linux process interfaces is that a single user is able to examine the memory and running state of any of their processes. For example, if one application (e.g. Pidgin) was compromised, it would be possible for an attacker to attach to other running processes (e.g. Firefox, SSH sessions, GPG agent, etc) to extract additional credentials and continue to expand the scope of their attack without resorting to user-assisted phishing. This is not a theoretical problem. SSH session hijacking and arbitrary code injection attacks already exist and remain possible if ptrace is allowed to operate as before. Since ptrace is not commonly used by non-developers and non-admins, system builders should be allowed the option to disable this debugging system.

ptrace_scope value 0 => disable this security, while value 1 is the default after each booting

 echo 0 > /proc/sys/kernel/yama/ptrace_scope 

10 iunie 2015

Probleme pt interviu: C++, Java, Database, Threads

cap. 13 - C/C++                                                                                  

Lucruri de baza:
* clase, mosteniri: by default, clasele sunt private
daca avem class Student : public Person { ... } ; Person p = new Student() ;  => p va fi Person (static binding, in timpul compilarii) . Pentru dynamic binding se foloseste cuvantul-cheie virtual.
* virtual permite suprascrierea cu ultima definitie a tipului declarat 
* virtual destructor va apela destructorul ambelor clase (cea mostenita si cea mostenitoare)
* functiile se pot declara cu valori implicite, la fel ca in Python
* overloading: BookShelf BookShelf::operator+ (BookShelf x)  { ... }     - supraincarcarea operatorului + pentru a fi aplicat si obiectelor de tip BookShelf
* pointeri: int * p = new int; *p = 7;      lungimea pointerului este de 32 sau 64 biti (in functie de tipul masinii)
* tipul referinta: int a = 5; int & b = a; b = 7; cout<<a; // scrie 7  , aici b este un alias pentru a, nu ocupa memorie pt el insusi
* nu este posibila declaratia:  int & b;  
dar e ok: int & b = 12; // b este referinta la locul unde este stocat nr. intreg 12
* templates: reutilizare a codului astfel incat aceeasi clasa sa fie aplicabila la mai multe tipuri de date
template <class T>
class ShiftedClass {
  T * arr;
  int offset, size;
  ... 
}

* o metoda pentru a scrie ultimele K linii dintr-un fisier, folosind C++

Sol.: se foloseste un sir circular de lungime K . Se pastreaza un index al celui mai vechi element si intotdeauna se inlocuieste elementul respectiv cu cel mai nou element(linie) citit.

void printLast (char * filename) {
  const int K = 10; // ultimele 10 linii
  ifstream file (filename);
  string L[K];
  int size = 0;
  while (file.good()) {
    getline ( file, L[size % K] );  // umple vectorul incepand cu cea mai "veche" pozitie
    size++;
  }
  // afla inceputul
  int start;
  if (size > K) start = size % K;  // ce ar fi devenit cea mai "veche" pozitie e acum prima din ultimele K
  else start = 0; // au fost mai putin de K linii
  int count = min (K, size);
  // print the lines
  for (int = 0; i < count; i++) {
    cout<< L [(start+1)%K] << endl;
  }
}


* comparatie intre hash table si un STL map. Cum sunt implementate? Daca nr. de input-uri este mic, care structura de date se foloseste mai bine?

Sol.: 
HashTable: - valorile sunt create apeland o functie de hash asupra valorii
  - valorile nu se salveaza in ordine ASC sau DESC
  - inserarea/cautarea se petrec in O(1)
  - trebuie sa rezolve potentialele coliziuni (adesea se face prin inlantuire, linked list)
  - implementare: un sir de liste inlantuite, cheia corespunde unui index in sir (care se afla folosind functia de hash), valorile intr-o lista inlantuita corespund unei aceleiasi chei, insa trebuie salvata si cheia pentru a furniza valoarea corecta

STL map: - perechea cheie,valoare se insereaza intr-un arbore binar de cautare, in fct de cheie
  - nu este cazul coliziunilor
  - inserare/cautare se petrec in O(log n)

Nr. mic de inputs: STL map sau un arbore binar. Nr. mare: hash table.


* cum functioneaza functiile virtuale in C++?

Sol.: Functiile nevirtuale se rezolva in timpul compilarii, cu static binding
Functiile virtuale se rezolva in timpul rularii, cu dynamic binding. Se salveaza intr-o structura numita vtable, asociata unei clase. Daca functia virtuala nu este suprascrisa, se acceseaza vtable al clasei derivate si adresa functiei se salveaza in clasa-parinte. 


* diferenta intre deep-copy si shallow-copy?

Sol.: Deep-copy: copiaza obiectul intocmai (duplicat), daca se modifica copia, originalul ramane intact. Shallow-copy: opusul.


* ce inseamna volatile in C?

Sol.: Cuvantul-cheie volatile informeaza compilatorul ca valoarea unei variabile se poate schimba din exterior, fara nicio corespondenta in codul sursa (se poate realiza datorita SO, al unui altui thread, sau din hardware). Astfel, compilatorul va trebui sa reincarce valoarea din memorie de fiecare data cand se foloseste variabila, iar astfel este prevenit sa nu faca optimizari care ar schimba logica codului.
int volatile x; // volatile int x;
int volatile * volatile x; // pointer volatil la o variabila volatila


* de ce un destructor ar trebui declarat virtual intr-o clasa care poate fi mostenita?

Sol.: 
Foo * p = new Bar();
La distrugere, fara un destructor virtual, se apeleaza destructorul din Foo, chiar daca p este de tip Bar. Ca "Bar", p ar putea avea campuri noi care nu vor ajunge sa fie distruse pentru ca nu apar in Foo.


* o metoda care face o copie completa a unui pointer la obiectul de mai jos:
struct Node {
  Node * ptr1;
  Node * ptr2;
}
Sol.:
typedef map <Node *, Node *> NodeMap; 
Node * copy (Node * current, NodeMap & nodeMap) {
  // fct recursiva 
  if (current == NULL) return NULL;
  // pt evitarea buclelor infinite de la un ptr care a condus la un ptr deja vizitat
  NodeMap :: iterator i = nodeMap.find(current); // std::pair, are first & second
  if ( i != nodeMap.end() ) {
    return i->second; //  valoarea 
  }
  Node * node = new Node;  // creeaza copia (sau bucata de copie)
  nodeMap[current] = node;  // first = current, second = node (~copia lui current este node)
  node->ptr1 = copy(current->ptr1, nodeMap);
  node->ptr2 = copy(current->ptr2, nodeMap);
  return node;
}

// creare
Node * mainCopy (Node * root) {
  NodeMap nodeMap;
  return copy (root, nodeMap);
}


cap. 14 - Java                                                                                     

Termeni-cheie:
> overloading - doua metode au acelasi nume dar numar diferit de argumente
> overriding - o subclasa redefineste o metoda a parintelui, folosind aceeasi semnatura pentru ea


* ce se intampla cand constructorul unei clase este privat?

R: se asigura faptul ca nimic din afara clasei nu poate instantia direct clasa, astfel singurul mod de a o instantia este folosind o metoda statica si publica (~ Factory Method Pattern)


* try { 
    ...
    return 0;
  }
  catch (Exception e) { ... }
  finally { ... }    // ajunge sa se execute aceasta portiune??

R: Da, finally se executa intotdeauna dupa ce try se termina. Singurele cazuri cand finally nu se executa sunt: masina virtuala se opreste in timpul try/catch sau thread-ul care executa try/catch este omorat.


* final vs. finally vs. finalize

final: cuvant-cheie pentru o variabila constanta SAU o metoda care nu poate fi suprascrisa SAU o clasa care nu poate fi derivata
finally: in try/catch, o portiune de cod care se executa intotdeauna indiferent daca apare exceptie sau nu
finalize: metoda apelata de garbage collector cand isi da seama ca nu mai exista referinte la resurse care trebuie "curatate"


* ce este object reflection? La ce ajuta?

Class rectDef = Class.forName("MyProj.Rectangle");  
rectDef.getConstructor();

Informatii "reflexiva" despre clase si obiecte Java, metode si campuri prezente in timpul rularii; Se pot crea instante noi ale clasei, get/set pe campurile obiectului indiferent de tipul de acces (public/private) . Ajuta la: observarea si manipularea comportamentului la runtime a aplicatiei; pentru depanare si testare.


cap. 15  - Baze de date                                                                      

Baza de date normalizata vs. nenormalizata: minimizarea redundantei vs. optimizarea timpului de citire (si evitarea join-urilor)
Aici exercitiile sunt de tip sql queries (subqueries, join-uri, having/group by, etc) si de tip teoretic.


* care sunt tipurile de join?

R: JOIN se foloseste la combinarea rezultatelor din 2 tabele care au cel putin un camp folosit pentru a face legatura intre ele. 
INNER JOIN: doar randurile unde conditia de join se respecta
OUTER JOIN: INNER JOIN + alte randuri care nu respecta conditia in cel de-al doilea tabel
 - LEFT JOIN: rezultatul contine toate inregistrarile din tabelul din stanga sau NULL daca nu exista valori coresp. in tabelul din dreapta
 - RIGHT JOIN: idem LEFT, dar invers
 - FULL OUTER JOIN: LEFT+ RIGHT


* denormalizare, ce este? pro, contra?

R: O tehnica de optimizare in care adaugam informatii redundante la 1 sau mai multe tabeluri. Ajuta la evitarea join-urilor costisitoare dintr-o baza de date relationala.
Pro: - datele se achizitioneaza mai repede, mai putine join-uri
   - interogarile sunt mai simple, riscul greselilor este mai mic
Contra: - update,insert sunt mai costisitoare si mai dificil de scris
   - datele pot deveni inconsistente
   - din cauza redundantei este nevoie de mai mult spatiu de stocare


* o interogare pt a obtine o lista a studentilor de onoare (top 10%) ordonati dupa medie

Student: sId, name, bday
Coursework: courseId, sId, grade
Course: courseId, courseName

DECLARE @gpaCutOff float;
SET @gpaCutOff = ( SELECT min(GPA) as 'GpaMin' 
                                    FROM  ( SELECT TOP 10 PERCENT AVG (Coursework.grade) as GPA 
                                                    FROM Coursework
                                                    GROUP BY Coursework.sId
                                                    ORDER BY GPA desc) Grades );
SELECT StudentName, GPA
FROM ( 
    SELECT AVG (Coursework.Grade) as GPA, Coursework.sId
    FROM Coursework
    GROUP BY Coursework.sId
    HAVING AVG(Coursework.grade) >= @GpaCutoff
) Honors INNER JOIN Students ON Honors.sId = Student.sId


cap. 16 - Threads & Locks                                                               

Fire de executie in Java:
1) implementeaza Runnable SAU
2) extind Thread
Se prefera Runnable deoarece Java nu accepta mostenire multipla.

Metode synchonized: se executa de catre un singur thread la un moment dat ( al doilea thread care nu are voie sa execute metoda trebuie sa apartina aceleiasi instante a obiectului, altfel are voie )

Lock:  ReentrantLock
Un Lock in Java este proprietatea thread-ului care l-a creat, niciun alt thread nu poate sa-l modifice. Pentru semafoare, nu .


* diferenta intre un proces si un thread

R: Procesul este o instanta a unui program in executie, foloseste CPU si memorie, se executa intr-un spatiu de adrese separat. Procesele nu-si pot accesa spatiile unul altuia, cu exceptia IPC (interprocess communication prin pipes, files, sockets, etc)
Un thread exista in cadrul unui proces, foloseste resursele procesului, inclusiv heap-ul. Mai multe thread-uri ale aceluiasi proces impart acelasi spatiu de heap, insa fiecare thread are propriile registre si spatiu pe stiva.


* cum se poate masura timpul petrecut intr-un context switch?

R: Trebuie masurat timpul dintre ultima instructiune executata de P1 si prima instr. exe. de P2.
Il fortam pe P2 sa execute fix dupa P1, printr-un pipe: P1 trimite, P2 primeste.
Pasii sunt:
- P1 marcheaza timpul de start, T1
- P1 trimite un token la P2, care ia Td pentru a fi livrat
- P1 incearca sa primeasca un raspuns de la P2, se blocheaza si are loc context switch -> Tc
- P2 incepe sa ruleze, primeste token-ul   -> Tr
- P2 trimite un raspuns catre P1, care ajunge in Td
- P2 asteapta un raspuns de la P1, se blocheaza si are loc context switch  ->  Tc
- P1 incepe sa ruleze, primeste token-ul     ->  Tr
- P1 marcheaza timpul de final, T2
=> T = 2 ( Td + Tr + Tc ) , unde T = T2 - T1
=> Tc = ... 

20 mai 2015

Probleme pentru interviu: Scalabilitate, Sortari si cautari, Testari

 cap. 10 - Scalability & Memory limits                                           

* fie un serviciu care poate fi apelat de pana la 1000 clienti pentru a obtine cateva informatii despre preturi de vanzare. Cum se pot salva informatiile?

Trei variante:
1) date salvate in fisiere text care se pot descarca prin FTP
2) o baza de date SQL : usor de obtinut informatii, functionalitati de backup, rollback, securitate, usor de integrat cu alte unelte . Dezavantaj: poate fi prea complex pentru simple functionalitati, trebuie cunoscut limbajul de interogare SQL, drepturile de securitate si setarea lor.
3) XML : usor de citit atat pentru om cat si pt calculator, cele mai multe limbaje au un API pentru parsarea XML, adaugarea de noi noduri nu incurca parserul existent. Dezavantaj: se trimit clientului toate informatiile indiferent daca sunt necesare sau nu, trebuie parsat intreg continutul pentru a obtine raspuns la o interogare.


* un fisier contine 4 miliarde de numere intregi pozitive. Gasiti un algoritm care poate gasi un numar necontinut in fisier, avand la dispozitie 1 GB de memorie.

4 miliarde = 2^32 numere
spatiul pt 4 miliarde de nr. = 8 * 2^32 = 2^35 biti
1 GB memorie = 2^30 biti  < spatiul necesar

Sol.: creare unui vector de 4 miliarde de biti, initializat cu 0
- pt fiecare numar se seteaza un bit in vector
- la final, se scaneaza vectorul si se returneaza indexul primei valori 0

long nofInt = (long) Integer.MAX_VALUE - 1; // MAX_VALUE e cel mai mare nr. posibil in fisier
byte [] bitfield = new byte [(int) (nofInt / 8)]; // 8 numere continute intr-un octet, similar cu radix sort
void find () {
  // setari
  Scanner in = new Scanner (new FileReader("srcFile.txt"));
  while (in.hasNextInt()) {
    int n = in.nextInt();
    bitfield [n/8] = bitfield [n/8] | (1 << (n%8));  // setarea bitului coresp., n%8 e pozitia in octet
    // pot exista duplicate, caz in care se seteaza din nou bitul
  }
  // cauta primul nr necontinut
  for (int i = 0; i < bitfield.length; i++ ) {
    for (int j = 0; j < 8; j++) {
      if ( (bitfield[i] & (1<<j)) == 0) {
        System.out.println ( i * 8 + j);
        return ;
     }
  }
  // si daca toate numerele au fost consecutive... nu exista!!
 System.out.println ("Nu exista un astfel de numar");
}


* avem un sir cu numere de la 1 la N  (N <= 32.000, necunoscut) . Pot exista duplicate. Folosind maxim 4 KB de memorie, cum se pot afisa toate elementele duplicate din sir?

Sol.:  4 KB de memorie pot codifica 4 * 8 * 2^10 = 2^15 biti = 32 Kbiti > 32*10^3 biti = 32.000 biti
=> crearea unui vector cu 32.000 biti
- se parcurge vectorul de biti si pe fiecare pozitie se seteaza 1 (pozitia repr. codificarea numarului curent din sir)
- daca pozitia era deja setata, se tipareste numarul caruia ii corespunde ca fiind duplicat
- fiecare bit reprezinta un numar, exista suficienti biti pentru marcarea fiecarui numar (32.000), deci daca vectorul va fi de tip int, el va avea 1000 elemente intregi, fiecare element avand 32 biti 
- accesul la "cuvant" se face printr-un index = pos / 32, iar in cadrul unui cuvant index2 = pos % 32, unde pos este pozitia "logica"
- exemplu de setare:   bitvec [pos >> 5] |= 1 << (pos & 0x20)  ,  adica la pozitia 2^5 din bitvec, se seteaza bitul de la subpozitia  pos & 32 , adica bitul restului impartirii lui pos la 32 , ceea ce aminteam mai inainte.


cap. 11 - Sortari, cautari                                                                   

* A, B sunt doua siruri deja sortate. Presupunem ca A are suficiente spatii libere la sfarsit astfel incat B poate incapea acolo. Cum se poate incorpora B in A a.i. A sa fie sortat?

Sol.: ne mutam la capatul lui A si inseram elemente de la sfarsit catre fatza, incepand cu cele mai mari elemente din A sau din B. Cand A sau B se termina, doar copiem sirul ramas pe pozitiile din A.


* sa se sorteze un sir de siruri de caractere astfel incat toate anagramele stau una langa cealalta.

Sol.: singura conditie de aranjare este ca anagramele sa stea impreuna, nu conteaza ordinea... O anagrama reprezinta orice permutatie folosind caracterele dintr-un sir de caractere.
- creeaza un HashMap <String, list of String>
- pt. fiecare string, sorteaza-i caracterele si adauga anagrama la lista corespunzatoare sirului sortat
- la sfarsit, se transforma HashMap-ul intr-un sir care va aparea sortat


* se da un sir sortat de numere intregi care a fost rotit de un numar necunoscut de ori. Sa se afle un anumit element din sir.

Sol.: in cazul obisnuit, la partitionarea in 2 a sirului, o parte va fi sortata crescator, iar in cealalta va aparea trecerea brusca de la un minim la maxim sau invers.

array = [9,10,4,5,6,7,8]

def find (A, elem, frm, to):
mid = (frm+to) // 2
if elem == A[to]:
print ("Position is ", to)
return None
elif elem == A[frm]:
print ("Position is ", frm)
return None
# case: left side is ordered and elem within the limits
if A[frm] < A[mid] and elem > A[frm] and elem < A[to]:
find (A, elem, frm, mid)
# case: right side is ordered and elem within the limits
elif A[mid] < A[to] and elem > A[mid] and elem < A[to]:
find (A, elem, mid, to)
# case: left side ordered and right is not => search in right
elif A[frm] < A[mid]:
find(A, elem, mid, to)
# case: right side ordered and left is not => search in left
elif A[mid] < A[to]:
find(A, elem, frm, mid)
else:
print ("Element not found:", elem)
return None
find(array, 10, 0, len(array)-1)


* avem o matrice M x N in care fiecare linie si coloana este sortata crescator. Sa se afle un element cautand intr-o astfel de matrice.

Sol.: ca si in cazul cautarii binare, se cauta sa se elimine portiuni din matrice in care sigur nu poate aparea elementul. Exista mai multe abordari: mai jos, ne pozitionam pe elementul din centrul matricei si in functie de comparatie, fie eliminam coltul stanga-sus de acest element, fie restul matricei. In carte, abordarea e ca se exclud linii care incep cu un element > ce cautam sau se incheie cu un element < al nostru, idem pt coloane.

matrix = [[1,2,3,4], [4,7,9,10], [5,9,11,15], [20,21,25,27]]
M = len(matrix)-1
N = len(matrix[0])-1

def find (A, fromI, toI, fromJ, toJ, elem):
midI = (fromI + toI) // 2
midJ = (fromJ + toJ) // 2

if fromI > toI or fromJ > toJ:
print("Element not found:", elem)
return False

# base cases
if elem == A[midI][midJ]:
print("Found at (", midI, ",", midJ, ")")
return True

if fromI == toI:
# search on the line
for j in range (fromJ, toJ+1):
if elem == A[fromI][j]:
print("Found at (", fromI, ",", j, ")")
return True
elif fromJ == toJ:
# search on the column
for i in range (fromI, toI+1):
if elem == A[i][fromJ]:
print("Found at (", i, ",", fromJ, ")")
return True

elif elem > A[midI-1][midJ] and elem > A[midI][midJ-1]:
# ignore left corner
result = find (A, fromI, toI, midJ+1, N, elem)
if result == False:
return find (A, midI+1, M, fromJ, midJ, elem)
else:
# search in left corner
return find (A, 0, midI, 0, midJ, elem)
return False

find(matrix, 0, 3, 0, 3, 10)


* intr-un numar de circ, oamenii se aseaza unul deasupra celuilalt pentru a forma un turn. Asezarea se face astfel incat deasupra sa vina un om mai scund si mai putin greu decat cel sub. Sa se afle cel mai mare numar de oameni din circ care poate forma un astfel de turn, stiind wi, hi greutatile respectiv inaltimile tuturor oamenilor angajati.

Sol.: Problema este echivalenta gasirii unei secvente de oameni ordonate astfel incat urmatorul om in sir sa aiba atat inaltimea cat si greutatea mai mica decat cel de dinaintea lui.
Intai, se sorteaza dupa inaltime. Apoi, se calculeaza cel mai mare subsir crescator in functie de greutate (vezi detalii aici). Acest subsir reprezinta cel mai mare numar de oameni care poate participa la alcatuirea turnului.


* se citeste un flux de numere intregi. Sa se afle rangul unui element (numarul de numere mai mici decat el). Implementati track (int x) care se apeleaza de fiecare data cand un numar este generat, si getRank (int x) care obtine rangul.

Sol.: Se construieste un arbore binar de cautare.
track (x) :  adauga un nod in arbore, detalii aici
getRank (node, x) { 
  if x == node.data 
    return node.leftSize()
  if x < node.data
    return getRank (node.left, x)
  else
    return node.leftSize() + 1 + getRank (node.right, x)
}


cap. 12 - Testari                                                                                 

Testarea programelor:
- manuala vs. automata
- black box vs. white box
White box: set pot testa functii in mod individual, modular. Accent pe validarea I/O
Black box: se testeaza intreg produsul fara sa stii cum este implementat

* un program crapa cand este pornit. Dupa 10 incercari de depanare, se observa ca niciodata nu crapa in acelasi loc. Aplicatia are un singur fir de executie, limbaj de programare C (stdlib). Ce ar putea cauza problema? Cum se poate investiga mai departe?

Sol.: Cauze:
- variabile la intamplare: datele de intrare ale utilizatorului variaza; numere generate aleator; se ia in calcul data/ora/momentul zilei
- variabile neinitializate care pot lua valori la intamplare
- memory leaks: programul a consumat memoria alocata (heap overflow, coruperea datelor pe stiva) => valorile variabilelor depind de alte procese care ruleaza la un moment dat
- dependente externe - alte librarii pot livra valori gresite
Se poate investiga cu runtime tools gen valgrind si altele.


* Cum se poate testa un pix? :)

Sol.: 
1) trebuie puse o multime de intrebari despre: cine va folosi pixul, pentru ce, functionalitati dorite.
2) in functie de raspunsuri, se creeaza un set de constrangeri. In general, atentie la: 
- nevoile/problemele consumatorului si ce se poate astepta in functie de ele -> de exemplu daca utilizatorul este un copil, pasta de pix nu trebuie sa fie toxica
- ce ar trebui sa furnizeze produsul -> scris pe hartie? pe suprafata dura? se verifica daca functioneaza
- ce nu ar trebui sa furnizeze produsul sub nicio forma -> nu ar trebui sa scrie pe pereti? se verifica
- cazuri de utilizare obisnuite 
- cazuri de utilizare pe muchie / exceptii
- conditii de esuare -> cum se poate sparge pixul, este suficient de dur materialul?
- securitate / incredere   -> in cazul de fata N/A

19 mai 2015

Sfat pentru viitorii studenti masteranzi in CACS, UL Louisiana

Acest sfat se adreseaza viitorilor studenti PhD, ai CACS, Louisiana, care inteleg limba romana, adica viitorilor studenti romani ai CACS. De-a lungul timpului, se pare ca a existat doar cate un student roman la un moment dat, asa ca dupa plecarea mea probabil ca cineva imi va lua locul...

Sfatul reflecta atat cat am invatat eu in cei doi ani de studii, despre cursurile care merita sau nu merita, despre profesori, despre examene, finante si alte lucruri de genul acesta. Poate ca va fi util si acelora care studiaza in alta parte, pentru ca ofera un snapshot asupra activitatii dintr-o universitate oarecare din SUA, Louisiana in particular.

Despre cursuri
Contrar asteptarilor mele, cursurile sunt foarte generale si de cele mai multe ori repeta informatiile din anii anteriori. Nu am invatat nimic nou la Algorithm design, Operating Systems, nu as fi invatat nimic nou nici la cursurile de Principles of Computer Network daca le luam, si probabil ca nici la Compiler Design daca as fi facut cursul in anul 4. Asadar, nu trebuie sa va pierdeti timpul prea mult cu aceste cursuri si recomand sa terminati coursework intr-un an si jumatate in loc de 2. Asta este posibil daca va inscrieti la 4 cursuri/semestru in loc de 3, ceea ce nu este o incarcatura prea mare deoarece nu sunt dificile. 
As putea sa detaliez fiecare curs in parte, dar mai bine este sa spun profesorii pe care ii recomand, pentru ca ei vor face cursul valoros sau nu. Asadar, recomand profesorii A. Lakhotia, R. Logan, M. Bayoumi, S. Dasgupta; si nu recomand dr. Tzeng, V. Raghavan. Despre ceilalti am o opinie moderata sau nu ii cunosc suficient de bine.

* Lakhotia: cursurile lui sunt Principles of Programming languages si Compiler design. Sunt bine predate, au teme in fiecare saptamana sau la 2 saptamani, deci mai mult volum de munca fata de alte cursuri. Cu siguranta, preferatele mele dintre toate. Daca ar fi sa reincep viata la UL si as fi in toamna lui 2013, m-as inscrie la Principles of programming languages inca din primul semestru, urmat foarte natural de Compiler design pe al doilea. Terminarea lor poate deschide noi oportunitati de cercetare oferite de dr. Lakhotia pentru cei care au "excelat".

* Logan: cursurile lui sunt Algorithm analysis (materie obligatorie), Bioinformatics si Automated reasoning. In ce priveste primul curs, il recomand mai degraba cu dr. Logan decat cu dr. Tzeng, de altfel conceptele predate sunt de baza, nu au cum sa ridice mari probleme. Bioinformatica este pentru cei curiosi sa afle despre un fel de genetica computationala, destul de interesanta de altfel, chiar daca la vremea cand am luat acest curs predarea nu a fost perfecta. Comparativ cu alte cursuri, e totusi ok. Despre Automated reasoning, cursul este impartit in doua: o parte de logica si o parte de invatare automata. Planul cursului suna excelent, sper doar ca Logan se va tine de el. Recomand analiza algoritmilor in semestrul de primavara cu Logan, dar si celelalte doua cursuri, oferite in primavara si toamna.

* Dasgupta: are doua cursuri, Cognitive Science (toamna) si Advanced topics in computer science (619, history of the birth of computer science, primavara). Dasgupta este un tip excelent, insa ii recomand cursurile doar daca nu aveti alta alegere la dispozitie. Daca totusi sunteti curiosi despre aceste subiecte, mai bine cititi suporturile de curs (Dasgupta are cate o carte despre fiecare). Daca va inscrieti la cursuri nu veti face nimic practic, fiecare curs consta in ascultarea unui monolog-poveste, iar la finele semestrului va trebui sa scrieti eseuri pentru a primi nota.

* V. Raghavan: are doua cursuri, Information retrieval (toamna) si Data mining (primavara). Nu recomand niciunul dintre ele deoarece este extrem de plictisitor. Felul in care vorbeste la ora te adoarme. Suportul de curs consta in slide-uri powerpoint total vraiste din care nu se mai intelege nimic. Si la un moment dat vine la clasa cu o hartiuta cu un scris de mana pe care o proiecteaza pe perete, nici din aceea nu se intelege nimic. Efortul lui pentru sustinerea cursurilor e minim. Pacat pentru ca domeniile in sine sunt foarte interesante.

* M. Bayoumi: in mod obligatoriu veti lua CSCE 595 (graduate seminar) care figureaza sub numele lui dr. Bayoumi. Pentru master trebuie 3 credite din CSCE 595, deci trei semestre. Nu sunt prea multe de zis aici, ci de ascultat si semnat prezenta. Un alt curs oferit este cel de VLSI. Nu am fost interesata si ma indoiesc ca ar fi cineva, in afara de cei orientati catre electrical sau hardware engineering. Tipul e haios si de treaba, mai ales daca esti fata.

* Tzeng: preda doua cursuri, Computer architecture (primavara) si Algorithm analysis (toamna). In privinta arhitecturii, cel mai probabil e ca nu o sa aveti incotro, cursul este aproape obligatoriu pentru master si doctorat. Dureaza cateva saptamani pana va veti acomoda cu accentul lui profund taiwanez, insa este o persoana de o competenta reala si bine intentionata. Pacat doar ca nu are talent didactic.

* Ashok Kumar: cursul lui este de Sisteme de operare, oferit atat toamna si primavara. Probabil ca acest curs se va schimba destul de mult ca structura, de-a lungul timpului. Desi cei mai multi se plang ca este prea multa programare, in realitate nu este, insa scoate la lumina aptitudinile vechi si prafuite de C++ sau Java, iar recent incepe sa aduca in prim-plan si ceva cercetare. Profesorul este bine intentionat, dar este foarte suspicios in privinta copierii.

* Anthony Maida: are in general cate un curs pe semestru, de obicei anuntat destul de tarziu si de care nu toata lumea va sti ca exista. Ambele cursuri se invart in jurul modelarii activitatii neurale, destul de interesant si exotic de altfel, precum Bioinformatics. Pentru curiosi, se merita. Am ascultat mai multe opinii pozitive despre aceste cursuri chiar daca nu am participat la ele. In schimb, un curs gen Advanced topics cu el se va dovedi in scurt timp o pierdere de timp: in afara de 1-2 prezentari nu va rezulta nimic dupa un intreg semestru.

* Se pot lua si cursuri de la alte departamente - este posibil! Se pot face inscrieri la limbi straine (spaniola, franceza sunt bune), istorie, matematica, etc.. O alta posibilitate este doar auditul, dupa ce ati instiintat profesorul respectiv.

La terminarea cursurilor, de obicei dupa 2 ani sau mai putin, ai ocazia sa aplici pentru titlul de master (trebuie sa aplici explicit). In Romania se spune ca masterul te face un specialist intr-un domeniu, iar doctoratul te face expert in acel domeniu. Dupa absolvirea CACS UL, nu te poti numi specialist intr-un domeniu din cauza generalitatii cursurilor, care nu au ca scop specializarea, ci sunt doar o etapa premergatoare cercetarii de doctorat. Probabil ca titlul de "masters degree in computer science" e doar simbolic. De fapt, dupa cum se poate constata la absolvire, pe diploma va fi scris sec doar "Masters of Science". Care science? Ce anume din computer science? Ce se devine dupa obtinerea acestui titlu? 

Notele
Se dau un fel de calificative {A, B, C, D, F, I} . La sfarsitul semestrului se calculeaza un GPA care reprezinta o medie pe o scara 0-4. Dupa un an de GPA 4.0 primesti o invitatie din partea organizatiei Phi Kappa Phi sa intri in cercul lor de excelenta (pe care poti sa o accepti daca vrei sa te vezi cu o medalie in mana, dupa ce ai platit constiincios taxa anuala de membru).
A-F sunt in ordine descrescatoare a valorii, unde F este Failed. I inseamna incomplet, si poate sa rezulte in urma unui curs "special project" sau "advanced topics" sau chiar curs obisnuit la anumiti profesori (gen dl. Bayoumi). Mai exista un calificativ inofensiv, cand te retragi de la o materie - W (withdraw) care nu conteaza la GPA.
In CACS UL lucrurile stau foarte simplu. Cea mai mare parte a studentilor iau A dupa un curs. Unii profesori dau A la prima jumatate de clasa, si B la cea de-a doua. Altii dau A la majoritatea studentilor, mai putin 2-3 codasi care nu isi fac temele. Altii incearca sa se tina de o grila de evaluare spunand ca doar daca reusesti mai mult de 85% o sa iei A. In realitate cred ca lucrurile stau mult mai lejer, si chiar daca grila de evaluare e rigida, profesorii vor compensa acest lucru cu o mai mare dare de mana in corectarea lucrarilor. Nu am auzit niciodata de un student picat, pana cand am ajuns in ultimul semestru si erau trei studenti indieni picati la Sisteme de operare, probabil situatia a fost foarte grava cu ei daca nu au reusit sa treaca.
Este destul de usor sa mentii un GPA maxim. In majoritatea cazurilor, ajuta foarte mult simplul fapt ca iti faci temele constiincios. Nu trebuie sa fii un maestru in programare si nici vreun geniu.

Advisor
Profesorii care au studenti PhD se vor intalni cu ei periodic sub forma unor seminare sau intr-un laborator. Daca aveti deja un advisor sa stiti ca el se poate schimba oricand si nu sunteti legati de el "pe viata". Recomand in primul semestru sa faceti un sondaj amanuntit despre fiecare in parte, pentru ca s-ar putea sa corespunda mai bine intereselor pe care le aveti. De asemenea, daca nu aveti un advisor si sunteti in cautarea lui, unii profesori "recruteaza" studenti prin intermediul cursurilor lor, deci este bine ca in primele 1-2 semestre sa luati cursuri cu profesori cat mai diferiti. O idee buna este si sa discutati cu alti doctoranzi si chiar sa ii vizitati in laboratoare.
Profesorii, in general, sunt foarte deschisi. Daca in Romania sunteti obisnuiti sa fiti un "anonim" pentru un profesor care preda la sute de anonimi, aici, datorita nr. mai mic de studenti dar si a amabilitatii lor, nu mai puteti fi anonimi. Profesorul retine repede numele si daca sunteti buni, e usor sa ramaneti "remarcati". O intalnire banala cu profesorul aduce dialoguri de genul "hello, how are you?" si mai mult de atat, nu doar un "buna ziua" fara ecou.
In unele ocazii, advisor-ul, dar si profesorul de clasa care se simte bine cu studentii lui, va poate invita la o intalnire informala, gen: cina la el acasa de Thanksgiving, sau king cake in laboratorul lui in ziua respectiva, desi, de cele mai multe ori, se stie deja ca de Ziua Recunostintei advisor-ului ii place sa-si invite studentii la el acasa pentru cina :-)

Studentii

Sunt in maaare parte indieni. La inceput aveam urmatoarea impresie: "americanii nu se omoara cu invatatul, isi iau licenta si fug la munca, nu ii intereseaza sa se instruiasca mai mult decat e obligatoriu dpdv social. Asa ca locurile lor sunt luate de indieni, mai ambitiosi, mai constiinciosi". Nimic mai gresit...
Dupa primele semestre mi-am dat seama de un adevar dezamagitor: majoritatea colegilor mei era mult mai slab pregatita decat mine si de asemenea si foarte imatura scolaresc vorbind. Pentru ei nota era sfanta, conta atat de mult pe cat contau pentru mine mediile de 10 in liceu. Nota aceea trebuia obtinuta pe orice cai posibile: copiat, mers la cele mai usoare cursuri, evitarea cursurilor care implica programare sau prea mult efort, etc. Acesti indieni sunt aproape toti studenti la master si nu au bursa. Sunt atat de slabi, si totusi CACS ii primeste pentru ca are nevoie de banii lor. Indienii la randul lor au nevoie de o diploma obtinuta usor, care sa ii propulseze mai departe pe piata de munca americana si mai departe catre green card, etc. Ce e cel mai culmea e ca majoritatea indienilor vin din aceeasi zona din India (Heyderabad) si sunt deja renumiti pentru nivelul de educatie extrem de scazut. Cu toate acestea, CACS/UL are nevoie de bani. Si indienii au nevoie de o diploma.
Mi-am dat seama de inca un fapt ciudat: studentii de la computer engineering habar nu au programare. In special studentii din lab. de VLSI nu au nicio treaba, abia au atins C-ul sau Java. Mi-am dat seama ca poti fi un student de nota A si fara sa stii un bob de programare, prin alegerea cursurilor potrivite, a celor mai usoare, poti fenta sistemul, si daca esti destept, poti sa iesi si doctor fara sa stii sa scrii cod. Suna ireal; poate nu am dreptate, dar cu siguranta ca poti fi onorat, premiat si respectat pentru GPA-ul tau 4.0 chiar daca nu meriti, din pacate..
In schimb, la studentii americani, in totala opozitie fata de cei indieni, se observa un mare simt de fair play si lipsa de coruptie. Studentii iranieni sunt inteligenti, fara indoiala, insa de multe ori actioneaza dupa o agenda proprie si sunt destul de egoisti. Studentii chinezi sunt dintre cei mai unprofessional ever - pur si simplu nu te poti baza pe ei, si nici macar nu te poti intelege normal cu ei, sunt dintr-o alta lume.

Teaching assistantship
Este metoda de supravietuire cea mai usoara a studentilor internationali. Pentru 1100-1200 $/ luna, ai de indeplinit 5-6 ore pe saptamana, fie sustinand un laborator, fie in office hours, fie supraveghind teste si examene, si corectand teme. Cred ca este aproape imposibil sa-ti pierzi bursa, asa ca odata obtinuta o ai pana la sfarsit.
Despre laborator: implica sa inveti studenti din undergrad, 1 ora/saptamana. Pare foarte putin doar o ora, dar atat se face. O sa observi ca acesti studenti in mare parte americani nu prea se obosesc nici macar sa ridice mana sa te intrebe ceva, de obicei ei stau in banca lor si se chinuie singuri sau vorbesc cu un coleg. Rareori apeleaza la TA. Si inca un lucru, in afara orelor, pe strada de exemplu, nimeni nu te recunoaste sa-ti spuna "buna". Relatia ta cu acesti studenti va fi strict in cadrul clasei, si sa nu te astepti sa fii salutat pe strada pentru ca nu o vor face. Absolut nici unul.
In office hours de asemenea, nu vei fi deranjat aproape deloc. Rareori, in cazuri extreme, vei fi vizitat de un student, desi ei nu stiu ce pierd, o oportunitate valoroasa, pe care eu daca as fi avut-o in anii de facultate, as fi utilizat-o la maxim... In aceste momente linistite de office hours, treaba ta e sa stai la calculator si sa pierzi vremea.
La examene si teste, vei observa, in cazul studentilor americani, cat de onesti si fair play sunt. Nu vor vorbi niciodata unul cu celalalt, nu vor intra pe telefon, nu vor incerca sa copieze de nu stiu unde... Daca ai studenti indieni, vei observa cum incep sa sopteasca, cum ies rand pe rand afara invocand toaleta, dar ei de fapt se duc sa-si consulte sursele, vor umbla pe telefon, adica coruptie la scara mica.
In corectarea temelor iti vei da seama de calitatea studentilor. Care e slabuta, atat la cei de undergrad cat si la graduate. Diferenta e ca cei din undergrad vor accepta nota cu serenitate, pe cand cei din graduate, in speta indienii, te vor cauta ca sa mai scoata macar un punct in plus, sau sa te convinga ca au incarcat un fisier gresit, sau sa faca o mica modificare finala pe nu stiu unde...
Later edit: au crescut bursele de la 1200 la 1500 $ , doar pentru studentii la doctorat, desigur. Studentii la master si-au pastrat suma de 750 $ / luna (stiu, este pe jumatate).

Research assistantship
De obicei acest suport financiar este oferit de un profesor care te cunoaste destul de bine si are incredere in tine. RA nu implica sa mai ajuti studenti sau sa corectezi lucrari, ci sa te dedici in totalitate cercetarii. De obicei, TA este oferit primul, pana la terminarea cursurilor obligatorii, urmand ca pe timpul verii sau in timpul semestrului ca PhD sa primesti RA, "daca esti cu minte". Salariul este ceva mai ridicat si convenabil as putea spune (de exemplu un 1500 $), dar depinde si de fiecare profesor in parte, caci se ofera din bugetul proiectului unui profesor si nu din partea CACS.

Comprehensive exam

Este acel examen care te aduce un pas mai aproape de candidatura la doctorat. Pe langa asta, avantajul material este o mica crestere a salariului de asistent. Este bine ca examenul sa se dea cat mai repede, eventual dupa primul semestru sau dupa primul an. 500$ in plus pe semestru conteaza.

Daca vreti sa va opriti dupa Masters degree, fiind admisi pentru PhD
Exista si aceasta optiune. Intrebarea este ce aveti de gand dupa. Daca scopul este un internship in SUA, cel mai convenabil este un OPT (optional practical training). Am pus o prezentare mai detaliata despre asta, aici, care explica pe larg ce inseamna un OPT. In cazul studentilor la doctorat, documentul I-20 pe care il au in vigoare este pe 4 ani, explicit studii doctorale. Daca dupa 2 ani vreti sa faceti o pauza de un internship, singurul legal este CPT (curricular practical training) care are dezavantajul ca facultatea trebuie platita in continuare (3 credite/semestru) pentru a ramane "in sistem" (bursa se pierde). Pentru studentii internationali nu exista posibilitatea "inghetarii" anului.
Daca sunteti siguri ca vreti sa va opriti dupa master, cel mai convenabil este un OPT, pentru care nu trebuie sa platiti nimic la facultate, fiind considerati absolventi. OPT se aplica, in cazul studentilor internationali, acelora care termina acelasi nivel de studii precum cel din documentul oficial I-20. Pentru doctoranzi, micul secret pentru a fi acceptati pentru un OPT este modificarea (ireversibila) a documentului I-20 si asta (atentie) la cel mult un an dupa admitere. Din motive ce tin de interfata sitului de imigratie, modificarea I-20 pentru a scurta perioada se poate face doar in primul an de studii, si odata facuta, in cazul in care doriti sa reveniti pentru doctorat, trebuie reaplicat cu tot cu dosar la universitate. Asadar, optiunea este in cazul in care sunteti foarte hotarati sa va opriti dupa cursurile de master, dar este un pas care ajuta foarte mult eliminand alte complicatii si costuri in plus.

Atitudinea Universitatii
In SUA, universitatea in general, este un brand! Vei vedea masini cu stickere pe care scrie "Ragin Cajuns" sau "LSU" (in cazul Louisianei), in casele absolventilor neaparat o amintire din universitate, fie diploma intr-o rama agatata pe perete, sau un trofeu, sau altceva. Cu cat mai mare e universitatea, cu atat mai mare e mandria.
Universitatea si UL in particular, au tot interesul sa intretina aceasta atmosfera. UL are un magazin de suveniruri, cu tricouri, haine, fulare, bijuterii, cani si tot tacamul pe care scrie, firesc, UL Ragin Cajuns... Preturile nu sunt deloc "studentesti". Spre sfarsitul semestrului, universitatea va face presiuni sa-ti cumperi roba de absolvire, sa cumperi o rama in care sa-ti pui diploma, sa-ti cumperi un trofeu pe care e scris "absolvent promotia..." si chiar sa-ti cumperi un inel cu UL la cateva sute de dolari. Ca student international, daca ar fi sa cumperi tot, ar insemna sa nu mai mergi acasa in vacanta pe anul acela.
De multe ori, si asta este de fapt specific american, universitatea imbina anumite evenimente cu oferirea unui pranz/snacks gratuit. Asa ca uneori, in CACS, dupa terminarea seminarului de vineri dimineata, se ofera pizza, sau Zeus, sau mancare Cajun..

Cat de mult ajuta CACS la gasirea unui job
CACS incearca de mai multa vreme sa aduca companii care sa vorbeasca despre oportunitati de munca. Nu vin Google sau Amazon, ci firmele sunt cu preponderenta din Louisiana. Se remarca insistenta unor firme ca Fugro si CGI, care au prezentari cu totul plictisitoare si cu toate acestea vin sa viziteze CACS in fiecare semestru. Nu ma indoiesc ca un absolvent are sansa oricarui loc de munca si multi dintre ei au reusit deja in cea mai populara destinatie - California.
Later edit: a venit Google (sau ma rog, un reprezentant absolvent de Computer science de aici), si am vazut si anunturi de internship din partea Amazon :) CGI preseaza in continuare ca sa atraga cat mai multi angajati in Lafayette, atat din zona cat si din orasele invecinate.

Concluzii - rezumat - de avut in vedere
1) Examenul comprehensive dupa primul semestru
2) Stabilirea unui traseu dupa cel mult un an - Phd or not?
3) Terminare titlu de master intr-un an si jumatate
4) Profita de libertatea de alegere a cursurilor, care pot fi si din afara specializarii, daca te pasioneaza si altceva 

Succes.
15 mai 2015

Later edit: 13 octombrie 2015

07 mai 2015

Linux: find text/file

> Cautare text intr-un fisier din folder:
grep -rnw 'numeFolder' -e "textDeCautat"
> Cautare fisier dupa nume, in folder:
find numeFolder -name "numeFisier"

24 aprilie 2015

Probleme pentru interviu: Probabilitati, OOP, Recursivitate si Programare dinamica

cap. 7 - Math & probabilities                                                         

* exista doua feluri de a trage in poarta la fotbal: (1) ai o singura incercare sa dai gol; (2) din 3 incercari trebuie sa dai 2 goluri. Daca p este probabilitatea de a reusi un gol, pentru ce valori ale lui p ar trebui sa alegi varianta (1) sau (2)? incercarile sunt independente intre ele.

Sol.: (1) P(castig) = p orice ai face. Pentru (2), P(castig) = P(3 goluri) + P(2 din 3 goluri in oricare ordine) = p^3 + 3 * p^2 (1-p)  => ca (1) sa fie varianta aleasa, p<= 0.5 , altfel  varianta (2)


* implementati operatiile - , * , / pentru numere intregi folosind doar operatorul +

Sol.:    int multiply(int x, int y) {  int sum = 0;
             for (int i=0; i<y; i++) sum += x;
             return sum; }

  int negate (int a) { int neg = 0;
    int d = a < 0 ? 1 : -1; // semnul opus al lui a
    while (a != 0) {
      neg += d;
      a += d; }
    return a; }

  int minus (int a, int b) { return a + negate(b); }

  Impartire: (1) a, b > 0 =>  daca a > b => algoritmul cu scadere repetata
                                            daca a = b => 1
                                            daca a < b => 0
                   (2) a = 0  =>  0
                        b = 0  => eroare
                   (3) a si/sau b < 0  => negate(a) si/sau negate(b) si re-executie


* 3 furnici se afla pe laturi diferite ale unui triunghi. Fiecare furnica isi alege o directie si porneste in ea. Fiecare directie are probabilitate egala de alegere. Care este probabilitatea sa existe o coliziune?

Sol.: Fie d1, d2, d3 directiile care pot fi {in sensul acelor, trigonometric} .
daca d1 = d2 = d3 => P(meet) = 0
daca d1 = d2 != d3 sau oricare alta combinatie => coliziune
P (coliziune) = P (d1 = d2 != d3) + P (d1 != d2 = d3) + P (d1 = d2 != d3) = 1 - P (d1 = d2 = d3) 
Cum toate cele 4 combinatii sunt exhaustive si au sanse egale => sansa e 1/4 => P (coliziune) = 3/4


* algoritm pentru aflarea celui de-al k-lea numar a.i. singurii factori primi ii sunt 3, 5 sau 7
Exemplu, primele numere sunt: 3, 5, 7, 9, 15, 21, 25, 27, 35, 45, 49, 63, 75, .....

Sol.: Idee - "urmatorul" numar este un produs de puterile lui 3, 5 sau 7. Toate numerele generate se tin intr-un sir. Exista 3 pointeri pentru pozitia curenta (pt numerele 3, 5, 7) care denota puterea cu care e folosit nr respectiv ca factor. Exista un pointer global pt dimensiunea sirului final. La fiecare pas se alege cel mai mic numar din cele 3 generate si care este mai mare decat numarul cel mai recent generat. 

public class Ex75 {

    private int getNumber (int k) {
        ArrayList<Integer> numbers = new ArrayList();
        numbers.add(3); 
        numbers.add(5);
        numbers.add(7);
        
        if (k < 0) {
            System.err.println("Type k > 0");
            return -1;
        }
        else if (k <= 2) 
            return numbers.get(k);
        
        int p1 = 0, p2 = 0, p3 = 0; // current pointers
        int mainp = 2;  // pointer to index of the last element
        
        while (numbers.size() <= k) {
            int res1 = numbers.get(p1) * 3,
                    res2 = numbers.get(p2) * 5,
                    res3 = numbers.get(p3) * 7;
            
            if (res1 > numbers.get(mainp) && res1 <= res2 && res1 <= res3) {
                numbers.add(res1);
                p1++;
                mainp++;
                if (res2 == res1) p2++;
                if (res3 == res1) p3++;
            }
            else if (res2 > numbers.get(mainp) && res2 <= res1 && res2 <= res3) {
                numbers.add(res2);
                p2++;
                mainp++;
                if (res2 == res1) p1++;
                if (res2 == res3) p3++;
            }
            else if (res3>numbers.get(mainp) && res3 <= res1 && res3 <= res2) {
                numbers.add(res3);
                p3++;
                mainp++;
                if (res3 == res1) p1++;
                if (res3 == res2) p2++;
            }
            else {
                // update all pointers
                p1++; p2++; p3++;
            }
        }
        
        for (int number : numbers) {
            System.out.print(number + " ");
        }
        System.out.println();
        
        return numbers.get(numbers.size() - 1);
    }
    
    public static void main(String[] args) {
        Ex75 exercise = new Ex75();
        // print the first 30 numbers with this property
        exercise.getNumber(30);
    }  
}


cap 8. OOP                                                                                                      

La acest capitol, raspunsurile tin de imaginatia fiecaruia, neexistand solutie unica. De fapt, rezolvarile sunt mai mult descriptive decat algoritmice, si anume modelarea unor clase cu anumite proprietati si care sa conlucreze bine.

Se au in vedere urmatoarele design patterns:
* singleton - o clasa care poate avea o singura instanta, accesul la instanta avand loc in cadrul aplicatiei
ex.   public class Restaurant {
          private static inst = null;
          public static Restaurant getInstance () {
            if (inst == null) { inst = new Restaurant (); }
            return inst; 
         }
       }
* factory method - existenta unei interfete pentru crearea unei instante a clasei, in care se decide carei subclase ii va apartine instanta

Exemple de intrebari (fara rezolvare):
* proiectarea unui lot de parcare folosind OOP 
* implementarea unui puzzle
* sistem de fisiere, etc.


cap. 9 - Recursivitate si Programare dinamica
In acest capitol, diferenta intre recursivitate si DP este ca DP are un plus de memorie care mai taie din intensitatea computationala a recursivitatii (vezi divide et impera) . Majoritatea programelor se pot rescrie din recursivitate in DP cu adaugarea unui caching.

* exista o scara care are N trepte. Un copil poate urca 1, 2 sau 3 trepte odata. In cate feluri posibile poate el sa ajunga in varful scarii?

#define MAX 100
// recursion: bottom-up - de la 0 trepte urcate pana ajunge la N
int ways = 0;

void runup1 (int n, int current) {
if (n <= current) {
if (n == current) ways++; // valid path completed
return;
}
runup1(n, current+1);
runup1(n, current+2);
runup1(n, current+3);
}

// dp: top-down - de sus in jos
int runup2 (int n, int map[MAX]) {
if (n<0) return 0; // invalid path
if (n==0)  return 1; // valid path completed
if (map[n] > -1) {
return map[n]; 
// nr. of ways you can run up to that point was already computed and cached
}
// else - compute and cache it
map[n] = runup2(n-1, map) + runup2(n-2, map) + runup2(n-3, map); /* cache nr. of ways you can  
reach height n as: nr. of ways you can reach via 1 step ahead + ..2 steps + ..3 steps ahead */
return map[n];
}

int main() {
int map [MAX],i;
for (i=0; i<MAX; i++) map[i] = -1;
printf("He ran in %d ways\n" ,runup2(4, map));
return 0;
}


* intr-un sir, indexul "magic" este nr. i pentru care  A[i] = i . Dandu-se un sir sortat de intregi distincte, scrieti o metoda pentru a afla un index magic in A . 

Sol.: ceva asemanator cu cautarea binara 

int magicIndex ( int myArray, int start, int stop ) {
  int mid = (start + stop) / 2; 
  if (stop < start) return -1;
  if (myArray [mid] == mid ) return mid;   /* index magic */
  if (myArray[mid] < mid ) {
    // partea stanga este exclusa, este prea inapoi, iar numerele sunt distincte, diferenta nu va fi acoperita
    magicIndex (myArray, mid+1, stop);
  }
  else {
    magicIndex ( start , mid-1 );
  }
}


* sa se afle toate submultimile unei multimi (pt. o multime cu n elemente exista 2^n submultimi)

Sol.:  pp A = {a1, a2, a3, ... , an } , atunci submultimile ce includ elemente cu nr. de ordine cel mult k sunt:
         k = 0 => {}
         k = 1 => {} , { a1 }
         k = 2 => {} , { a1 } , { a2 } ,  { a1, a2 } = P(2)
         k = 3 => P(2) + { a3 } + { a1, a3 } + { a2, a3 } + { a1, a2, a3 }
                   =  P(2) + clonele lui P(2) adaugand a3 la ele
         ...
         k = n  => P(n-1) + clonele lui P(n-1) adaugand an la ele

// pseudocod
void generate (int index, list<int> initialList) {
  if (index == 0)  return new emptyList;
  else {
    int currentElem = initialList.get(index);
    int prevLists = generate(index - 1, initialList);
    list <list <int>> newLists = init ();
    copy (newLists , prevLists);
    for ( mylist : prevLists ) {
      newLists.add ( mylist.add(currentElem));
    }
    return newLists;
}


* avem un numar infinit de monezi de 25 bani, 10 bani, 5 bani si 1 ban. In cate feluri de poate reprezenta suma de N bani?

Sol.:  am inlocuit banii cu centi.
# change(100) = change(100) using 0 quarters + 0 dimes
#   = change(100) using 0 quarters + 1 dime 
#   = change(100) using 0 quarters + 2 dimes
#   = ....
#   = change(100) using 0 quarters + 10 dimes -> SOLUTION!
#   = etc
# AND SO ON

# solutia considera monezi de la cele mai mari la cele mai mici

# n = amount of money
# denom = the largest coin available
# coin set is {25, 10, 5, 1} cents
# 25 = quarter, 10 = dime, 5 = nickel, 1 = penny
def change (n, denom):
next_denom = 0
if denom == 25:
next_denom = 10
elif denom == 10:
next_denom = 5
elif denom == 5:
next_denom = 1
elif denom == 1:
# there is no less denomination
# means a single way to pay the rest,
# using pennies
return 1
ways = 0
i = 0
while i * denom <= n:
# assume i*denom was used with the current denomination, 
# in how many ways we can give the rest using next denom?
ways += change (n-i*denom, next_denom)
i += 1
# all combinations with our current denom were used so far
return ways

# how many ways you can make this amount using
# coins less or equal than 25
print change(26, 25)


* avem o stiva cu N cutii, cu dimensiunile respective wi, hi, di. Cutiile nu se pot roti, dar se pot pune una deasupra alteia daca cutia de deasupra e mai mica decat cea de dedesubt in privinta tuturor celor 3 dimensiuni. Scrieti o metoda prin care se poate construi cea mai inalta stiva posibila, inaltime = suma inaltimilor tuturor cutiilor.

Sol.:    
createStack (boxes, bottom) {
  int max_height = 0;  List<Box> maxStack = null;
  for (int i = 0; i< boxes.length; i++ ) {
    if (boxes[i].canBeAbove (bottom)) {
      // TODO: ignora cutiile deja considerate, aflate sub bottom
      List<Box> new_stack = createStack (boxes, boxes[i]);
      new_height = getHeight(new_stack);
      if (new_height > max_height ) {
        max_stack = new_stack;
        max_height = new_height;
     } 
   }
  }
  if (max_stack == null) { max_stack = new ArrayList<Box> (); }
  if (bottom != null) { max_stack.add (0, bottom); {
  return max_stack;
}

Imbunatatire: cache,  un HashMap <Box, List<Box>> , unde cheia reprezinta cutia de la fund iar valoarea este cea mai buna stiva gasita pentru acest fund.