MIT 18.404J – Theory of Computation [video] | Hacker News Reader

MIT 18.404J – Theory of Computation [video]

youtube.com

210 pointshidden-spyder40 comments

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.

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.

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.

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.

1980s, and I make no claim to having invented it - just that it was what I was doing, and that it worked but others hated it when they tried it out.

However, I did not hear the term spaced repetition until around 2000 or so and I realized it was very similar to what I used to do back in college.

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.

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

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

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.

https://www.saylor.org/

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.

> 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?

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.

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.)

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.

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).

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

Depends on who is teaching I assume

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.

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.

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.

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).

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

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)

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

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.

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.

:-) "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 ]

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

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.)

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.

(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.

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

Hilarious! Thanks for the heads up.

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.

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."

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.

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.)

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

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

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

Reply on news.ycombinator.com