3 ms·

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.

by abzug 5y ago

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."
ghaff 5y ago
This is the syllabus: https://zyzx.haust.edu.cn/moocresource/data/070101/U/712/Syllabus/index.htm 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 5y ago
He addresses prerequisites specifically in the first lecture at this timestamp: https://youtu.be/9syvZr-9xwk?t=266 https://youtu.be/9syvZr-9xwk?t=266 (You're expected to be comfortable understanding mathematical theorems and producing proofs.)

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.

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

ghaff 5y ago

This is the syllabus: https://zyzx.haust.edu.cn/moocresource/data/070101/U/712/Syllabus/index.htm 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 5y ago

He addresses prerequisites specifically in the first lecture at this timestamp: https://youtu.be/9syvZr-9xwk?t=266 https://youtu.be/9syvZr-9xwk?t=266 (You're expected to be comfortable understanding mathematical theorems and producing proofs.)