1. Un sir de lungime n contine numere intregi din multimea {1, 2, ..., n-1}. Folosind Principiul lui Dirichlet deducem ca cel putin un element se repeta. Gasiti un algoritm liniar care afiseaza o valoare ce se repeta, folosind memorie suplimentara constanta si nemodificand la nici un pas vreun element din sir.

2. Se dau n numere de la 1 la n. Unul din ele unul apare de doua ori in sir, iar restul sunt distincte. Evident ca un numar nu va aparea niciodata. Sa se dea un algoritm cat mai eficient care sa determine numarul lipsa si numarul ce apare de doua ori.

2. Se dau n numere de la 1 la n. Unul din ele apare in sir de doua ori, iar restul sunt distincte. Evident ca un numar nu va aparea niciodata. Sa se dea un algoritm cat mai eficient care sa determine numarul lipsa si numarul ce apare de doua ori.

*Literatura:*

{'Finding duplicates in a data stream, P Gopalan, J Radhakrishnan - … of the Nineteenth Annual ACM-SIAM …, 2009':'http://www.cadmo.ethz.ch/education/lectures/FS09/RA_PM/duplicates_datastream.pdf'} Aici se arata un algoritm randomizat ce foloseste o parcurgere si O(log^3(n)) memorie.

{'Finding a duplicate and a missing item in a stream, J Tarui - Proceedings of the 4th international conference on …, 2007':'http://www.jtlab.ice.uec.ac.jp/~tarui/tarui-tamc07.pdf'} Aici se demonstreaza ca pentru algoritmi deterministi la k parcurgeri trebuie folosita cel putin O(n^(1/(2k - 1)) spatiu, iar pentru algoritmi ce folosesc doar O(log n) spatiu e nevoie de cel putin O(log n/log log n) parcurgeri.
 

{'Finding a duplicate and a missing item in a stream, J Tarui - Proceedings of the 4th international conference on …, 2007':'http://www.jtlab.ice.uec.ac.jp/~tarui/tarui-tamc07.pdf'} Aici se demonstreaza ca pentru algoritmi deterministi la k parcurgeri trebuie folosita cel putin O(n^(1/(2k - 1)) spatiu, iar pentru algoritmi ce folosesc doar O(log n) spatiu e nevoie de cel putin O(log n/log log n) parcurgeri.