7 ms·

MIT 18.404J – Theory of Computation [video]

210 points by hidden-spyder 5y ago

truly 5y ago
The MIT lectures in general are very good quality and these ones in particular are a treasure trove. I would have loved access to something like this when I was a student. The MITOCW channel on Youtube has many more for those who are interested. A nice one is Design and Analysis of Algorithms.
- rg111 5y ago
  > A nice one is Design and Analysis of Algorithms. I searched and found multiple playlists on YouTube. Which one do you recommend? Or should it be the most recent one?
- DelightOne 5y ago
  Agreed. Do you know how is decided what courses are uploaded? Some courses like 6.046 only have recordings from 2015, but the field and the teaching probably advanced since then.
  - kyawzazaw 5y ago
    Depends on who is teaching I assume
  - PennRobotics 5y ago
    There are a few classes that are posted on Youtube or other sites (not via the official OCW channel) by instructors or students, like 6.004 and the Underactuated Robotics course. I would argue 6.046 doesn't necessarily represent the bleeding edge of algorithms. For the most advanced/modern, there's the graduate-level course, 6.854: https://courses.csail.mit.edu/6.854/21/course_materials.html https://courses.csail.mit.edu/6.854/21/course_materials.html (The 2021 videos are on Youtube, unlisted.)
    - DelightOne 5y ago
      Thanks for the recommendation and sharing! I appreciate lecturers and students sharing their knowledge wider, despite the difficulties involved. I hope that one day people won't have to search anymore, but easily being able to find cool resources like this.
  - truly 5y ago
    I don't know how they choose the lectures that they put online, but I can tell you that the effort needed to do so for a lecture is not at all trivial. From having researched things a bit myself, you need (at least) an in-class cameraperson to film the entire lecture and then you need post-processing. You need TV-grade equipment, for both audio and video. You need to ensure that the room is noise-free and has good lighting. The instructor ideally also needs to be aware of the recording (at the very least, they should at least not be standing between the camera and the board).
  - c-c-c-c-c 5y ago
    Every course needs to be captioned. Making a course ready for OCW takes alot of time and money when youd think its just a simple matter of uploading. See previous HN posts regarding this. https://news.ycombinator.com/item?id=9039798 https://news.ycombinator.com/item?id=9039798 And https://news.ycombinator.com/item?id=28583194 https://news.ycombinator.com/item?id=28583194
whymauri 5y ago
Wow! They got Sipser on OCW. This is widely considered to be one of the best classes around.
- jacobkg 5y ago
  Agreed. This was a fantastic class when I took it. The textbook written by Sipser is also extremely good and could stand alone. Fun fact: I got to have dinner with Sipser once and he told us that he had wagered an ounce of gold back in the 80s or 90s that P v NP would be resolved by the year 2000 (and thus had paid up)
  - shrimpx 5y ago
    That's amazing, I'd be really curious to know his reasons for leaning toward P vs NP been resolved.
- OJFord 5y ago
  I didn't go to MIT, but I'd highly recommend his Introduction to the Theory of Computation, it's only little, but a great one.
canjobear 5y ago
I sat in on this class in 2015. I still remember it clearly and it influenced how I think about a lot of things. Highly recommended.
abzug 5y ago
How much math do I need to follow this? And please, avoid terms like "high school math" since I'm not from US and this means nothing to me.
- hatersgonnahate 5y ago
  It’s more of a different kind of mindset you need, which is commonly seen from people with good math training. So much more tricky to say “how much” in this case. A graduate level of ability to abstract things and familiarity with abstract notations I assume?
- soganess 5y ago
  (Assuming this class is based on the Sipser book)Theory of comp needs: comfortably with algebraic manipulation, basic understanding of sets, the light touch of asymptotics usually learned in algos, strong comfort with boolean things, and the ability to grawk shorter proofs.
  - amilios 5y ago
    Sorry I just want to interject that it's "grok" not "grawk", that's an interesting spelling ahaha
    - soganess 5y ago
      Hilarious! Thanks for the heads up.
  - barrenko 5y ago
    Another Q, what is the difference between "computation" and calculation? Recently got into "Science of functional programming" (Sergei Winitzki) and "Program design by calculation" (J.N. Oliveira ), so was wondering if this would be a beneficial pre or post course.
    - soganess 5y ago
      The classic CS route for readiness to take ToC is programming+data structure (which if you are asking about taking ToC course, you probably have under your belt) Then algos which is usually the first time a student encounter asymptotic analysis (but like baby steps, its usually like only the first 3 weeks of the course and then the students use those skills during the course, like practice.) Some schools offer a discrete math course which I think helps everyone get up to speed on the math required, but, depending on your background can seems like a lot (I still remember it feeling like a lot to me, and I took it mannnnnny moons ago.) So I would call both of those "post" courses. To answer your question about C v C: As a first pass, it is fair to think of a computation as a calculation because they are the same thing many times! But I wouldn't, for example, consider controls (like a for loop) as a calculation but it is very much part of your model of computation (or if you are doing functional, a for-loop is not part of your model.) The two sentence elevator pitch for ToC is "You rigorously define and learn three increasing more powerful models of computation, then you find out that there are many more models, but they are not more powerful. So then you quantify and analyze what that condition means and how it effects our ability to compute actual hard problems."
FabHK 5y ago
:-) "Because non-determinism, the magic is that you always guess right. I wish that was true in real life. It would make exams a lot easier." [Lecture 2, 40:26 minutes: https://youtu.be/oNsscmUwjMU?t=2426 https://youtu.be/oNsscmUwjMU?t=2426 ]
- unobatbayar 5y ago
  If you study for the exam, wouldn't that make it deterministic?
  - remexre 5y ago
    A non-deterministic Turing machine has the ability to choose "correctly" from a finite set of options. (This corresponds to search, which gives a nice intuitive notion that search can't do better than exponential time without knowledge of the search space unless P=NP.)
deleted 5y ago
[deleted]
MisterBastahrd 5y ago
Seems to me that one of the advantages that students at elite universities have is elite instruction. Every Harvard or MIT class that I've ever audited online has been insanely easy to follow.
- truly 5y ago
  It is true to some extent, but not all instructors at some universities are that good. You are probably experiencing a two-sided selection bias, since they (1) wouldn't upload a bad video and (2) you wouldn't follow something you are not interested in. The main advantage of elite universities is the club effect. It makes such universities attractive for students, professors, and industry -- a nice circle.
  - deleted 5y ago
    [deleted]
  - mirker 5y ago
    Here’s another way to put it in terms of money: * Research universities make money from research and not teaching. * Admins create promotion schedules on research and not teaching. * Teaching is the “cherry on top”. Good research > good teaching. Of course, top institutions want it all, but it’s not a hard requirement. Also: The hardest courses to teach are the intro classes. Those require teaching excellence that doesn’t overlap with technical chops. It is very hard to explain programming when you take it for granted.
    - truly 5y ago
      Teaching intro classes is indeed difficult. I like how some universities have dedicated staff for this (who are paid to only teach and not do research).
danrocks 5y ago
I wonder if anybody has built a Computer Science curriculum from the OCW lectures in a playlist or some other form, so people could (in theory) follow the same path as an actual MIT grad from beginning to end. This dude did something similar but he was mostly trying to sell his productivity method and ebooks. https://www.scotthyoung.com/blog/2018/03/15/how-successful-was-mit-challenge/ https://www.scotthyoung.com/blog/2018/03/15/how-successful-w... I am more interested in increasing my theoretical knowledge and taking deep classes in algorithms, data structures, linear algebra, vector calculus, and other foundational CS stuff.
- truly 5y ago
  I think that the will power to go through 3 or 4 years worth of lectures on your own would be the main blocker. The main benefit to in-class learning is that your peers drive you, and you drive your peers. As a not-on-campus-learner, you should probably concentrate on smaller pieces that can be had individually. It would not hurt to have a small community to discuss the things that you learn (e.g., peers at work) to keep you motivated as well.
  - varelse 5y ago
    I was a curve breaker in college. These courses are fantastic for filling in the missing details left out to rehash the basics for everyone else and what I've forgotten decades later. Ironically, when people asked to study with me, they didn't get why studying for an hour each the 3-4 nights preceding an exam was crushing their cramming the single night before, so they would get frustrated with me and leave. Or I was doing spaced repetition before that was a thing. Which is to say motivated sorts can have trouble finding peers willing to stay focused.
    - metagame 5y ago
      Spaced repetition has been a thing for a really long time. Were you in college +/-1900? Depending on where the line is drawn for spaced repetition, it could be claimed to have been discovered initially from roughly 1885 to 1932.
ducktective 5y ago
Anyone knows a good course on formally proven methods of programming?
- YorkshireSeason 5y ago
  T. Nipkow, G. Klein, Concrete Semantics. http://concrete-semantics.org/ http://concrete-semantics.org/ B. C. Pierce et al, Software Foundations. https://softwarefoundations.cis.upenn.edu/ https://softwarefoundations.cis.upenn.edu/

210 points by hidden-spyder 5y ago

The MIT lectures in general are very good quality and these ones in particular are a treasure trove. I would have loved access to something like this when I was a student. The MITOCW channel on Youtube has many more for those who are interested. A nice one is Design and Analysis of Algorithms.

rg111 5y ago
> A nice one is Design and Analysis of Algorithms. I searched and found multiple playlists on YouTube. Which one do you recommend? Or should it be the most recent one?
DelightOne 5y ago
Agreed. Do you know how is decided what courses are uploaded? Some courses like 6.046 only have recordings from 2015, but the field and the teaching probably advanced since then.
- kyawzazaw 5y ago
  Depends on who is teaching I assume
- PennRobotics 5y ago
  There are a few classes that are posted on Youtube or other sites (not via the official OCW channel) by instructors or students, like 6.004 and the Underactuated Robotics course. I would argue 6.046 doesn't necessarily represent the bleeding edge of algorithms. For the most advanced/modern, there's the graduate-level course, 6.854: https://courses.csail.mit.edu/6.854/21/course_materials.html https://courses.csail.mit.edu/6.854/21/course_materials.html (The 2021 videos are on Youtube, unlisted.)
  - DelightOne 5y ago
    Thanks for the recommendation and sharing! I appreciate lecturers and students sharing their knowledge wider, despite the difficulties involved. I hope that one day people won't have to search anymore, but easily being able to find cool resources like this.
- truly 5y ago
  I don't know how they choose the lectures that they put online, but I can tell you that the effort needed to do so for a lecture is not at all trivial. From having researched things a bit myself, you need (at least) an in-class cameraperson to film the entire lecture and then you need post-processing. You need TV-grade equipment, for both audio and video. You need to ensure that the room is noise-free and has good lighting. The instructor ideally also needs to be aware of the recording (at the very least, they should at least not be standing between the camera and the board).
- c-c-c-c-c 5y ago
  Every course needs to be captioned. Making a course ready for OCW takes alot of time and money when youd think its just a simple matter of uploading. See previous HN posts regarding this. https://news.ycombinator.com/item?id=9039798 https://news.ycombinator.com/item?id=9039798 And https://news.ycombinator.com/item?id=28583194 https://news.ycombinator.com/item?id=28583194

whymauri 5y ago

Wow! They got Sipser on OCW. This is widely considered to be one of the best classes around.

jacobkg 5y ago
Agreed. This was a fantastic class when I took it. The textbook written by Sipser is also extremely good and could stand alone. Fun fact: I got to have dinner with Sipser once and he told us that he had wagered an ounce of gold back in the 80s or 90s that P v NP would be resolved by the year 2000 (and thus had paid up)
- shrimpx 5y ago
  That's amazing, I'd be really curious to know his reasons for leaning toward P vs NP been resolved.
OJFord 5y ago
I didn't go to MIT, but I'd highly recommend his Introduction to the Theory of Computation, it's only little, but a great one.

canjobear 5y ago

I sat in on this class in 2015. I still remember it clearly and it influenced how I think about a lot of things. Highly recommended.

abzug 5y ago

How much math do I need to follow this? And please, avoid terms like "high school math" since I'm not from US and this means nothing to me.

hatersgonnahate 5y ago
It’s more of a different kind of mindset you need, which is commonly seen from people with good math training. So much more tricky to say “how much” in this case. A graduate level of ability to abstract things and familiarity with abstract notations I assume?
soganess 5y ago
(Assuming this class is based on the Sipser book)Theory of comp needs: comfortably with algebraic manipulation, basic understanding of sets, the light touch of asymptotics usually learned in algos, strong comfort with boolean things, and the ability to grawk shorter proofs.
- amilios 5y ago
  Sorry I just want to interject that it's "grok" not "grawk", that's an interesting spelling ahaha
  - soganess 5y ago
    Hilarious! Thanks for the heads up.
- barrenko 5y ago
  Another Q, what is the difference between "computation" and calculation? Recently got into "Science of functional programming" (Sergei Winitzki) and "Program design by calculation" (J.N. Oliveira ), so was wondering if this would be a beneficial pre or post course.
  - soganess 5y ago
    The classic CS route for readiness to take ToC is programming+data structure (which if you are asking about taking ToC course, you probably have under your belt) Then algos which is usually the first time a student encounter asymptotic analysis (but like baby steps, its usually like only the first 3 weeks of the course and then the students use those skills during the course, like practice.) Some schools offer a discrete math course which I think helps everyone get up to speed on the math required, but, depending on your background can seems like a lot (I still remember it feeling like a lot to me, and I took it mannnnnny moons ago.) So I would call both of those "post" courses. To answer your question about C v C: As a first pass, it is fair to think of a computation as a calculation because they are the same thing many times! But I wouldn't, for example, consider controls (like a for loop) as a calculation but it is very much part of your model of computation (or if you are doing functional, a for-loop is not part of your model.) The two sentence elevator pitch for ToC is "You rigorously define and learn three increasing more powerful models of computation, then you find out that there are many more models, but they are not more powerful. So then you quantify and analyze what that condition means and how it effects our ability to compute actual hard problems."

FabHK 5y ago

:-) "Because non-determinism, the magic is that you always guess right. I wish that was true in real life. It would make exams a lot easier." [Lecture 2, 40:26 minutes: https://youtu.be/oNsscmUwjMU?t=2426 https://youtu.be/oNsscmUwjMU?t=2426 ]

unobatbayar 5y ago
If you study for the exam, wouldn't that make it deterministic?
- remexre 5y ago
  A non-deterministic Turing machine has the ability to choose "correctly" from a finite set of options. (This corresponds to search, which gives a nice intuitive notion that search can't do better than exponential time without knowledge of the search space unless P=NP.)

deleted 5y ago

[deleted]

MisterBastahrd 5y ago

Seems to me that one of the advantages that students at elite universities have is elite instruction. Every Harvard or MIT class that I've ever audited online has been insanely easy to follow.

truly 5y ago
It is true to some extent, but not all instructors at some universities are that good. You are probably experiencing a two-sided selection bias, since they (1) wouldn't upload a bad video and (2) you wouldn't follow something you are not interested in. The main advantage of elite universities is the club effect. It makes such universities attractive for students, professors, and industry -- a nice circle.
- deleted 5y ago
  [deleted]
- mirker 5y ago
  Here’s another way to put it in terms of money: * Research universities make money from research and not teaching. * Admins create promotion schedules on research and not teaching. * Teaching is the “cherry on top”. Good research > good teaching. Of course, top institutions want it all, but it’s not a hard requirement. Also: The hardest courses to teach are the intro classes. Those require teaching excellence that doesn’t overlap with technical chops. It is very hard to explain programming when you take it for granted.
  - truly 5y ago
    Teaching intro classes is indeed difficult. I like how some universities have dedicated staff for this (who are paid to only teach and not do research).

danrocks 5y ago

I wonder if anybody has built a Computer Science curriculum from the OCW lectures in a playlist or some other form, so people could (in theory) follow the same path as an actual MIT grad from beginning to end. This dude did something similar but he was mostly trying to sell his productivity method and ebooks. https://www.scotthyoung.com/blog/2018/03/15/how-successful-was-mit-challenge/ https://www.scotthyoung.com/blog/2018/03/15/how-successful-w... I am more interested in increasing my theoretical knowledge and taking deep classes in algorithms, data structures, linear algebra, vector calculus, and other foundational CS stuff.

truly 5y ago
I think that the will power to go through 3 or 4 years worth of lectures on your own would be the main blocker. The main benefit to in-class learning is that your peers drive you, and you drive your peers. As a not-on-campus-learner, you should probably concentrate on smaller pieces that can be had individually. It would not hurt to have a small community to discuss the things that you learn (e.g., peers at work) to keep you motivated as well.
- varelse 5y ago
  I was a curve breaker in college. These courses are fantastic for filling in the missing details left out to rehash the basics for everyone else and what I've forgotten decades later. Ironically, when people asked to study with me, they didn't get why studying for an hour each the 3-4 nights preceding an exam was crushing their cramming the single night before, so they would get frustrated with me and leave. Or I was doing spaced repetition before that was a thing. Which is to say motivated sorts can have trouble finding peers willing to stay focused.
  - metagame 5y ago
    Spaced repetition has been a thing for a really long time. Were you in college +/-1900? Depending on where the line is drawn for spaced repetition, it could be claimed to have been discovered initially from roughly 1885 to 1932.

ducktective 5y ago

Anyone knows a good course on formally proven methods of programming?

YorkshireSeason 5y ago
T. Nipkow, G. Klein, Concrete Semantics. http://concrete-semantics.org/ http://concrete-semantics.org/ B. C. Pierce et al, Software Foundations. https://softwarefoundations.cis.upenn.edu/ https://softwarefoundations.cis.upenn.edu/