Homework 4 Question 3.1

There is a major mistake in question 3.1 on homework 4. I neglected to mention that the Pythagorean triples should be modulo n, that is:

$a^2+b^2 \equiv c^2 mod n$

The question should be doable now. Sorry about this.

Richard,

What you can bring to the exam

Hello class,

Here is what you are allowed to bring with you to use for the midterm on Monday:

+ (Annotated) course notes from the website

+ "The Design and Analysis of Algorithms" by Kozen, either in hard copy, or the printed chapters from the website.

Note: You cannot bring any other textbook.

You shouldn't bring other materials. Email us if you have specific questions.

Good luck!

Correction to problem 4.

Hi guys,

Problem 4 on the latest homework turns out to be a lot harder than we anticipated. (Thanks to Jiri and Min for pointing this out).

Here is a modification that makes it much more tractable. The separation penalty between vertices i and j will now depend on the distance between the labels of i and j. That is, label pairs (Bac, Foc) and (Foc, For) still result in penalty p_i,j, but the label pair (Bac,For) now results in penalty 2*p_i,j

Sorry about this. Grading will be lenient, and extra credit if you solve the original problem.

Homework 3 Question 2

Hi,

For homework 3 question 2, you may assume the graph is connected (aka. k>0 and the algorithm can always find some edge to contract). Also, part 5 of that question should have "at most $O(|V|^{2\alpha})$" instead of $\Omega(|V|^{2\alpha})$.

Sorry about this.

Richard

Office Hours

Hi Class,

I'll be out of town this coming week, so I won't be holding my regularly scheduled office hours. I should still be in frequent email contact though, so feel free to email questions about the homework if you're getting started early (It should be posted by later today).

I'll also hold extra office hours by appointment, in addition to my regular office hours next week, so if you can save up your questions until then, we can meet when it is convenient for you.

-- Aaron

Wednesday office hours moved

Hi Class,

I'll be out of town during my regularly scheduled Wednesday office hours, so I'll be holding office hours Thursday instead. (Same time, 10:00-11:00 am)

Modification to Homework 2 Question 4

Hi,

Question 4 of homework 2 has been changed to remove the degenerate case of multiple points having the same y-coordinate. You make assume the input points have been perturbed to avoid this.

Thanks to Henry DeYoung for pointing this out and sorry for not realizing this issue earlier.

Richard,