CS 577: Introduction to Algorithms

Hi everyone, 

There are still a few slots open for peer mentoring, and I wanted to make sure everyone who wants some extra mentoring has the opportunity for it. We heavily encourage those who haven't seen us before to sign up.

We've added more time slots on Sunday and Monday, and we're introducing drop-in office hours on Tuesday. From 10AM-4PM, at least one of us will be in CS 4384 to answer brief questions you have. This time is meant for BRIEF QUESTIONS ONLY (~15 min each).

Good luck studying!

-- CS 577 Peer Mentors

If you haven't filled out course evals yet, please do so by tonight. It only takes 5-10 mins of your time. Your feedback is extremely important to us, especially as this course scales up in size and transitions from a 3 credit to a 4 credit course.

We are still at a roughly 50% response rate. I'm hoping we can achieve a 70-80% response rate.

Thanks, everyone!

In Homework 8, problem 4 was graded by Andrew Brockmann and problem 5 was graded by Amanda.

Problem 4 seems to have been a difficult one - the issues that arose were many and varied. Those who did part (c) generally did so correctly (or very close to it), but numerous submissions left (c) blank, and problems in parts (a) and (b) were quite common.

First, here are a couple general pieces of advice for homework:

(a) Many p4 submissions regressed to writing almost pure code. Don't do this. It is not at all easy to understand. Experience leads me to think that it should be annoying to write, too.

(b) If you're given a target runtime and your algorithm does even better, carefully examine your work. Sometimes it is possible to beat the target runtimes, usually with more complicated algorithms. But if you come up with a very fast and very simple algorithm (e.g., an $O(1)$ algorithm for part (a)), it is quite likely that something is wrong.

Here are explanations of the problems corresponding to the numbers I sometimes wrote while grading:

#1: "Trivial" or brute force algorithms. Each part of this problem really was nontrivial.

(i) Simply checking every array element to determine whether it's between $M[i^{\prime },j^{\prime }]$ and $M[i,j]$ is not good enough for part (a). The array has $n^2$ elements, so this is not an $O(n)$ algorithm. Brute force algorithms like this did not receive points.

(ii) A common problem in (a) was the use of an incorrect shortcut. Numerous submissions made reference to a "box" with $M[i^{\prime },j^{\prime }]$ and $M[i,j]$ as two of the corners, assumed that the array elements between these values are just those within the box, and performed some $O(1)$ index arithmetic to count the elements of the box. See the attached counterexample - the values 20 and 51, for instance, are between 0 and 80, but are not within the box defined by 0 and 80.

(iii) The most common "trivial" algorithm for (b) was to take all of the elements counted in (a), put them in a new array, and uniformly select an element from that array. This isn't $O(n)$ because there may be more than $O(n)$ elements between $M[i^{\prime },j^{\prime }]$ and $M[i,j]$. For example, if there are $n^2/2$ values in between, the construction of that array takes time $n^2/2=\mathrm{\Omega }(n^2)$. The crux of part (b) was coming up with a way to simulate such an array without actually creating it.

(iv) Overly simplistic algorithms for (c) were uncommon. They tended to try one of two things: finding a median of medians (taking the median of each column/row, then returning the median of those medians), or taking the median of the diagonal entries. The attached counterexample foils both of these attempts. Note that 51 is the median of that array.

#2: Non-uniform algorithms for (b). (Alternately, neglecting to demonstrate that one's algorithm for (b) is uniform.) For a submission for (b) to demonstrate uniformity, it is necessary that all array elements between $M[i^{\prime },j^{\prime }]$ and $M[i,j]$ are selected with equal probability.

(i) The most common incorrect approach was to uniformly select a row/column, and then uniformly select one of the values of that row/column that is between $M[i^{\prime },j^{\prime }]$ and $M[i,j]$. This fails if the rows/columns have different numbers of values in range. Each of the values will have a nonzero probability of being chosen, but those probabilities will not, in general, be equal.

(ii) Another incorrect approach stemmed from misconceptions about the "box" mentioned in issue #1(b). Uniformly selecting a value from the box is not sufficient - some values within range may be outside of the box, and this approach would never select any of those values.

p4_counterexample.pdf

Q4 was graded by Amanda and Q5 was graded by Gautam, Please direct any grading related questions to the T.A. who graded the problem.  

The most common error in Q5 involved an incorrect approach to decide the order in which the child subtrees of a given node should be visited. 

The two most common incorrect strategies involved either visiting the children in decreasing order of $\mathrm{\#}worms$ or decreasing order of

$\mathrm{\#}worms/\mathrm{\#}leaves$. Both these strategies fail on this example. 

Some submissions failed to notice that the order in which the subtrees are visited matters.

And a few others  used an incorrect recurrence relation. 

Effective next week, I will be moving my Wednesday 3:30-4:30 office hours to 12-1 on Fridays, due to the change in homework due date. This change is reflected on the course calendar. 

I will not be having office hours this Friday 4/21. 

The grading for HW 5 is finished. The graders this time were:

p4: Tianyu

p5: Andrew Brockmann

Following is some explanation on the common types of errors/issues in problem 5 submissions. There were, broadly speaking, two major classes of issues.

Issue #1: Algorithm design is incomplete or incorrect.

(i) Numerous submissions tried using a graph consisting of the locations on the race track, with edges drawn between nodes when a car can move from one node to the other in one time step. This is perhaps the most natural thing to try, but this approach faces problems because we can take different paths to arrive at the same node with different velocities, and the set of nodes we can immediately travel to depends on our current velocity. Consequently, no single graph that we can create will suffice - either it will not allow for all possible paths through the race track, or it will permit some invalid paths.

(ii) Other submissions recognized that tracking our current velocity was necessary but fell into a more subtle pitfall. Specifically, we may get incorrect output if we mark a position as "visited" the first time we reach it and then disregard all other paths through that position. (The correct approach here is to mark a state, position + velocity, as visited.) Oddly enough, reaching each position as fast as possible will not necessarily bring us to the finish line as fast as possible. Let each state be represented as a 5-tuple $(x,y,v_x,v_y,t)$, where $(x,y)$ is our position, $(v_x,v_y)$ is our velocity, and $t$ is the time that has passed so far. Suppose we have two states $(x,y,v_x,v_y,t)$ and $(x,y,v_x^{\prime },v_y^{\prime },t^{\prime })$, with $t^{\prime }>t$. The optimal path to the finish line through $(x,y)$ will not necessarily be via the first state; for example, the velocity $(v_x,v_y)$ may guarantee that we veer off the race track in the next time step. We may therefore be better off passing through position $(x,y)$ with velocity $(v_x^{\prime },v_y^{\prime })$, even though it took us more time to reach $(x,y)$ this way.

(iii) Other people crafted a recursive algorithm to be implemented with memoization. The issue here is that a memoization order is needed, and in the most general case (where no single race track is specified), creating a valid memoization order is not simple. Memoization works nicely in many DP problems because each entry in a DP table can be computed by reference to table entries that have already been filled in. That is, we can specify an order in which to fill in a DP table (row by row, diagonal by diagonal, etc.) such that each value only depends on values which have already been filled in. Generally, our race track might be complicated (e.g., it might zigzag through the grid), so a valid memoization order is not easy to produce. Without memoization, these algorithms will not be efficient.

Issue #2: Runtime analysis is incomplete.

Note that the algorithmic runtime should always be specified in terms of the input size. In this case, the input is the $n\times n$ grid with size specified by its dimension $n$. Runtimes should therefore be in terms of $n$, the dimension of the grid.

(i) The standard approach to this problem was to construct a graph and then run a shortest path algorithm on it - usually BFS, though Dijkstra was sometimes used too. For algorithms that used BFS, for example, it was incorrect to simply say that the algorithm was $O(m+n)$ since that's the runtime of BFS; in this problem, $n$ is the grid dimension, which should not be the number of nodes or edges in the graph. Instead, the expectation here (for BFS, at least) was to note that the runtime of BFS is $O(|V|+|E|)$, and then produce bounds on $|V|$ and $|E|$ in terms of $n$. Many people used the bounds $1\le x,y\le n$ and $-n<v_x,v_y<n$, so that there are $n$ values each for $x$ and $y$ and about $2n$ values each for $v_x$ and $v_y$, and hence $|V|\approx n\cdot n\cdot 2n\cdot 2n=O(n^4)$. Submissions which simply cited the runtime of BFS or Dijkstra did not receive many points since they skipped most of the work that was necessary in this runtime analysis.

(ii) Other submissions fell short of a complete runtime analysis by setting bounds for $|V|$ but not for $|E|$. If the runtime of your shortest path algorithm of choice depended on $|V|$ and $|E|$, then it was necessary to find bounds for both. (Note that some algorithms were crafted in ways such that the shortest path runtime was solely dependent on $|V|$; for these algorithms, producing a bound for just $|V|$ was fine.) In particular, if you found that $|V|=O(n^4)$, then you still cannot say that the BFS runtime $O(|V|+|E|)$ is $O(n^4)$ unless you show that $|E|=O(n^4)$ too. Perhaps the easiest way to obtain the $|E|$ bound was to note that each node has at most 9 edges (corresponding to the 9 possible velocity adjustments), so that $|E|\le 9|V|=O(|V|)=O(n^4)$. In this particular case, the number of edges was linear in the number of nodes. In general simple graphs, however, it is possible to have $|E|\sim |V{|}^2$.

The midterm exam will be held on Thursday, March 16, 7:15-9:15 PM in Agriculture Hall room 125. 

Please make sure to get to the room *15 minutes before* the start of the exam. The exam will begin and end promptly. 

You are allowed to bring a cheat-sheet to the exam -- one letter-sized sheet, front and back. No other material, books or notes, is allowed.