Midterm
October 17th, 2007The midterm can be found here. Due date is Oct 19 (friday) @ 5pm. LaTeX src (minus the figures: you’ll have to comment those parts out) is here.
Additional notes:
- You may NOT consult your fellow classmates or others. The books are your only friends.
- You may post questions about the midterm as comments on this post. I will be monitoring it frequently.
Entries
October 17th, 2007 at 3:08 pm
Question 6: It looks to me that there is a typo in line 3. It says that if t[i+j] is 0 then p[j] can not be zero which contradicts with equation in line 2.
October 17th, 2007 at 3:09 pm
Question 6: It looks to me that there is a typo in line 3. It says that if t[i+j] is 0 then p[j] ca not be zero which contradicts with equation in line 2.
October 17th, 2007 at 3:11 pm
Question 6: It looks to me that there is a typo in line 3. It says that if t[i+j] is 0 then p[j] ca not be zero which contradicts with equation in line 2.
October 17th, 2007 at 3:21 pm
Ah yes, there is a typo. replace that by ‘p[j] MUST be zero’. I’ll change the src files. thanks
October 17th, 2007 at 5:22 pm
Question 1.2: Since its important to get the quantifiers right, could you please define what T(n,m) = O(f(n,m)) means? I am a bit confused comparing the bounds, when the running time of an algorithm has two dependent variables.
October 17th, 2007 at 5:53 pm
Is there a link to the Homework Solutions (I am looking for Homework 1 solution in particular)?
October 17th, 2007 at 5:54 pm
In problem 2: Do we assume that “knowing person well” is symmetric?
October 17th, 2007 at 8:00 pm
Anon 1: For a definition of O() notation for multiple variables, you can see this wikipedia link for example. In short, the definition is what you’d expect it to be.
Anon 2: There is no link to the homework solutions, because I don’t place them online. Email me directly about this, or you can drop by my office tomorrow and pick up one.
Sarwani: Yes, you can assume that “knowing person well” is symmetric.
October 17th, 2007 at 11:50 pm
Problem 2.2 - second bullet:
“Anyone holding the camera can take a picture of someone they know very well, and then pass the camera to that person.”
Do they /have/ to pass the camera after taking only one picture? Or can, for example, I get the camera, take a picture of three people, and pass the camera to one of them?
October 18th, 2007 at 12:11 am
No, you take the picture of “someone” you know very well, and then pass it on to them. i.e one person only.
October 18th, 2007 at 1:14 am
In question 1.1 it is given that T(n,0) = T(n, n) = 1. Is this right? Because this means that n is always greater than m and if n = m then the answer is just 1 … Also, T(n, n) = T(n-1, n) + T(n-1, n-1) will definitely be greater than 1 …
October 18th, 2007 at 1:14 am
Sorry - it is 1.2
October 18th, 2007 at 1:48 am
I should have clarified that T(i,j) for i
October 18th, 2007 at 1:49 am
I should have clarified that T(i,j) for i < j is zero. Also, T(n,n) is a boundary case, which you hit as you start calculating T(n-1, m), T(n-2, m) and so on. So it doesn’t make sense to apply the recurrence to it really. Or, if you prefer, T(n,n) = T(n-1,n) +T(n-1,n-1) = T(n-1,n-1) = T(n-2,n-2) all the way down to T(1,1) = 1
October 18th, 2007 at 10:25 am
Just to be sure on how you want it submitted….
You want (at least) two pages per problem, the first of which is just the problem, right?
October 18th, 2007 at 11:51 am
Correct. and don’t forget the cover sheet.
October 18th, 2007 at 1:32 pm
Q3) is it okay to have summation notation in our answer? or do we need to expand it out should we come across such a thing?
October 18th, 2007 at 1:45 pm
unless there’s a really good reason (like there *is* no closed form), I expect summations to be collapsed.