h1. Cool research papers

O lista cu paperuri misto - cele avansate au stelute ('*') in fata in functie de cat de _avansate_ sunt. Cine adauga un paper ar trebui sa zica pe scurt de ce merita citit.

O lista cu paper-uri misto. Cine adauga un paper ar trebui sa zica pe scurt de ce merita citit.

table. |_. Paper |_. Cine l-a pus |_. De ce merita citit |
| 'Text Algorithms W. Rytter':http://web.njit.edu/~rytter/TEACHING/TEXTS/book.html | ==user(user="Cosmin" type="tiny")== | Carte cu o gramada de algoritmi pe stringuri, scrisa de un antrenor al lotului polonez. |

table. |_. Paper |_. Cine l-a pus |_{width:30%}. De ce merita citit |
| 'Text Algorithms':http://web.njit.edu/~rytter/TEACHING/TEXTS/book.html | ==user(user="Cosmin" type="tiny")== | 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':http://webglimpse.net/pubs/suffix.pdf | ==user(user="Cosmin" type="tiny")== | ? |
| 'Cuckoo hashing':http://cs.nyu.edu/courses/fall05/G22.3520-001/cuckoo-jour.pdf | ==user(user="Cosmin" type="tiny")== | ? |
| 'An O(ND) Difference Algorithm and Its Variations':http://www.xmailserver.org/diff2.pdf | ==user(user="Cosmin" type="tiny")== | 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). |

| 'Dictionary matching and indexing with errors and dont cares':http://www.cs.nyu.edu/cs/faculty/cole/papers/CGL04.ps | ==user(user="flmanea" type="tiny")== | Cateva probleme interesante pe siruri cu wild-carduri |
| 'Dynamic dictionary matching and compressed suffix trees':http://www.cs.pitt.edu/~hlchan/research/publications/soda05-chan.pdf | ==user(user="flmanea" type="tiny")== | Din nou algoritmi pe siruri. |
| 'Rank Aggregation Methods for the Web':http://www10.org/cdrom/papers/577/index.html | ==user(user="flmanea" type="tiny")== | Un articol interesant despre clasamente si combinarea lor, in contextul cautarii pe web. |

| 'Finding an Optimal Tree Searching Strategy in Linear Time':http://www.cs.brown.edu/~shay/BST.pdf | ==user(user="azotlichid" type="tiny")== | Arbori binari de cautare optimali in O(N) |
| 'An Efficient Context-Free Parsing Agorithm':http://www.cs.cmu.edu/afs/cs.cmu.edu/project/cmt-55/lti/Courses/711/Class-notes/p94-earley.pdf | ==user(user="flmanea" type="tiny")== | 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':http://www.cs.princeton.edu/%7Ers/talks/LLRB/RedBlack.pdf | ==user(user="rgrig" type="tiny")== | Implementare mai simpla pentru arbori Rosu-Negru. Merita citita si discutia de la pagina 'asta':http://geomblog.blogspot.com/2008/02/notes-from-dagstuhl-i-red-black-trees.html (later edit, flmanea) |
| 'Treaps':http://www.win.tue.nl/~speckman/CourseMat/04-treaps.pdf | ==user(user="cosmin" type="tiny")== | 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':http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf | ==user(user="flmanea" type="tiny")== | 'Premiul Godel':http://sigact.acm.org/prizes/godel/ in '2007':http://sigact.acm.org/prizes/godel/2007.html.  |