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.

HW2 Clarifications

A couple clarifications on Homework 2, Problem 2: first, we forgot to describe how the polygon P is specified. You can assume that you are given the vertices of the polygon in counterclockwise order. Also, when we say that a point is in the polygon we mean that it is actually inside the polygon, not just one of the vertices. So a viewpoint can be anywhere inside the polygon but has to be able to see every point in the polygon, not just the vertices.

Homework 1 graded

The average was 80.16, and the standard deviation was 14.7.

HW2 Posted

:)

HW1 Clarifications

Some last minute clarifications (compiled from popular questions we received recently). Check back regularly---we will continue to update this entry as we get more questions.

1. Problem 2. A couple of people pointed out that $G_i$, as stated in the hint for question 2b, can be empty, leading to horrible consequences. We were indeed sloppy about the definition of $G_i$. To be more precise, $G_i$ includes all elements of $D_i$ that were ``good'' at some point during $I_i$.
   
   As such, $G_i$ can never be empty, because at most $\alpha n$ elements were corrupted at the beginning of $I_i$ and $D_i$ contains $2\alpha n$ elements.
   
2. Just to be more clear about what assumptions we make about an $\alpha$-relaxed priority queue:
   
   
   
   • At any point in time only $\alpha n$ elements can be ``bad,'' where $n$ here is the number of elements in the priority queue at that moment.
     
   • When an element becomes ``bad,'' it records a time stamp of when it gets "corrupted."
     
   • Once an element becomes ``bad,'' it can never go back to normal. The priority queue may raise the value of an element more than once.
     
   • If an element is bad, its effective priority value is at least the value of its original priority. Note that priority value implies that an element with priority value $9$ is smaller than an element with value $10$, so if your queue has only $9$ and $10$, findMin will report a $9$.
     
   
   
3. Problem 4. The (evil) hint may have led to believe that you can construct $H$ in $O(n^{40})$ time. You should ignore it. Indeed, $H$ will have $O(n^{40})$ nodes, but it will take time $O(n^{80})$ to construct.