Finals Have Been Marked

Hi,

The finals have been marked and the grades should be posted soon. You can take a look at your marked final in Gary's office, GHC 8109.

Thanks to everybody for coming to the class and putting up with your Newbie TA. This term has been a great learning experience for me. Hopefully I can avoid repeating the many mistakes that I made in my next attempt at TAing:-).

Richard,

Solutions to Practice Questions

Hi,

The solutions to the practice problems have been posted on the course website. I couldn't find solutions to the past finals, but can go over some of them in person tomorrow afternoon.

Richard,

Location for Review

Hi,

The review session will take place in GHC 4405 at 8pm today (May 4). Hope to see you there.

Richard,

Finals Review Session / Practice Problems

Hi,

The review session for the final exam will happen tomorrow (May 4) at 8pm in a room to be determined. Hopefully I'll make another post about its location soon.

Some practice exams/problems are posted on the course webpage, with solutions to come. We could go through some of the questions during the review session tomorrow, or other ones upon request. Please come with questions to ask as well :-).

Richard,

Changes to Homework 6 Scoring

Hi,

Due to my inability to add, 5 more points were added to questions 3 and 4 of homework 6 to make the total 100. Sorry about this.

Richard,

Hint for Problem 4

Here's a handy hint for problem 4 on the most recent problem set:

Suppose L_t and R_t are the partition your algorithm has selected at time t. Define some integer valued potential function f(L_t, R_t) such that f is always in some bounded range [o, R].

Show that:

1) If we ever have f(L_t, R_t) = R, then L_t, R_t is a triangle free partition

2) Pr[f(L_t+1,R_t+1) = f(L_t, R_t) + 1 ] = Pr[f(L_t+1,R_t+1) = f(L_t, R_t) - 1 ]

Then all you have to do is analyze the evolution of the potential function: and this is just a random walk on a line graph of length R.

Corrections to Homework 5

Hi,

Here are two corrections to homework 5 question 2, sorry for overlooking these.

part 2 (thanks to Julian for pointing this out): the algorithm given needs to first pick a random middle element before partitioning to guarantee random sequences. The algorithm has been modified.

fact (thanks to Henry for pointing this out): the right side of the bound ($S \leq (1 -1/e ) n + \epsilon n$ ) is erroneous and has been removed.

Richard,

Office Hours

Hi class,

I'll be out of town for my office hours tomorrow (Monday). I'll be back Tuesday afternoon, in time for my regularly scheduled office hours on Wednesday. If you want to meet at some other time, feel free to send me an email, and I'll make sure to be available.

-- Aaron

I have several graded midterms. Let me know if you need them this weekend.

Gary Miller

Takehome Midterm and Assignment 4

Hi,

The take home midterm is available on the website and is due Monday before class. The scoring formula is mentioned once again on the first page.

Also, the due date of homework 4 is moved back to Wednesday.

Several people have asked about one complication resulting from question 2.1 on homework 4. The issue is about how to insert vertices in front of other vertices in the ordering and still be able to query whether one vertex comes before another in the ordering. There is a way to get around this issue by processing the entire graph again globally after building partial information. However, you can also use a data structure by Dietz and Sleator that supports both operations in O(1) worst case time. It can be found at http://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf if you are interested.

Richard,

Clarification on Hw4 Question 2.1

Several people have asked about whether "$v_i$ is connected to $v_j$, $v_k$" in the definition of deadend free ordering in question 2.1 means path connectivity. It should instead be "$v_i$ has edges to $v_j$, $v_k$". Also, note that there are no other assumptions on where $v_j$ and $v_k$ are in the ordering other than being before/after $v_i$.

Richard,

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,

Hints for Problem 2

Here are some hints for problem 2, for those of you who are stuck. Even though the solutions are all simple, for these problems its easy to think for awhile without getting anywhere. This should get you on the right track; feel free to email or visit office hours for further hints.

2a)
See if you can mentally divide the pizza into two sets in such a way that you can select every slice in one or the other of the sets, no matter what your opponent does. If you can do this, you are done, because one of the two sets has to have at least half of the pizza.

2b)
This problem doesn't depend on the specifics, like the exact size of the pepperonis. Think symmetry. Suppose we're playing on an annulus (a disk with a circle cut out of the middle). If I make the first move, what is some move you are guaranteed to be able to make? If you are the first player on a pizza, how can you guarantee that you will be the second player on an annulus?

For 2c:
It's a long standing open problem to actually come up with a winning strategy for the 1st player, so don't try to do that. Just prove one must exist. Suppose it were the case that the 2nd player had a winning strategy. What this means is that even if he were to tell you exactly what his strategy was, he could still win. Is this possible, or if he were to tell you his strategy in the chocolate bar game, could you use it to win yourself? An important property of this game is that many moves wipe out all sign of the previous history of the game in the current game state: for example, if I go first and select square (1,1), and you go second and select square (3,3), the state of the game is exactly the same as if you had gone first and selected square (3,3). The solution to this problem is a nice example of a nonconstructive proof.

Homework 1 Question 4

Thanks to several people who pointed this out during Aaron's office hours, what we thought was a minor detail on question 4 is a lot more complicated. The rearrangement of the 4 rank k subtrees causes changes to the parent pointers of their siblings, which are required to determine and fix violations. There exists a fairly complicated set of extra invariants on the violations that keeps this process at O(1) worst case, but that is beyond what is reasonable for this assignment. Sorry for this oversight.

As a result, your solutions may assume that there is an oracle which can support the rearrangement of rank-k subtrees and queries for parents in O(1) worst case time. You are also welcome to work towards the full solution for up to 20 bonus points.

HW0 solutions posted & HW1 modified

Hi,

Solutions to homework 0 have been posted on the course website. A typo in homework 1 question 4 has also been fixed.

Richard,

Office Hours Changed

Hi,

I've changed my office hours to Wednesday and Friday 3:00~4:30pm due to scheduling issues.

Richard,

Modified Office Hours

Hi class,

I will have to cancel my office hours this Monday (10:00 -- 11:00). Instead, I will have extended hours on Wednesday. In addition to my regular Wednesday office hours (also 10:00 -- 11:00), I'll be available to meet 12:30 -- 1:30.

Homework Zero Modified

The missing diagram was added to question 4 and part b) of it was removed. Question 5 was also modified to make it clear the domain of the function are the integers from 1 to n. Sorry about this.