MIT team finds that the ratio of component atoms is vital to performance.
Mihai Patrascu, a junior majoring in mathematics, has been named the national Outstanding Male Undergraduate by the Computing Research Association.
Patrascu's research is in the area of data structures and algorithms. He has solved three major open problems during his three years at MIT. While still a freshman, Patrascu solved a problem in data structures that had remained open for the last 20 years--tight upper and lower bounds on the partial-sums problem. As a sophomore, he proved logarithmic lower bounds for several problems that had been conjectured to require logarithmic time for more than 20 years. And in his fourth semester at MIT, he made a major breakthrough in dynamic optimality for binary search trees.
These and related results have been published in two papers from the top theoretical computer science conferences, and in two separate papers at the premier algorithms conference. He has published four additional papers.
Patrascu also has a perfect academic record. Before entering MIT, he received numerous silver and gold medals in Informatics Olympiad competitions. Since then, he has worked as a volunteer to help organize the high-school Olympiads in Romania and the Balkans. He plans to attend graduate school to continue his study of theoretical computer science.
The Computing Research Association seeks to strengthen research and advanced education in computing and allied fields. It counts among its members more than 200 North American organizations active in computing research. It was formed in 1972 as the Computer Science Board to provide a forum for the chairs of Ph.D. granting computer science departments to discuss issues and share information.
Andrea Grimes of Northeastern University received the board's Outstanding Female Undergraduate award.