I just love those recitation sessions (not just for this course, almost all EECS courses have them). They fill in more concrete examples and/or mathematical details to the original lecture. Well done MIT.
i can't agree more. Sometimes I can't learn in the lectures but i can always learn in the recitations. Because it's gives you solid interaction, not observation
Crazy to think that I was flipping pizzas at Little Caesars and taking college algebra in fall 2011, and here I am learning about algorithm complexity 9 years later when this was recorded way back then. Life takes us on a weird journey.
@25:00 A much simpler solution is the fact that (n n/2) is picking half the elements out of N elements ... so 2^N must be an upper bound to that, hence O(log(2^n)) = O(nlog(2)) = O(n)
When it comes to (n n-2), 2^N is an upper bound for sure, but there is a tighter upper bound. I don't think this way is great enough in all (n i) case.
When he is asking everyone whether following I really want to anwser I am. This lesson really has magic can let me keep attention on it, compare with my university.
is there a channel for us to improve the subtitles? I've noticed a couple of mistakes, for example at 39:32 , its supposed be T(n/2^i) instead of T(n/2^n).
+Roy lee You can send an email with subtitle correction(s) via the Contact Us form at ocw.mit.edu/jsp/feedback.jsp?Referer=. Depending on how much you want to do, the subtitle files (.srt) are available on our site at ocw.mit.edu/6-006F11. We welcome corrections to them. :)
DivinityStripes he said that we would look at complexity forest because of it isn't faster then who cares if it works or not. If out works then we will check if it is correct.
at 53:30, TA said M in the original equation will be replaced by lg(m) if 1-D peak is used instead. But I think not only that M is changed, the M in the recurrence (i.e. the M in T(N/2,M)) and the base case are also changed to lg(M) as well. Am I correct?
How many hours does MIT EECS meet their students in these recitation sessions per week? Is it always 1 hour lecture, 1 hour recitation? Do they have a lab session in this class?
Lectures: 2 sessions / week, 1 hour / session Recitations: 2 sessions / week, 1 hour / session See ocw.mit.edu/6-006F11 for more info. Best wishes on your studies!
I am surprised that the person who transcribed this lecture could not make out that Victor is saying Srini, who happens to be the course professor, but instead transcribes as [INAUDIBLE].
Can the Big Theta of a function have the same upper bound and lower bound(same constant factor)? For example: the function n^2 = Big-Theta(n^2) could mean n^2
I guess you could but that wont be useful because it represents a very specific case of g(n) = theta(g(n)). This is true but whats the point of the asymptotic notation if it is not making your life simpler.
Is the algorithm being applied correctly, or described correctly, or am I not getting it? Start in middle, look at neighbors, if local peak halt, else recurse T(n/2), is what he wrote. Recurse T(n/2) means to me, start in the middle of one of the halves, and I guess it doesn't matter which one, and check its neighbors, if local peak halt, else recurse by starting in the middle, n/4. What I'm seeing him do follows that up to the recurse T(n/2). He doesn't start in the middle of one of the halves, he starts at the beginning, i.e., the larger neighbor of n/2. It makes more sense to do it that way but it's not the way he wrote out the algorithm, is it?
How come he can get rid of the base at 23:31? I thought he did it at 22:11 because when n gets larger, log(ln(5)) is just a trivial number that doesn't have much impact on the result. But at 23:11 it affects the calculation itself before we make that assumption about the scalability Couldnt you do the same strategy as the earlier problem without getting rid of it? I end up with: log(100 log(n)) / log(ln(5))
It's not about whether it has an impact or not, log(ln(5)) is a constant value that does not affect the upper or lower bounds. Hence, we can eliminate it from our final solution. What you've suspect to be the reason log(ln(5)) was dropped in the first example is actually true for any function that contains n. For example, look at 31:09 - we reject log(n)/2 because it exponentially smaller than 2^n. In this case, the reasoning that log(n)/2 is just a trivial number that doesn't have much impact on the result as n increases is correct. Hope this helps!
the problem of log( ( n n/2 ) ) would be much simpler if you wouldn't use approximation formula. Just open the factorials and check the highest power of n.
The professor is wrong at the 13:00 mark. It's not a big deal but it's still theta of x^1.5 as x^1.5 is clearly also a lower bound to the equation: (1+sin(x))x^1.5 + x^1.4
No he is correct because when sinx becomes -1, the x^1.5 term disappears and we have only the x^1.4 term remaining. x^1.5 cannot be the lower bound as it's greater than x^1.4 in this case.
+Ahmad Ayyash (Ash) it's because in log-arithmetics, log(n^2) = 2 log(n), you can bring down that exponential as a multiply, and since its a constant, hence it's non-significant and neglect-able.
question is to find a peak, so its ok to have multiple peaks because we are only searching for a peak. watch 6.006 ist lecture then come to this video you will understand
It looks like he is writing x^(1.4) but it sounds like he says "x to the one fourth". Maybe I'm not seeing or hearing him correctly? 11:25 Also he switches between N and n as if they are the same... Sloppy.
I suggest you to go look for calculus 1 and if you have time go for calculus 2. There are some expression that you can find the answer of the question.
Find maximum element in just one column = M The (maximum) number of column that you need to check = log N Total = for the (log N) number of columns, you check all M elements on each column = M * log N
It's a long time past, but answering for future reference: log_a(b) = log(b)/log(a) so a constant base becomes just a constant multiplicative factor that you can disregard.
Recitation is a complement to lecture. Whereas lectures are filled with far too many students and far too much material to have ample opportunity for individualized engagement and specific questions, recitation holds smaller numbers of students and is aimed to address anything covered during lecture or individualized studying that is unclear. Recitation is a safe space in which asking questions for cla
this guy is so cool & his writing is OK i have seen people with more miserable handwriting & he sits exactly at back of me in exams......n great thing is i have to cheat from his answer sheet.....in chemistry, electrical, physics exams :p
People who say that monetary profit is just a corrupting factor should think about what he said here. Why does google care about giving you a fast service? Because in a capitalist system, you have a right to not help them make money. Without a capitalist system of accountability to customers, they'd be okay with making you wait for results, just like the DMV (who should be more efficient according to socialist theory), because there's no penalty to them for doing so. >Just go full Soviet and torture them if they don't get 200 milliseconds! And now you understand why putting leftists in charge of humans rights is like putting child molesters in charge of CPS.
I am calm, I am just telling you as a mathematician and computer scientist (both) I found his comments to be very inappropriate to a course in this subject. I would appreciate you not inferring false statements about my feelings. As somebody who has taught this subject numerous times (in analysis) and at the university level myself as an instructor that is not the way to present oneself with this subject. The point is to emphasize the importance of mathematics in computation as it is required
He's making the distinction between math and computer science conventions using a little bit of humor. Honestly the fact that you aren't used to this makes it seem like you are in fact not both a mathematician and computer scientist.
I find this TAs jokes to be incredibly arrogant. To segregate your students between the "maths" students and the "CS" students is ridiculous. There is no line to draw when they are one in the same.
