The course meets 3:30--4:45 pm Tuesday and Thursday at 3321 SC (Seaman Center).

Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, email:firstname-lastname@uiowa.edu.

Walk-in hours: Monday 10:30--12:00, Wednesday 10:30--12:00; 101D MLH.

This is an algorithms course where the algorithms handle geometric data. We will cover:

- geometric structures such as convex hulls, triangulations, and Voronoi diagrams
- representations of these structures and algorithms for computing them
- algorithm design techniques such as line sweep, randomized incremental construction, sampling, space partitions, and multiplicative weights update
- data structures for nearest neighbor search, range search, etc

We will use the textbook *Computational Geometry: Algorithms and Applications* by de Berg, Cheong, van Kreveld, and Overmars. An electronic version of its 3rd edition, from 2008, is available from the UI library.

In addition to the above, we may cover material from surveys or research papers. You will also have an opportunity to do this in your expository paper, see below.

I will assign four to six homework assignments, some of which may involve programming. There will be one take-home exam towards the end of the course. Each student will also write an expository paper on a topic that I will help choose -- this can be done either individually or in teams of two.

The homework will account for 45 percent of the grade, the exam for 20 percent, and the paper for 25 percent. The remaining 10 percent is for engagement. Several things will contribute to this last category -- involvement in class; explaining your home work solution when I call upon you to do so; keeping me up to date about the topic of your paper and being timely about discussing any roadblock you may face in executing it.

The policy on late homework is that you have a quota of four days for the entire semester that you may use for late submissions. So for example, there will be no penalty if you submit the third homework two days late, the fifth two days late, and the rest of the homework assignments on time. Once you use up your quota of four days, any homework submitted late will not be accepted and you will get 0 points for that homework. No individual homework can be late by more than two days. (I don't count the weekends/holidays -- if an assignment is due 1:45 pm on Thursday, and you submit it by 1:00 pm the following Monday, you will be two days late.)

When you submit a homework X days late, your quota gets decreased by X irrevocably. You can only be late by an integer number of days -- if you submit 10 hours after the deadline, for example, your quota is depleted by one day.

We will keep track of what we covered each week here.

- First Day Handout
- Homework 1, due in ICON by 11:59 pm, Thursday, February 6.
- Homework 2, due in ICON by 11:59 pm, Tuesday, February 25.
- Homework 3, due in ICON by 11:59 pm, Thursday, March 12.