O lista cu paperuri misto, care sunt avansate au ceva * in fata, cine adauga un paper ar trebui sa zica pe scurt de ce se merita sa citeasca cineva paperu respectiv.

h1. Cool research papers

'Suffix arrays: A new method for on-line string searches':webglimpse.net/pubs/suffix.pdf
 

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 |_{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). |
| 'Computational Complexity: A Modern Approach':http://www.cs.princeton.edu/theory/complexity/book.pdf | ==user(user="azotlichid" type="tiny")== | 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':http://www.ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf | ==user(user="mpatrascu" type="tiny")== | Era un classic pe Lista lui Francu |
| 'Simple Linear Work Suffix Array Construction':http://www.cs.helsinki.fi/juha.karkkainen/publications/icalp03.pdf | ==user(user="mpatrascu" type="tiny")== | Un algoritm de construit suffix trees/array absolut superb. |
| 'Dynamic Transitive Closure via Dynamic Matrix Inverse':http://www.mimuw.edu.pl/~sank/pub/sankowski_focs04.ps | ==user(user="mpatrascu" type="tiny")== | Ca sa ne convingem ca n-am invatat algebra de clasa 11 degeaba. |
| Level ancestor | ==user(user="Cosmin" type="tiny")== | ? |
| Minimal diameter spanning tree | ==user(user="Cosmin" type="tiny")== | ? |
| Smallest polygon containing k points | ==user(user="Cosmin" type="tiny")== | ? |
| Fenwick trees | ? | ? |
| '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.  |