# Computational Geometry

## CS 498 TC, Spring 2021

### Main❖Syllabus❖Schedule❖Resources

Caveat
This is my first time teaching a 400-level special topics course, and my first time teaching a computational geometry class in ocver a decade, so I'm still figuring out lots of stuff on the fly! I may need to change some aspects of this syllabus as the semester progresses; I will announce any significant changes well in advance of their effect.

Prerequisites
CS 374 or an equivalent undergraduate algorithms course. Specifically, the course assumes a solid background in the following:
• Basic algorithm design techniques (divide-and-conquer, dynamic programming, graph modeling, ...)
• Basic graph problems/algorithms (traversal, topological sort, shortest paths, ...)
• Basic data structures (balanced binary trees, priority queues, hashing, adjacency lists, ...)
Familiarity with discrete probability and basic linear algebra is also helpful.

Recommended Reading
Most of my lectures will follow these sources fairly closely.

I will provide additional typeset lecture notes and/or paper links as necessary. You can find additional useful references on the resources page.

Credit
Like most 400-level classes in computer science, this class is offered on two sections:
• Section TC3 is for undergraduates and is worth 3 credits.
• Section TC4 is for graduate students and is worth 4 credits.
Undergraduates can earn honors credit by doing the additional work required for the graduate section. Please contact Jeff for details.

Grading
Course grades will be based on 4–6 biweekly(ish) homework assignments, a midterm exam, a final exam, and (for section TC4 only) a paper presentation.
• Section TC3: 40% homework + 25% Midterm + 35% final exam
• Section TC4: 35% homework + 20% Midterm + 30% final exam + 15% presentation
Homework averages will be based on the highest $c\cdot k$ homework scores, where $c$ is the number of credits and $k$ is the number of homework assignments.

Policies
We will follow essentually the same course policies as CS 473. In particular:
• Students who require accommodation for a disability should work with DRES to provide Jeff with an accommodation letter as soon as possible. In particular, exam accommodations require an accomodation letter at least one week in advance. Please ask Jeff for further details.
• Teams of up to three students can submit joint homework solutions. All team members should be listed on the first page of each homework submission.
• Homework will be submitted on Gradescope as separate PDF files for each problem. Exactly one team member should upload each solution and identify all other team members.
• I strongly encourse students to collaborate on homework (and practice for exams) in larger study groups, as long as each submitted solution is written independently and cites contributions from larger groups amd/or their members. Collaboration on exams is not allowed.
• No late work will be accepted for any reason; the deadline is the deadline. (Remember that the lowest several homework scores will be dropped.) However, I may forgive homework or even the midterm under extreme circumstances, such as a documented disability, illness, injury, or other emergency. Please contact Jeff as soon as possible.
• Whenever a homework or exam problem asks you to design an algorithm, your solution should include a clear description of the algorithm (usually in pseudocode), an analysis of the running time, and justification of correctness (if correctness is not obvious). Faster algorithms are worth more points, but only if they are correct.
• Homework and exam grades will depend not only on correctness and speed, but also on clarity and style. Your solutions should be complete and mathematically precise, but at the same time, easy to understand and concise. Don't submit your first draft!
• Academic integrity: Generously cite your sources. Use your own words. Don't put your name on work that isn't yours.

Important information about university policies regarding academic integrity, anti-racism and inclusivity, disability accommodations, FERPA rights, religious observances, and sexual misconduct reporting are listed on a separate page.

Advice
• Kindness > Honesty > Clarity > Correctness > Efficiency. First make it clear; then make it work; then make it fast; then make it faster. (Notice that “perfection” and “cleverness” don't even make the list.)
• Homework will be due roughly every other week, but I strongly recommend starting on each homework assignment as soon as it is released. Don't wait until two days before the deadline to start!
• I strongly recommend typesetting your homework solutions in LaTeX, especially if you have poor handwriting. (I'll post a LaTeX homework template here soon.) If you must handwrite your solutions, please write using dark ink (not pencil) on plain white unlined paper, and please use a scanning app (to align margins, increase contrast, and the like) instead of uploading raw photos.
• For this course especially, illustrations can be extremely helpful in communicating intuition and examples, but don't confuse intuition and examples for mathematical precision. I strongly recommend using a vector-graphics program like Ipe, Inkscape, LibreOffice Draw, or OmniGraffle. Every picture is worth 1000 words, so you should take as much time and care creating each picture as you would writing 1000 words.