Midterm 1 Graded

As requested, here are some stats: mean was 60.41 with stddev of 20.68. Median was 63.5 Max was 94 and min was 20. For the curious, we are also including the histogram here.

HW3 posted

You can find it here or on the website :-)

Friday office hours canceled

I have to cancel my 10am Friday office hours this week, due to conflicts with the CSD open house. If you have any questions about anything, feel free to email me instead.

Traveling Salesman in O(1)

As a quick distraction from your studying and my grading, there's actually an xkcd comic related to the last homework. For anyone who hasn't seen xkcd before, I highly recommend it.

Closest point

Suppose we're given a convex polygon $P$ and a point $q$ inside $P$, and we would like to find the closest point on the boundary of the polygon. Note that the distance from a point to a line is defined as the shortest distance from that point to the line.

If the polygon has $n$ vertices, it is easy to solve this problem in $O(n)$ time: compute the distance to every edge and find the minimum. In the review session today, we also wanted to show that this is optimal, but we ran out of time.

Now we will prove an $\Omega(n)$ lower bound. In particular, we will show that no algorithm which look at $\leq n/2$ queries can correctly find the closest point. Here's a proof sketch, based on an adversarial argument. The problem instance that we will use consists of a regular $n$-gon centered at the origin, and a query point $q = (0,0)$. After the algorithm finishes "looking" at $k \leq n/2$ points and produces an answer, there will still be points which the algorithm has not seen. We can therefore freely move these points, as long as we maintain convexity of the polygon: in particular, we will move some of these points so that the answer the algorithm gave was wrong (convince yourself that this can be done).

Question 4

There have been a couple questions about nasty algebraic calculations for question 4 of the homework. To make the calculations simpler, you're welcome to assume that $\log(n!) = n \log n$. This is not actually true, although it is true that $\log(n!) = \Theta(n \log n)$. Dealing with the extra constant seems to require much more annoying calculations, which can be done but are a pain to both figure out and to grade. We might take off a point if you do this, or give a little bit of extra credit to people who do the full calculations. Note that this is also a hint that you should probably be using factorials :-).

Practice Midterm I

In light of the review session on Friday, we are posting a practice midterm (PDF) for you to chew on. This is the exam from last year. We will go over these problems during the review session.