Cool research papers
O lista cu paper-uri misto. Cine adauga un paper ar trebui sa zica pe scurt de ce merita citit.
| Paper | Cine l-a pus | De ce merita citit |
|---|---|---|
| Text Algorithms |  Cosmin Negruseri •Cosmin | Carte cu o gramada de algoritmi pe stringuri, scrisa de un cercetator francez (M. Crochemore) si de un cercetator polonez (W. Rytter) cu rezultate bune in stringology (Rytter este si antrenor al lotului polonez). |
| Suffix arrays: A new method for on-line string searches | Cosmin Negruseri •Cosmin | ? |
| Cuckoo hashing | Cosmin Negruseri •Cosmin | ? |
| An O(ND) Difference Algorithm and Its Variations | Cosmin Negruseri •Cosmin | Distanta de editare in O(n) memorie (cum am dat eu la GInfo), in O(d*n) timp unde d este distanta de editare finala (cum a dat Mars la ONI). |
| Computational Complexity: A Modern Approach |  Adrian Vladu •azotlichid | Calculabilitate, clase de complexitate, algoritmi de aproximare si aplicatii. Scrisa de doi profi de la Princeton si oferita gratuit pe net. |
| The LCA Problem Revisited |  Mihai Patrascu •mpatrascu | Era un classic pe Lista lui Francu |
| Simple Linear Work Suffix Array Construction | Mihai Patrascu •mpatrascu | Un algoritm de construit suffix trees/array absolut superb. |
| Dynamic Transitive Closure via Dynamic Matrix Inverse | Mihai Patrascu •mpatrascu | Ca sa ne convingem ca n-am invatat algebra de clasa 11 degeaba. |
| Level ancestor | Cosmin Negruseri •Cosmin | ? |
| Minimal diameter spanning tree | Cosmin Negruseri •Cosmin | ? |
| Smallest polygon containing k points | Cosmin Negruseri •Cosmin | ? |
| Fenwick trees | ? | ? |
| Dictionary matching and indexing with errors and dont cares |  Florin Manea •flmanea | Cateva probleme interesante pe siruri cu wild-carduri |
| Dynamic dictionary matching and compressed suffix trees | Florin Manea •flmanea | Din nou algoritmi pe siruri. |
| Rank Aggregation Methods for the Web | Florin Manea •flmanea | Un articol interesant despre clasamente si combinarea lor, in contextul cautarii pe web. |
| Finding an Optimal Tree Searching Strategy in Linear Time | Adrian Vladu •azotlichid | Arbori binari de cautare optimali in O(N) |
| An Efficient Context-Free Parsing Agorithm | Florin Manea •flmanea | O lucrare de inceput in teoria limbajelor formale, interesanta mai ales din punct de vedere istoric. Algoritmul prezentat este un punct de plecare in multi algoritmi de parsing folositi si acum. Autorul, Jay Earley, a scris doar vreo 10 lucrari de CS, si acum e psiholog, dar aceasta e considerata drept una dintre lucrarile de mare importanta in informatica teoretica a secolului trecut. |
| Left-leaning Red-Black trees |  Radu Grigore •rgrig | Implementare mai simpla pentru arbori Rosu-Negru. Merita citita si discutia de la pagina asta (later edit, flmanea) |
| Treaps | Cosmin Negruseri •Cosmin | Treapurile sunt arbori echilibrati foarte simplu de implementat. Mult mai curati si ceva mai eficienti decat arbori Rosu Negru sau arborii AVL. Fara atatea cazuri la care sa fii atent. Nu se predau la scoala pentru ca demonstratia ca in medie operatiile iau O(log n) timp este mai dificila, dar in concursurile de programare sunt ideali. Ar trebui sa ii puteti implementa in 15 minute dupa ce ii intelegeti, fara a toci bucati de cod pe de rost. |
| Natural Proofs | Florin Manea •flmanea | Premiul Godel in 2007. |
