As you may have read in "what a programmer does", I indirectly assert that a strong theoretical basis is indispensable for a strong programmer. This is the intent behind hiring computer scientists to become programmers. The language may change, but the underlying data structures and theoretical components won't change. I find my own skill-set lacking, however, in some important theoretical aspects. To improve it, and patch any potential holes in my understanding, I'll try covering the fundamentals with a concrete bottom-up approach over the next year.
The following is my ideal computer science curriculum, broken into 3 main sections, with multiple ordered topics in each section.
FOUNDATION:
Discrete Mathematics ==> Theory of Computation ==> Bottom-Up HardwareDescription
So, people falling off the computer science theory train in college starts with discrete math. Now, I was pretty solid at this in undergrad, but I'd really like to make some concepts like recognizing special series, solving combinatoric problems, doing convolutions, etc... into muscle memory.Moreover, the main reason you learn discrete math isn't just to get good at number problems, but so you can then understand the math behind turing machines and algorithms. After gaining this theoretical knowledge, we finish laying the foundation with a tour of computer systems by writing and programming on our own MIPS processor. The theoretical knowledge we gained can be applied to gain exact run-times for instructions on the processor, and designing the processor gives us a deeper insight into how our computers actually work.
Recommended Text Books
#1 Concrete Mathematics#2 Introduction to the Theory of Computation
#3 Elements of Computing Systems,
CORE:
Algorithm Design ==> Systems Programming ==> Language and Compiler DesignDescription
This is the most important part of the curriculum. It is the heart and soul of a sensible understanding of computer science in applied form. These concepts are the distillation of decades-worth of research packed in a modern, usable form. The goal of this segment is to give us the most elegant and powerful understanding of how our theory fits into solving real-world problems and designing real-world tools that run, almost magically, exactly how our imaginary-world theories say they should run.The Algorithm Design portion is a set of drills where we apply the theoretical computer we developed in section 1 to a set of the most common core problems in computer science. These problems have further implications in the limits of computer systems so they're pretty important to know.
The "Systems Programming" portion isn't like your dad's (uncle's? mom's?) systems programming course. It's more like a tour of the API linux provides user, and understanding how to use then and their implementation. Furthermore, we will learn about the x86_64 architecture as well as debuggers. Thankfully, the book Computer Systems covers this stuff quite well so we'll be following its outline for the most part.
Finally, Language and Compiler design is the trickiest, but most important black magic to learn. Like summoning an angel into earth-realm, making a parser to recognize a language is taking the beautiful abstract ideal that is a langauage and binding it into the pulsing shell of a physical machine. Parsers are tools that everything relies on, so it's pretty important to do it as well as humanly possible. Here we'll approach theoretical limits of parsers on language-by-language-class basis.
Recommended Text Books
#1 Algorithm Design Manual, Competitive Programming#2 Computer Systems: A Programmer's Perspective, Inside the C++ Object Model
#3 Compilers: Principles, Techniques, and Tools, Arithmetic and Logic in Computer Systems
COMPREHENSIVE:
Implementing Pure Math ==> Real Operating System Design ==>Scientific-Applications ==> Modern Problems in Computer Science
Description
The comprehensive section aims to provide a full, modern understanding of computer science. Yes, you may have a core understanding of computer science, but you have yet to drill it in via the final form of a comprehensive, modern computer system.This section is a canvas on which all previous theory can be drawn on. As such it will rely more on case studies and examples as we learn about scientific computing than the general theory that describes computers.
The ability to describe pure math in some arbitrary machine and understand its fundamental limits while in some physical form is so absurdly powerful, important that it's the original reason we even had computer systems. More importantly, as new tools get developed, we want to be able to verify their correctness and to develop new components ourselves.
The section concludes where we started in the beginning: with pure theory. In conclusion, we survey some modern intractable problems, examine their proofs and try to think of ways to compute them via approximation and heuristics.
Recommended Text Books
#1 Introduction to Numerical Computations, Numerical Recipes#2 Computer Systems: APP, Understanding the Linux Kernel
#3 Introduction to Linear Optimization, Some Bullshit on Probabilistic Simulations
#4 Computers and Intractability: A Guide to the Theory of NP-Completeness
Note: Since this is so far in the future, it's subject to minor changes
These are my goals. This is what I want to spend my time on.
The details of each topic's attack-plan will be devised as I reach them, there's always the possibility of the plan changing, realizing a step was a mistake, etc... Realistically, it won't be a quick process. Life gets in the way sometimes, and we often overestimate how much we can do every day, but we also underestimate how much we can get done with a consistent effort and a long duration. In the next year, utilizing my after-work time wisely, I expect I might get away with completing FOUNDATION and part of CORE. Part of me thinks the journey will be long, painful and boring, and there is some truth in this, but I'll also be sharing it with all you dear readers on this blog*, so it's sure to be a fun ride.
*two people
No comments :
Post a Comment