The oral exams will take place Monday January 10, 2005 and Tuesday January 11, 2005. The exam takes 20 minutes, including evaluation. The exam will be a discussion of the reports on the three projects and the material covered in class. The final grade will be based on the project reports and the oral examination. A grad will be given on the 13-scale.
The exam takes place in Turing-016.
|1.||[BKOS] Computational Geometry: Algorithms and Applications. Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Second Edition. Springer-Verlag, 367 pages, 2000. ISBN: 3-540-65620-0.||Chapters 1-3, 5, 6.1-6.2, 7, 8.2, 9.1-9.3, 10 , 11.1-11.2, 12-15, 16.1-16.3|
|2.||[C96] Timothy M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete and Computational Geometry, 16, pages 361-368, 1996.||Sections 1-2, 4|
|3.||[ST86] Neil Sarnak, Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, 29(7), 1986, pages 669-679.||All|
|4.||[O83] Mark H. Overmars, The Design of Dynamic Data Structures, Volume 156 of Lecure Notes in Computer Science, 1983.||Chapter 7|
|5.||[S98] Sven Skyum, Lecture note on Introduction to lower bounds, February 1998.||Chapter 11|
|6.||[A03] Sanjeev Arora, Approximation schemes for NP-hard geometric optimization problems: A survey. Appeared in Math Programming, August 2003.||Sections 1-2|
|7.||[BGH99] Julien Basch, Leonidas J. Guibas and John Hershberger, Data Structures for Mobile Data, Journal of Algorithms, 31(1), 1999, pages 1-28.||Sections 1, 4|
|8.||[H04] Herman J. Haverkort, Introduction to bounding volume hierarchies, Manuscript, May 2004.||All|