MIT 18.404J – Theory of Computation [video]

https://www.youtube.com/playlist?list=PLUl4u3cNGP60_JNv2MmK3wkOt9syvfQWY

by hidden-spyder • 5 years ago

210 40 5 years ago

truly5• 5 years 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.

DelightOne2• 5 years 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• 5 years ago

Depends on who is teaching I assume

PennRobotics• 5 years 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

(The 2021 videos are on Youtube, unlisted.)

truly5• 5 years 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• 5 years 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 And https://news.ycombinator.com/item?id=28583194

rg111• 5 years 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?

whymauri• 5 years ago

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

jacobkg• 5 years 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• 5 years ago

That's amazing, I'd be really curious to know his reasons for leaning toward P vs NP been resolved.

OJFord• 5 years 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• 5 years 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• 5 years 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.

soganess3• 5 years 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• 5 years ago

Sorry I just want to interject that it's "grok" not "grawk", that's an interesting spelling ahaha

barrenko• 5 years 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.

ghaff• 5 years ago

This is the syllabus:

https://zyzx.haust.edu.cn/moocresource/data/070101/U/712/Syl... You can also see sample problem sets.

The short answer is you probably need some college-level math. This is an intermediate(?) math department course.

kjhughes• 5 years ago

He addresses prerequisites specifically in the first lecture at this timestamp:

https://youtu.be/9syvZr-9xwk?t=266

(You're expected to be comfortable understanding mathematical theorems and producing proofs.)

FabHK• 5 years 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 ]

unobatbayar• 5 years ago

If you study for the exam, wouldn't that make it deterministic?

remexre• 5 years 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.)

MisterBastahrd• 5 years 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.

truly5• 5 years 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.

mirker• 5 years 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.

danrocks• 5 years 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-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.

truly5• 5 years 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.

varelse2• 5 years 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.

AareyBaba• 5 years ago

The MIT Undergraduate Curriculum Map https://www.youtube.com/watch?v=eSRLIYaPPA0

ai_ia• 5 years ago

I am the creator of Primerlabs(https://Primerlabs.io) and we create self paced computer science courses. Though it's not based on OCW rather follows mostly teachyourselfcs.com reading list.

Also, we have two courses as of now. But we will start releasing more courses soon.

trenchgun• 5 years ago

OSSU is not exactly that, as it uses only courses where you can enrol.

"The OSSU curriculum is a complete education in computer science using online materials. It's not merely for career training or professional development. It's for those who want a proper, well-rounded grounding in concepts fundamental to all computing disciplines, and for those who have the discipline, will, and (most importantly!) good habits to obtain this education largely on their own, but with support from a worldwide community of fellow learners.

It is designed according to the degree requirements of undergraduate computer science majors, minus general education (non-CS) requirements, as it is assumed most of the people following this curriculum are already educated outside the field of CS. The courses themselves are among the very best in the world, often coming from Harvard, Princeton, MIT, etc., but specifically chosen to meet the following criteria.

Courses must:

Be open for enrollment Run regularly (ideally in self-paced format, otherwise running multiple times per year) Be of generally high quality in teaching materials and pedagogical principles Match the curricular standards of the CS 2013: Curriculum Guidelines for Undergraduate Degree Programs in Computer Science When no course meets the above criteria, the coursework is supplemented with a book. When there are courses or books that don't fit into the curriculum but are otherwise of high quality, they belong in extras/courses or extras/readings."

https://github.com/ossu/computer-science

oretoz• 5 years ago

https://www.saylor.org/

nverno• 5 years ago

This is site lays out a good plan https://teachyourselfcs.com/

Courses on there can be substituted for equivalents from MIT, eg. https://pdos.csail.mit.edu/6.828/2020/ for the Berkeley OS course. I just worked through that MIT course and the 6.824 Distributed systems (https://pdos.csail.mit.edu/6.824/schedule.html), also listed on that site [[personally, I recommend both of the forementioned classes taught by Robert Morris (also a cofounder of ycombinator)]] Both courses were fully available (lectures,assignments,projects) from the current course sites.

The MIT sites hosted there are incredibly open in general - https://courses.csail.mit.edu/, absolutely amazing institution.

ducktective• 5 years ago

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

YorkshireSeason• 5 years ago

T. Nipkow, G. Klein, Concrete Semantics. http://concrete-semantics.org/

B. C. Pierce et al, Software Foundations. https://softwarefoundations.cis.upenn.edu/

MIT 18.404J – Theory of Computation [video]

Related Stories