Final Exam
December 7th, 2007The much awaited final is here. There are 6 problems, and all must be solved. Each problem is worth 20 points, and I’ll normalize to 100 later on.
The final is due Tuesday Dec 11 @ 5pm. You may submit the solution electronically or physically (if the latter, slide it under my door). As usual, this post will be the clearing house for question, and you can always email me directly.
The LaTeX for the final is here.
Good luck !
Entries
December 7th, 2007 at 5:17 pm
Do you want what we hand in to be the same format as the Midterm (i.e., one page per problem)?
December 7th, 2007 at 5:50 pm
Problem 4: Is a sequence of numbers consisting of just one number considered oscillating?
For example, is the following true?:
{1} is oscillating
{2, 1} is oscillating
{1, 2} is not oscillating
December 7th, 2007 at 6:24 pm
L. Vegas: the format is not important. It’s just cleaner for me to lay them out that way
A. Star: your labelling of sequences as oscillating or not is correct.
December 7th, 2007 at 9:31 pm
Hi,
Question 2: When Monte rolls a die the first time and jumps based on the outcome of the die … This is the normal 6 faced die and when the outcome is say 4, he jumps 4 miles … Is this right?
December 7th, 2007 at 10:05 pm
ah. I changed things and forgot that. No, there’s no die. he merely evaluates a random variable whose expectation is g(x). I’ll email a clarification
December 8th, 2007 at 1:58 am
I am still confused with problem 2… By monotonically increasing .do you mean that if x1 > x2 then g(x1) > g(x2)? Also, is a random value generated for the very first jump also? Given the fact that the first jump can be atmost half the total destination, can we assume that the generated random numbers are always within acceptable range after every jump?
December 8th, 2007 at 2:02 am
Question 1(a) : Do we assume no variable is flipped more than once?
December 8th, 2007 at 10:57 am
By monotonically increasing .do you mean that if x1 > x2 then g(x1) > g(x2)?
Yes. Maybe it’s easiest to think about what happens in the “deterministic” case. Each rabbit starts at N and “tosses a coin” whose value is N/2. It then moves to N-N/2 = N/2, “tosses a coin” whose value is N/4, and then moves to N/2-N/4 = N/4. and so on
The same thing happens in the randomized case. You can also assume that if at some point you are at position x, and g(x) > x, then in the next move you’re done, because you’ve reached Carrotopia. So assuming that the g(x) values are “in range” is a worst-case assumption, since you’ll always do at least as well, and so it’s safe to assume that the g(x) values are always in range.
December 8th, 2007 at 12:29 pm
For problem 3, can we use any algorithm as long as we can achieve in poly-time?
December 8th, 2007 at 12:50 pm
Sure. As usual, closer to the ideal garners more marks. BUt shouldn’t you be out jumping towards Carrotopia ?
December 8th, 2007 at 1:41 pm
On problem 3 can we assume that the weights and profits are rational numbers?
Better yet can we assume division of the weights and profits to be a polynomial time operation?
December 8th, 2007 at 1:56 pm
Two things:
Problem 4,
consider sequence A = {3, 10, 1, 2} and a subsequence in A, a = {10, 1, 2},
a is the only oscillating sequence and as such is the longest oscillating subsequence in A, correct? or is it that 3 in A has index 1 and 10 in A has index 2 and so on in A and so in a 10 still has index 2? if it is the second case the largest oscillating subsequence in A is zero.
Problem 2,
I am not understanding the discussion of ‘range’ above, is it really meant that g(x1) (this is when Monte C. is at N) can never return a value greater than N/2? If this is the case than I don’t believe that Monte C. will ever get to where he desires.
I am getting confused by all this monotonically increasing (for I keep thinking it should be decreasing), is this merely a fancy way of saying the rabbits never lose hope, that they never return home that they always move toward the carrots?
I will have another question, about 6, when I can think of how to form a question.
December 8th, 2007 at 2:31 pm
Lame Foot: yes, you can assume that. just state it
confused: Problem 4: No, the first case is correct. In other words, once you construct a subsequence, you “renumber” so that the first element has index 1 etc. In your example, 10 has index 1, 1 has index 2, and 2 has index 3 in a. in A, 10 has index 2, 1 has index 3, and 2 has index 4.
Problem 2: Don’t worry about the monotonically increasing for now if it’s bothering you (you’ll need to use the fact that if x1 > x2, then g(x1) > g(x2) later on though). Intuitively, what it’s saying is that in the beginning, the rabbits can jump far (because g(x) is large), and the closer they get to 0, the smaller the jumps get.
Remember that the rabbits *always* have hope since the value of the random variable is always positive (which means they always go in the right direction).
As for the range of values, don’t worry if you’re not following the above discussion. The main point is this: The rabbit jumps by a certain amount, and clearly unless the amount it jumps is “reasonably large”, the rabbit will never get to the origin in a reasonable time. This is why we say that the expected value of the random variable is g(x). g(x) essentially says that things are reasonable.
does that help ?
December 8th, 2007 at 2:33 pm
Sarvani: as for question 1, we don’t assume anything; the random procedure does independent coin tossing at each step.
December 8th, 2007 at 3:33 pm
Yes, very,
Just to clarify, you said above about the rabbits:
in the “deterministic” case. Each rabbit starts at N and “tosses a coin” whose value is N/2
why would the rabbit toss a coin, if he knows it will jump by N/2?
I think you mean that the coin always comes up true and only if the coin came up false would the rabbit not jump (procrastinate)
or am I still missing something?
December 8th, 2007 at 3:52 pm
yes! got it!
December 8th, 2007 at 3:54 pm
no no. I think I said too much. When I talked about deterministic rabbits, i was referring to what the *other* rabbits were doing, where you could “pretend” that they tossed a coin that always gave the same value. If you understand basically what needs to be done, ignore my comment about deterministic rabbits.
December 9th, 2007 at 12:00 am
Question 5: I did not get how can we multiply two sqrt(n) bit integers in constant time … Will we not need atleast O(n^log3/2) time according to the formula to muliply integers?
December 9th, 2007 at 12:03 am
What I’m saying is, ASSUME that you can do this. how does this then change the running time ?
December 9th, 2007 at 3:22 pm
6.2. If we look at the bipartite graph k_{3,3}, there 9 paths from s to t that have one edge between L and R. What does it mean to “augment by all such paths”?
December 9th, 2007 at 3:31 pm
Augment by all *edge-disjoint* paths (of which there are three)
December 9th, 2007 at 5:23 pm
6.1: “Prove that this implies that this graph consists of cycles and paths, . . .”
If we say M = {a = v1->v2}
And M’ = {b = v3->v4, c = v5->v6}
The graph induced by M \Deta M’ has three edges, which don’t form a cycle.
Is that not what you mean by “this graph”?
December 9th, 2007 at 7:35 pm
“Augment by all *edge-disjoint* paths (of which there are three)”
Which three?
Or is question 6.2
“Given any set S of edge-disjoint paths from s to t with one edge going from L to R such that |S| is maximized, show that the matching we obtain by augmenting all paths in S is a 1/2-approximation”?
So, for example, k_{3}{1} has 3 paths of length 1 (not including edges touching s or t). However, the maximal set of edge disjoint paths from s to t is 1 (since there’s only one vertex in R, thus only one edge to t, which all paths must use). Is that the right thinking? Or is there some way of getting “all edge-disjoint paths” given a graph and I’m not seeing?
December 9th, 2007 at 7:56 pm
L’ost: the graph induced has three disjoint edges (v1->v2, v3->v4, and v5->v6). these are three paths, are they not ? each of length 1 ?
M. Flow: Replace “maximized” by “maximal”, and then your restatement of 6.2 is correct. maximal means that you can’t add another edge without destroying the disjointness property. maximum is the largest possible (necessarily maximal) set. maximal suffices for this case.
December 9th, 2007 at 9:43 pm
Question 2: I am not really sure what this questionis asking. Is it asking for expected number of jumps Monte C will take to reach to Carrotopia?
December 9th, 2007 at 10:02 pm
Halo-99: that is correct.
December 9th, 2007 at 11:01 pm
6.2: What does it mean to have a path that is a “vertex-disjoint augmenting path with respect to M”? I get the vertex-disjoint augmenting path (I hope), but “with respect to M”?
December 9th, 2007 at 11:05 pm
Remember that when we define an “augmenting path” in this bipartite graph, it is defined with respect to a matching, because the augmenting path must alternate between edges not in M and edges in M. So you can’t talk about an augmenting path without talking about the matching it is an augmenting path with respect to
December 10th, 2007 at 10:24 am
For problem 4: By efficient algorithm do you mean a polynomial time algorithm?
December 10th, 2007 at 10:26 am
Sarvani: yes, efficient == polynomial time :). As always, the more efficient, the more points.
December 10th, 2007 at 5:39 pm
Question 6.1 asks to show that the graph induced by the symmetric difference of M and M’ consists of cycles and paths. I’m confused because doesn’t every graph consist of cycles and paths? Plus, the induced graph may not have any edges, if M and M’ contained all the same edges to begin with. Or, are we assuming M and M’ do not have all the same edges?
December 10th, 2007 at 6:11 pm
the symmetric difference consists of a collection of cycles and paths that are vertex disjoint (i.e eac of the paths is disjoint from each of the cycles). If you take (say) a tree, this is not true in general, since a node of degree three might decompose the tree into paths that overlap.
If the graph is empty, then it contains the empty cycle and/or the empty path, so that’s consistent.
December 10th, 2007 at 8:30 pm
When you say vertex disjoint augmenting paths : do you mean that an augmenting path has no vertex repeated or that two augmenting paths do not have a common vertex?
December 10th, 2007 at 8:44 pm
well an augmenting path is a *path* so by defn there are no repeated vertices. I mean that two augmenting paths do not share common vertices
December 10th, 2007 at 8:53 pm
Not clear about the matching with respect to M (I did read the previous blog). If an augmenting path alternates between edges in M and M’, then we cannot call it an augmenting path wrt to M or M’?. An augmenting path wrt M must hence have edge only from M?
December 10th, 2007 at 10:51 pm
remember, the first edge is NOT from the matching. that breaks the apparent symmetry between M and M’
December 10th, 2007 at 11:18 pm
6.4 : Show that there are at most sqrt(n) augmenting paths remaining … Can we assume these augmenting paths are vertex disjoint too?
December 10th, 2007 at 11:19 pm
You don’t really have to. Think about what 6.1 is telling you.
December 11th, 2007 at 3:07 am
Should we obtain a closed form for Carattopia problem, would we receive no carrots(points)? Does a closed form strictly not exist?
December 11th, 2007 at 9:18 am
no no. there isn’t a compact closed form as far as I know. if you find one, more power to you. I only mentioned the lack of a closed form so people don’t go crazy trying to find one.
Here’s an example of an answer that isn’t a closed form, but it sort of what i’m talking about:
E[T] = \sum_0^N g(x)^3
It’s not a closed form soln because of the summation, but it only involves N and g(x)
December 11th, 2007 at 12:38 pm
Hello Prof, I am still lost in Vegas(prob 1)! Could you make at least one question optional?
December 11th, 2007 at 2:09 pm
nope, sorry.