Just van Rossum, via DrawBot
Thanks everyone for a great semester! (Well, you know, except for that whole pandemic thing.)
Regrade requests can be submitted until Friday, June 11.
The exam will cover all material in the class through April 15—including line arrangements, but not the funnel algorithm, Minkowski sums, or visibility graphs—or equivalently, the material actually covered in the homeworks (except HW5.4). The final exam will have a bit more emphasis on material presented after the midterm.
You may find the exams and practice material from David Mount's recent computational geometry class helpful. You can also find good study problems in the appropriate chapters of “Four Marks”.
The format and length of the final exam will be exactly the same as the midterm.
This is an open-book but closed-everything-else exam. You are welcome to use any of this semester’s official course materials—including the recommended textbook, lecture notes, lecture scribbles, lecture videos, and homework solutions—and anything you write yourself before starting the exam. All other materials—including course materials from past semesters, materials from courses elsewhere, other internet resources, other textbooks, and (most importantly) other people—are not permitted. Do not communicate with anyone about the exam before Monday at 10pm.
You will submit your midterm solutions as a single PDF file. I recommend writing and drawing your solutions by hand and then scanning to create your PDF, but you are welcome to use LaTeX/Google Docs/Word/whatever if you can do that quickly enough. As with homework, you can submit as many times as you like; only the most recent submission before the deadline will be graded.
There is a "Practice Midterm 1" on Gradescope with the same format as the actual midterm, but with a 60-minute time limit. (The questions on the practice exam are just Homework 2.) I strongly recommend scanning and uploading a hand-written test document to see how long the entire process takes.
The exam will cover the same material as Homeworks 1 and 2: convex hulls, duality, segment intersection, plane sweep, point-in-polygon testing, winding numbers, planar straight-line graphs, and Euler's formula. This roughly corresponds to Chapters 1–3 of “Four Marks” (plus a bit of material on duality from Chapter 8); the problems at the end of those chapters are good review material.
I expect to include five problems in each homework assignment. Homework averages will be based on the highest $c\cdot k$ homework scores, where $c$ is your number of credits and $k$ is the number of homework assignments. So on average, 3-credit students should submit solutions for at least three problems in each assignment, and 4-credit students should submit at least four problems in each assignment.
This class is an introduction to the design, analysis, and applications of algorithms for fundamental problems where the input are naturally interepreted as geometric objects. Specific problems we may consider include convex hulls, Voronoi diagrams, line segment intersection, polygon triangulation, geometric range searching, low-dimensional linear programming, geometric shortest paths, and visibility. Computational geometry has immediate applications in many other research areas, including computer graphics, mesh generation, geographic information systems, VLSI design, and robotics. While we may briefly consider these applications, the class will primarily focus on theoretical results and techniques.
In short, this is an algorithms class, with lots of pretty pictures! Lectures, homeworks, and exams will assume a solid background in algorithms, at least at the level of CS 374.
For more information, please see the course syllabus.
