News for hackers. Stuff that matters.
Re:MIT 18.404J – Theory of Computation [video] by abzug on Sunday October 10, 2021 @06:34PM (#28822596)
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.
Re:MIT 18.404J – Theory of Computation [video] by soganess on Sunday October 10, 2021 @07:05PM (#28822766)
(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.
Re:MIT 18.404J – Theory of Computation [video] by amilios on Sunday October 10, 2021 @07:52PM (#28823049)
Sorry I just want to interject that it's "grok" not "grawk", that's an interesting spelling ahaha
Re:MIT 18.404J – Theory of Computation [video] by soganess on Monday October 11, 2021 @02:05PM (#28831095)
Hilarious! Thanks for the heads up.
Re:MIT 18.404J – Theory of Computation [video] by barrenko on Monday October 11, 2021 @08:04AM (#28827383)
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.

Re:MIT 18.404J – Theory of Computation [video] by soganess on Monday October 11, 2021 @02:05PM (#28831087)
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."

Re:MIT 18.404J – Theory of Computation [video] by ghaff on Sunday October 10, 2021 @07:06PM (#28822770)
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.

Re:MIT 18.404J – Theory of Computation [video] by kjhughes on Sunday October 10, 2021 @09:53PM (#28823791)
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.)