CSC236H: Introduction to the Theory of Computation
Thank you to Prof. Francois Pitt for providing this information!
So, what exactly IS CSC236H1??
The “second half” of CSC165H1, where we apply proof techniques to topics that are central to CS: algorithm correctness (how to prove it, but more importantly, how to use it to design correct algorithms from the start, instead of programming by trial-and-error); and algorithm complexity (expanding the analysis of worst-case time complexity to include recursive algorithms). We take advantage of your growing mathematical maturity to discuss mathematical induction more in depth, including strong induction and structural induction, and we spend some time applying our reasoning skills to discuss a central topic in theoretical CS: models of computation and their power to solve certain kinds of problems — or not.
Keys to Success!
This is very much a theoretical course. It's quite possible to explore the topics through forms of trial-and-error, but unlike programming courses (where you can try without thinking very much about what you're doing, and run the code to figure out the result), you need to understand how to judge the correctness of your ideas for yourself. This means having a good understanding of how to prove statements: after all, proofs are NOT some arbitrary mathematical material that we are "forcing" you to learn for no reason at all! They are an essential tool in reasoning about algorithms. The foundation you built in CSC165H1 is critical to your success here: if you are still uncertain about any of it, you would be making excellent use of your time to go back and review this material. And an important note about this: we do NOT mean "how do I write up a proof to get good marks", but "how do I come up with correct reasoning". It's the content that matters the most — the structure of proofs is important, of course, but only as the support to ensure that your reasoning is correct, that the conclusions you reach are actually true.
How is CSC236H1 going to help me?
Understanding what it means for an algorithm to be correct is a key part of studying more complex data structures (in CSC263H1) and algorithms (in CSC373H1) — both of which are essential components of many follow-on courses and technical interviews. So, not only is this material foundational to further studies in many areas of CS, but it's something companies actually care about — it has real impact on your actual job prospects. And your understanding of data structures and algorithms will suffer if you don't understand how and why they work — which requires understanding algorithm correctness. For example, I doubt very much that you'll be asked directly to come up with (let alone prove) a loop invariant in any technical interview (or even any course outside CSC236H1, CSC263H1, or CSC373H1) — but understanding loop invariants will allow you to come up with a correct implementation for a complex data structure or algorithm in a small fraction of the time it would take you to do the same through blind trial-and-error, especially as the data structures and algorithms get more and more complex. It will make you a better programmer, period.
How will CSC236H assignments help me learn?
The biggest obstacle I've seen to students doing well in CSC236H1 is a matter of belief: if you start the course with an attitude that "I'm not going to get this anyway, let me just get through it", you have closed the door on any chance you have of getting the most out of the course! This attitude will colour your approach to the course: you will worry about your marks, instead of focusing on understanding the material (which anyone can do).
It's very easy to get caught up in the "I need these marks" view of assignments, especially if you are worried about your ability to solve problems on tests and exams. In our experience, this is a self-fulfilling prophecy: if you focus too much on coming up with a solution that will maximize your marks on assignments, you are sabotaging your own understanding of the material that the assignment is based on — and if you understand the material less, you will perform more badly on the same material on tests and exams. Instead, we find that students who prioritize understanding how to solve assignment problems (without worrying about their mark) inevitably perform better on the tests and exam. And which would you rather do: get a high mark on an assignment worth 5% and a low mark on a test worth 15%, or get a low mark on the 5% assignment and a high mark on the 15% test? Remember that you cannot learn without making mistakes — if you make NO mistake ever, then it means you have nothing to learn! The assignments are the correct place for you to make mistakes, so you can learn from them and know how NOT to make those same mistakes in the future. We want to see how you think a problem should be solved, so that we can tell you if you are correct or not. Don't throw away your chance to learn because of a near-sighted desire for a "perfect" mark: remember that you're here to improve yourself (to learn), not just to get a grade. So dive into those assignments, let the material arouse your interest, grapple with problems that challenge your current understanding, and allow yourself to move to the next level!
A few last words from the instructor:
An unfortunate side effect of the highly competitive program admission process is that it is a "reasonable" strategy to maximize your marks (perhaps at the expense of your depth of learning). And while high marks correlate with high understanding, the relationship is not as direct as one might hope. In other words, now that you're "in", please keep an open mind about shifting your perspective to get the most out of your studies and out of each individual course. It's difficult to achieve BOTH the elusive "4.0 GPA" and a deep understanding of the material you are learning throughout your studies. Think it through: what will be most useful in your future life? Not just next term or next year's future life, not just "after graduation", but 5, 10, even 20 years down the road. Do your future self a favour: take advantage of the incredible opportunity you have right now to engage deeply with some foundational learning, to benefit from your peers in learning together, so that when you leave the U of T you can say that you have truly mastered the skills and topics that you encountered. This will matter so much more than tiny differences in your GPA — nobody (not even you) will care about your GPA 5 years out after graduation, but the knowledge and experience you come out with will still be relevant and useful and appreciated.
CSC236H is a prerequisite for...
CSC263H1 — Data Structures and Analysis
CSC265H1 — Enriched Data Structures and Analysis
CSC410H1 — Software Testing and Verification
CSC448H1 — Formal Languages and Automata
CSC463H1 — Computational Complexity and Computability
CSC465H1 — Formal Methods in Software Design
MAT301H1 — Groups and Symmetries
MAT309H1 — Introduction to Mathematical Logic
MAT315H1 — Introduction to Number Theory