Math topics useful for computer science/programming(matheducators.stackexchange.com)
matheducators.stackexchange.com
Math topics useful for computer science/programming
http://matheducators.stackexchange.com/questions/1734/what-should-be-included-in-a-freshman-mathematics-for-computer-programmers-cou/1745#1745
68 comments
I agree, I have had to learn Newton's methode for differential equations (for simulation), I've had to use logic and an automatic prover (for system validation), I've had to do some complexity analysis (for everything), I've had to play with linear applications, matrices and all the stuff around 3D, I've had to dig into geographical projection equations for another job (in GIS). I'm currently toying with computational geometry. I think what is important is some kind of math to understand how those people write (which far from obvious), and then random stuff to learn to switch.
This comment is a little frustrating, because part of the point of linking to the Stack Overflow post is to continue the discussion, which is obviously germane to our site. Why not dig into specifics of how you'd approach the intersection of math and CS?
It's actually inspired me to write my own article, but that will take time.
Meanwhile, I actually write a blog called "Math Intersect Programming." Even though it's more about my specific interests than how a freshman should approach the topics, and I certainly emphasize the mathematical ideas over the engineering challenges, it still gives a good idea of what I would suggest:
Orient the learning around applications in CS. Find a problem that requires the mathematics you want to learn, and learn it with the persistent contextual understanding that you are trying to do something more than just tinker with definitions. Do this for one application and repeat as desired.
My view is that when this is done, you learn to focus on the things that matter over the things that are used to fill empty space in courses (calculus courses come to mind as a specifically abhorrent example of this). You get better at seeing the forest over the trees.
The problem is this avoids the OP's question (and this ensuing discussion about the OP's questions and the purported answers), since you can't organize a single class around it. Another problem is that very few books are written this way, or are only superficially so.
Meanwhile, I actually write a blog called "Math Intersect Programming." Even though it's more about my specific interests than how a freshman should approach the topics, and I certainly emphasize the mathematical ideas over the engineering challenges, it still gives a good idea of what I would suggest:
Orient the learning around applications in CS. Find a problem that requires the mathematics you want to learn, and learn it with the persistent contextual understanding that you are trying to do something more than just tinker with definitions. Do this for one application and repeat as desired.
My view is that when this is done, you learn to focus on the things that matter over the things that are used to fill empty space in courses (calculus courses come to mind as a specifically abhorrent example of this). You get better at seeing the forest over the trees.
The problem is this avoids the OP's question (and this ensuing discussion about the OP's questions and the purported answers), since you can't organize a single class around it. Another problem is that very few books are written this way, or are only superficially so.
I want to chime in and say that I've found your blog wonderful, and since you're too modest to post a link, let me do it: http://jeremykun.com/
I largely agree with your sentiments.
However, you should keep in mind that these lists are intended as an answer to "What Math should we teach freshmen undergrads?", not an answer to "What Math do all the CS-people need to know?". The latter is naturally a very small subset of Math, the 'logicish' type.
I do STRONGLY agree with you that we should help students figure out the areas that they find interesting, and let them know what kind of Math is useful for each.
However, you should keep in mind that these lists are intended as an answer to "What Math should we teach freshmen undergrads?", not an answer to "What Math do all the CS-people need to know?". The latter is naturally a very small subset of Math, the 'logicish' type.
I do STRONGLY agree with you that we should help students figure out the areas that they find interesting, and let them know what kind of Math is useful for each.
But the question is one and the same in this instance: they're asking what should be taught in "the" math class for a CS degree. If that doesn't contain the math that all CS-people need to know, then what should it contain?
The OP describes universal algebra and term rewriting, which is what I claim is the logicish type that is not as crucial as, say, linear algebra if you want to find widely applicable mathematics for CS/programming.
The OP describes universal algebra and term rewriting, which is what I claim is the logicish type that is not as crucial as, say, linear algebra if you want to find widely applicable mathematics for CS/programming.
It may not be crucial for programming, but I'd say it's more crucial than Linear Algebra for finishing the degree at all, since there are CS subjects that you just can't really take unless you learn the logicish stuff.
I can't imagine not taking calculus either... How do you comfortably take the logarithm of an inequality without it?
This whole idea seems so ridiculously impossible to me...
I can't imagine not taking calculus either... How do you comfortably take the logarithm of an inequality without it?
This whole idea seems so ridiculously impossible to me...
This does not seem very informed, starting from the false premise in the question up to the random concepts listed in the answers.
Calculus is actually important for Computer Science, it's actually important for everything, it's where you learn how to handle the exponential function and the natural logarithm, how to do approximations and bounds, how to handle infinite series, etc., and those things then appear all over the place, unlike most things listed it's something that you can expect to encounter almost regardless of what domain you are interested in.
I mean, the guy asks what should replace Calculus and then the first answer includes "Asymptotics", "basic limits, sequences and series", so actually calculus. In general I cringe a little every time I hear Computer Science people should focus on "discrete math", because without tools from analysis you can only solve the most trivial discrete problems. And yes, calculus by itself is hardly ever applicable in CS, yet you still have to learn it, tough luck. In general what is not stressed enough I think is that applying math is hard and you need to learn a lot of it before you have enough tools to tackle problems anywhere close to real-world complexity.
The top answer also lists random concepts. I am learning probability currently, for applications in machine learning. "Discrete spaces, Bayes theorem and expected values" you can learn in a day, "Markovs, Chebyshev and Chernoff inequalities" are mostly only useful for further theoretical work, so is "the law of large numbers". What will really be useful will depend a lot on the applications, if you are a theoretical computer scientist, mastery of generating functions and transforms will be useful, and it's one of those instances where discrete problems are solved via tools from calculus/analysis. For machine learning you need to know everything about the normal distribution by heart, and this means you have to know everything about the exponential function by heart, so again back to calculus. Notions from information theory are useful, but of course none of the ones he listed. The comment "This is a must for modern programmers." sounds just comic.
Calculus is actually important for Computer Science, it's actually important for everything, it's where you learn how to handle the exponential function and the natural logarithm, how to do approximations and bounds, how to handle infinite series, etc., and those things then appear all over the place, unlike most things listed it's something that you can expect to encounter almost regardless of what domain you are interested in.
I mean, the guy asks what should replace Calculus and then the first answer includes "Asymptotics", "basic limits, sequences and series", so actually calculus. In general I cringe a little every time I hear Computer Science people should focus on "discrete math", because without tools from analysis you can only solve the most trivial discrete problems. And yes, calculus by itself is hardly ever applicable in CS, yet you still have to learn it, tough luck. In general what is not stressed enough I think is that applying math is hard and you need to learn a lot of it before you have enough tools to tackle problems anywhere close to real-world complexity.
The top answer also lists random concepts. I am learning probability currently, for applications in machine learning. "Discrete spaces, Bayes theorem and expected values" you can learn in a day, "Markovs, Chebyshev and Chernoff inequalities" are mostly only useful for further theoretical work, so is "the law of large numbers". What will really be useful will depend a lot on the applications, if you are a theoretical computer scientist, mastery of generating functions and transforms will be useful, and it's one of those instances where discrete problems are solved via tools from calculus/analysis. For machine learning you need to know everything about the normal distribution by heart, and this means you have to know everything about the exponential function by heart, so again back to calculus. Notions from information theory are useful, but of course none of the ones he listed. The comment "This is a must for modern programmers." sounds just comic.
>Calculus is actually important for Computer Science, it's actually important for everything
This.
If you take a look at the MIT course "Mathematics for Computer Science"[1] you'll see that the only prerequisite for learning the math for cs is ... calculus!
[1]http://ocw.mit.edu/courses/electrical-engineering-and-comput...
This.
If you take a look at the MIT course "Mathematics for Computer Science"[1] you'll see that the only prerequisite for learning the math for cs is ... calculus!
[1]http://ocw.mit.edu/courses/electrical-engineering-and-comput...
I was a TA for that course last semester. I think the actual reason calculus is a prerequisite is just so that students will have some mathematical maturity beforehand. We didn't really teach any concepts that actually used calculus (that I remember).
That said, I totally agree that calculus is good to know for a CS student.
That said, I totally agree that calculus is good to know for a CS student.
Oh, you do use calculus, at least in the notes, actually touching on the topics I mentioned, so it's a good illustration. For example in the chapters about generating functions and on sums and asymptotics:
http://ocw.mit.edu/courses/electrical-engineering-and-comput...
http://ocw.mit.edu/courses/electrical-engineering-and-comput...
http://ocw.mit.edu/courses/electrical-engineering-and-comput...
http://ocw.mit.edu/courses/electrical-engineering-and-comput...
> Calculus is actually important for Computer Science, it's actually important for everything, it's where you learn how to handle the exponential function and the natural logarithm, how to do approximations and bounds, how to handle infinite series, etc., and those things then appear all over the place,
It's still interesting to think about which branches of math are actually applicable to programming itself.
People tend to talk about programming and math as very strongly related, and of course there is the obvious relationship that "some computer programs do particular kinds of math" like you're talking about here.
But there is no (intuitive) overlap between writing, say, a web application and doing algebraic or calculus computation on paper. However, there are things like:
- Set theory underpinning relational databases
- Typed lambda calculus underpinning functional programming
I'd be interested in other examples like this.
It's still interesting to think about which branches of math are actually applicable to programming itself.
People tend to talk about programming and math as very strongly related, and of course there is the obvious relationship that "some computer programs do particular kinds of math" like you're talking about here.
But there is no (intuitive) overlap between writing, say, a web application and doing algebraic or calculus computation on paper. However, there are things like:
- Set theory underpinning relational databases
- Typed lambda calculus underpinning functional programming
I'd be interested in other examples like this.
I have a couple simple ones off the top of my head:
- You write a recursive program the same way you write an inductive proof
- Abstract algebra and category theory are likely relevant, especially for metaprogramming. My math education hasn't included this, so I can't say much more.
- Linear algebra is just ridiculously important
- Statistics for machine learning. Also for figuring out how to combine data in a meaningful way. There are also a lot of people asking statistical questions directly, and writing programs is how you get those kinds of answers in a reasonable timeframe.
- You write a recursive program the same way you write an inductive proof
- Abstract algebra and category theory are likely relevant, especially for metaprogramming. My math education hasn't included this, so I can't say much more.
- Linear algebra is just ridiculously important
- Statistics for machine learning. Also for figuring out how to combine data in a meaningful way. There are also a lot of people asking statistical questions directly, and writing programs is how you get those kinds of answers in a reasonable timeframe.
> Abstract algebra and category theory are likely relevant, especially for metaprogramming.
In general, the whole "oh yeah CS people should know some category theory and abstract algebra" is pretty hilarious.
First, it's a bit like saying "oh yeah CS people need to know the undegraduate basics and also the generalization that most mathematicians don't encounter until a couple years into grad school."
Second, most people who say this really mean "a conceptual grasp on different types of morphisms is useful". But that's like saying you need calculus in order to drive a car; or, in the case of categories, it's like saying you need two semesters of real analysis in order to drive a car.
Why not just say "knowing about different sorts of mappings is pretty useful in functional programming"? Knowing how this generalizes to more abstract mathematical objects is totally unnecessary.
In general, the whole "oh yeah CS people should know some category theory and abstract algebra" is pretty hilarious.
First, it's a bit like saying "oh yeah CS people need to know the undegraduate basics and also the generalization that most mathematicians don't encounter until a couple years into grad school."
Second, most people who say this really mean "a conceptual grasp on different types of morphisms is useful". But that's like saying you need calculus in order to drive a car; or, in the case of categories, it's like saying you need two semesters of real analysis in order to drive a car.
Why not just say "knowing about different sorts of mappings is pretty useful in functional programming"? Knowing how this generalizes to more abstract mathematical objects is totally unnecessary.
Well, frankly you can get along not knowing the "Gang of Four" design patterns and write Java. By the same token, you don't need to know about iterables and comprehensions to write Python, smart pointers to write C++, Graph theory to use a Graph database, macros to write LISP, etc.
By analogy, you don't need to know abstract algebra and category theory to write Haskell. But as in the other cases, knowing helps.
By analogy, you don't need to know abstract algebra and category theory to write Haskell. But as in the other cases, knowing helps.
I think you misunderstood my criticism.
"Different sorts of mappings" is NOT synonymous with "category theory". Not even close. Heck, Euclid knew about "different sorts of mappings".
Most everything in Gamma et al is arguably useful for everyday programming in Java. Maybe 5-10 pages of MacLane is useful for everyday programming in functional languages.
Unless by "Category Theory" you mean "5-10 pages of MacLane", Category Theory -- on the whole -- is a horrendously inefficient way of teaching about "different sorts of mappings useful in functional programming."
Unless you want to use functional programming as an environment for doing pure mathematics, there's no reason to actually study actual Category Theory.
"Different sorts of mappings" is NOT synonymous with "category theory". Not even close. Heck, Euclid knew about "different sorts of mappings".
Most everything in Gamma et al is arguably useful for everyday programming in Java. Maybe 5-10 pages of MacLane is useful for everyday programming in functional languages.
Unless by "Category Theory" you mean "5-10 pages of MacLane", Category Theory -- on the whole -- is a horrendously inefficient way of teaching about "different sorts of mappings useful in functional programming."
Unless you want to use functional programming as an environment for doing pure mathematics, there's no reason to actually study actual Category Theory.
Functional Programming is a vast subject.
I've really never needed an abstraction for semigroups, monoids, meet-semi-lattices, monads, comonads, arrows or catamorpisms in Clojure, Common Lisp, Scheme, or Hy.
These concepts become more relevant when I program Haskell, Agda, Isabelle/HOL, or Coq.
I'd say a stronger analogy can be made between reading MacLane's Catagories for the Working Mathematician and reading Hoyte's Let Over Lambda; you really only need to read a little bit of these books to get the core concepts. That being said, depending on what sort of functional programming you're doing, a strong background in category theory or meta-programming can enabling (or not).
I've really never needed an abstraction for semigroups, monoids, meet-semi-lattices, monads, comonads, arrows or catamorpisms in Clojure, Common Lisp, Scheme, or Hy.
These concepts become more relevant when I program Haskell, Agda, Isabelle/HOL, or Coq.
I'd say a stronger analogy can be made between reading MacLane's Catagories for the Working Mathematician and reading Hoyte's Let Over Lambda; you really only need to read a little bit of these books to get the core concepts. That being said, depending on what sort of functional programming you're doing, a strong background in category theory or meta-programming can enabling (or not).
> when I program Haskell, Agda, Isabelle/HOL, or Coq.
That's fair. Although Haskell is a bit of an odd man out in that list, both in terms of its nature and in terms of its typical use case.
> That being said, depending on what sort of functional programming you're doing, a strong background in category theory or meta-programming can enabling (or not).
This is where the analogy between the two books breaks down. When you're using a functional programming language as a proof assistant, category theory can be helpful. But this is far less common than meta-programming.
edit: 2nd paragraph.
That's fair. Although Haskell is a bit of an odd man out in that list, both in terms of its nature and in terms of its typical use case.
> That being said, depending on what sort of functional programming you're doing, a strong background in category theory or meta-programming can enabling (or not).
This is where the analogy between the two books breaks down. When you're using a functional programming language as a proof assistant, category theory can be helpful. But this is far less common than meta-programming.
edit: 2nd paragraph.
More simply (but hard to appreciate without going through semesters of work): know that structure-preserving mappings are the important parts.
Yes. But my more important point is that you can tach about these mappings in isolation, in the context of functional programming. No Category Theory needed.
You can teach about "different sorts of mappings" in just about any setting. In fact, that's kind of the whole reason Category Theory exists. So why teach the general result when all you care about is its application to functional programming?
You can teach about "different sorts of mappings" in just about any setting. In fact, that's kind of the whole reason Category Theory exists. So why teach the general result when all you care about is its application to functional programming?
The importance of structure preserving mappings shows up in many other places besides functional programming. I do believe context is important, but having multiple contexts is even better.
As someone currently teaching themselves linear algebra (via Strang), I'm curious as to why you believe linear algebra is ridiculously important. I see its applications to graph programming and obviously to cryptography, but I've done a lot of work in both of those subjects and never strictly needed a background in linear algebra to be effective.
Linear algebra is insanely important. I would consider the most important area of numerical mathematics to know. Any sort of mathematical modeling you do is going to involve linear algebra at some point.
I have argued that almost all numerical mathematics, in some form, can be modeled as a linear algebra problem. Google's original page rank algorithm is linear algebra. Remember that Netflix challenge? All linear algebra. Optimisation? Linear algebra. Want to do any engineering of a system? Behind the scenes it is all linear algebra as every single numerical technique for solving PDEs, that I am aware of, can be thought of in a linear algebra sense. Fluid modeling is all linear algebra. A lot of the machine learning I've seen is just linear algebra. I would also that almost every simulation running on the world's supercomputers involves linear algebra.
Do you absolutely need linear algebra to do this things? No. Just like I don't need to understand how my car works to drive it. But having an understanding how these systems operate can really help you use them in a more logical way.
I have argued that almost all numerical mathematics, in some form, can be modeled as a linear algebra problem. Google's original page rank algorithm is linear algebra. Remember that Netflix challenge? All linear algebra. Optimisation? Linear algebra. Want to do any engineering of a system? Behind the scenes it is all linear algebra as every single numerical technique for solving PDEs, that I am aware of, can be thought of in a linear algebra sense. Fluid modeling is all linear algebra. A lot of the machine learning I've seen is just linear algebra. I would also that almost every simulation running on the world's supercomputers involves linear algebra.
Do you absolutely need linear algebra to do this things? No. Just like I don't need to understand how my car works to drive it. But having an understanding how these systems operate can really help you use them in a more logical way.
`ridiculously` might be hyperbole, but the two biggest ones I can think of are computer graphics and machine learning; these of which you can't even sneeze at without getting in linear algebra.
I have some sense of the linear algebra implicated in machine learning (I lived for many years with a comp. neuroscience PhD), but I have no visibility into graphics. So with my ignorance pinned to my lapel: the linear algebra involved in computer graphics is pretty simple, right? Just knowing how to manipulate vectors and matrices? Not a lot of eigenvalues, or for that matter orthogonalization?
I'm asking not to rebut but because I hope to prompt the sort of "sell us on linear algebra" statement that will make me study harder. :)
I'm asking not to rebut but because I hope to prompt the sort of "sell us on linear algebra" statement that will make me study harder. :)
Much of computer graphics operates in projective space (http://en.wikipedia.org/wiki/Projective_space), so it's a little bit more than cookie-cutter linear algebra. This is done so that translations in 3D space — which aren't linear transformations — can be represented as 4D linear transformations in projective space via homogeneous coordinates (http://en.wikipedia.org/wiki/Homogeneous_coordinates).
Still, many folks use the APIs without really grokking that, so in practice it can be a bit cookie-cutter. I think of it similarly to how people can use crypto APIs without, say, really understanding what's going on under the hood.
BTW, projective space is also intimately related to elliptic curves (as you may or may not know — not implying anything!). So that darn linear algebra is lurking all over the place.
Likewise, any time you're talking about fields (even finite fields), vector spaces and linear algebra are right around the corner.
Still, many folks use the APIs without really grokking that, so in practice it can be a bit cookie-cutter. I think of it similarly to how people can use crypto APIs without, say, really understanding what's going on under the hood.
BTW, projective space is also intimately related to elliptic curves (as you may or may not know — not implying anything!). So that darn linear algebra is lurking all over the place.
Likewise, any time you're talking about fields (even finite fields), vector spaces and linear algebra are right around the corner.
I'm familiar with projective coordinates for elliptic curves, but the funny thing about curves is that, for high-speed software, the math is tricky enough that you don't "need" to grok it: there's an "explicit formulas database" that you can just copy from:
http://www.hyperelliptic.org/EFD/g1p/index.html
Curves are what made algebra 'click' for me, getting me from my high school understanding of "algebra is math about unknown variables" to "algebra is about sets of related objects with operators that have identities and inverses".
http://www.hyperelliptic.org/EFD/g1p/index.html
Curves are what made algebra 'click' for me, getting me from my high school understanding of "algebra is math about unknown variables" to "algebra is about sets of related objects with operators that have identities and inverses".
Disclaimer: I'm not very experienced with CG, but I think your intuition is correct on CG, for lots of 'boilerplate' game or photoshop programming.
However, I do think you can find plenty of examples in academia. For example, applying PCA
http://cmp.felk.cvut.cz/~hlavac/TeachPresEn/11ImageProc/15PC...
(Perhaps this is just the result of crossover between CG and ML/Statistics here).
Not a good sell, but perhaps someone with more experience can chime in.
However, I do think you can find plenty of examples in academia. For example, applying PCA
http://cmp.felk.cvut.cz/~hlavac/TeachPresEn/11ImageProc/15PC...
(Perhaps this is just the result of crossover between CG and ML/Statistics here).
Not a good sell, but perhaps someone with more experience can chime in.
- number theory underpinning almost all modern cryptography
- NFA/DFA underpinning regular expressions ( well practical regular exp are not in fact regular, but anyway)
- NFA/DFA underpinning regular expressions ( well practical regular exp are not in fact regular, but anyway)
Actually, although number theory touches a lot of "conventional" crypto (some of the design rationale for AES, polynomial MACs), most of workhorse cryptography in normal applications is not especially number-theoretic, and has more to do with information theory and statistics.
The belief that number theory is essential for cryptography is due to its role in public-key cryptography. But even if you're comfortable with number theory, new applications of public-key cryptography are tremendously difficult to get right, and require subject-matter specific expertise.
The belief that number theory is essential for cryptography is due to its role in public-key cryptography. But even if you're comfortable with number theory, new applications of public-key cryptography are tremendously difficult to get right, and require subject-matter specific expertise.
Another example:
- Linear algebra used in graphics and game programming
- Linear algebra used in graphics and game programming
Well there is the Curry-Howard correspondence. Though I don't know if this correspondence is intuitive in the general case - I guess what this correspondence means is that programs can be translated to some computational model, which can then be translated to some formal logic, and then back again (but with these kinds of high-level facts, I'm bound to have misunderstood something, somewhere). Though this connection might be only intuitive for some kinds of languages - like statically typed functional languages.
I think it's amazing that programming can leverage and express so many mathematical facts - from implementing a binary tree that is enforced to always be balanced by the type system in Haskell, to using linear types to safely use and free OS resources in ATS.
I think it's amazing that programming can leverage and express so many mathematical facts - from implementing a binary tree that is enforced to always be balanced by the type system in Haskell, to using linear types to safely use and free OS resources in ATS.
I certainly agree. I'm trying to re-learn advanced calculus and analysis from a rigorous standpoint, as I think it is crucial for developing deep knowledge in probability theory, among other things.
Slightly tangential but, while there are many lovely books for linear algebra (like Halmos, Axler or Hoffman & Kunze), as a newcomer I don't find analysis literature so exciting. The standard, Rudin, is really synthetic Bourbaki-style. I like short and precise books, but I found it really removes most intuition. Any good books you happen to like? Perhaps Pugh or Zorich?
Slightly tangential but, while there are many lovely books for linear algebra (like Halmos, Axler or Hoffman & Kunze), as a newcomer I don't find analysis literature so exciting. The standard, Rudin, is really synthetic Bourbaki-style. I like short and precise books, but I found it really removes most intuition. Any good books you happen to like? Perhaps Pugh or Zorich?
Among the many texts almost the only one I really liked and learnt from is Courant's "Differential and Integral calculus" and the newer edition "Introduction to Calculus and Analysis". It doesn't do the typical modern division of topics and instead treats single-variable calculus, multi-variable calculus and real analysis in its two volumes in a single long sequence, but the writing style is very pleasant and the exposition very intuitive, and it includes a lot of physics applications. Hardy "A course of pure mathematics" is great too, but it is much more, well, pure, but it stays relatively intuitive and the clarity with which he writes is unparalleled, many things I first really understood from this book. Those are old texts though and notation and details of exposition differ here and there from modern standards.
I have the book by Pugh, but that one is pure^2, even as far as analysis texts go, the problems are difficult and there are no solutions, so I think it would work only for people very in love with absolutely pure mathematics and most likely only in an academic setting, while I am interested in applications and self-studying. From modern texts, given your interests, I would look at "Understanding analysis" by Abbott and "Measure, Integral and Probability" by Capinski, both pleasant to read and together providing a not too steep path toward measure-theoretic probability.
I have the book by Pugh, but that one is pure^2, even as far as analysis texts go, the problems are difficult and there are no solutions, so I think it would work only for people very in love with absolutely pure mathematics and most likely only in an academic setting, while I am interested in applications and self-studying. From modern texts, given your interests, I would look at "Understanding analysis" by Abbott and "Measure, Integral and Probability" by Capinski, both pleasant to read and together providing a not too steep path toward measure-theoretic probability.
Thanks for taking the time to write such a thorough reply. I find Abbott a bit imprecise sometimes, but Courant is a fantastic book. Could you also mention to some of your favorite math references, in particular those that deal with probability theory and statistics?
I found it easier to handle Analysis by following the sequence:Spivak ->Apostol->Rudin.
I think I am ready to tackle Rudin, but I don't really like it. I'm not alone there. Arnol'd is said to have called it Bourbakian propaganda. That's a bit extreme, but I certainly dislike books that strive to remove intuition:
http://pauli.uni-muenster.de/~munsteg/arnold.html
http://pauli.uni-muenster.de/~munsteg/arnold.html
[deleted]
Interested in a range of book recommendations for Calculus on up.
Also I'm not sure how you can mention information theory in the context of programming and not mention PCM or the Shannon-Nyquist sampling theorem...
"Many students struggle with the idea of recursion..."
I still remember one of the worst bugs I'd ever introduced (in terms of pain to me). I was maybe 2-3 years out of my bachelors, and I thought recursion was so nifty that I'd use it where ever I could. I was coding C++, at the time. And, I got the dreaded 2am call after all of the production servers went down hard. Like terminate and corrupt data hard.
Lesson learned: it's good to know recursion, but it's also good to know maximum stack sizes.
I still remember one of the worst bugs I'd ever introduced (in terms of pain to me). I was maybe 2-3 years out of my bachelors, and I thought recursion was so nifty that I'd use it where ever I could. I was coding C++, at the time. And, I got the dreaded 2am call after all of the production servers went down hard. Like terminate and corrupt data hard.
Lesson learned: it's good to know recursion, but it's also good to know maximum stack sizes.
There's also thunk/trampolining continuation style to convert recursion easily into something that is not stack limited. http://nathansuniversity.com/cont.html
What problem were you trying to solve with recursion?
That and tail-call optimisation :)
In my experience, I've seen a lot of students entering CS not comfortable with even basic arithmetic and algebra, despite it not being mentioned in any of the linked responses.
As for calculus, I think its importance is overrated - unless you are specifically doing some numerical computation that requires it.
As for calculus, I think its importance is overrated - unless you are specifically doing some numerical computation that requires it.
Calculus gives you some of the intuition for figuring out a good big O bound for the computing time of an algorithm.
I'd include combinatorics under 'useful' too - although the basics are usually covered in statistics courses. Odd that the list mentions differential equations but not basic calculus, which I'd think is more fundamental.
It's also interesting to consider the chapter headings in Concrete Mathematics (Graham, Knuth, Patashnik), a text designed with students of CS and programming in mind:
It's also interesting to consider the chapter headings in Concrete Mathematics (Graham, Knuth, Patashnik), a text designed with students of CS and programming in mind:
Recurrent Problems
Summation
Integer Functions
Number Theory
Binomial Coefficients
Special Numbers
Generating Functions
Discrete Probability
AsymptoticsI got Concrete Mathematics a few days ago, after someone recommended it. My background is physics, and I find the "mathematicians' style" to be very awkward to learn from. This book is excellent for me - concrete examples - it is always trying to solve specific problems, so if I don't follow the theory, I can always refer to a concrete example and try to understand that specific case. This the way I learn best/fastest.
[deleted]
Although I did mathematics to degree level, I have used so little of it in my professional career that I have largely forgotten it all now. Any such list is going to depend on what area of programming you want to get into.
For a lot of programming understanding user interaction and human psychology is much more important than mathematics.
For a lot of programming understanding user interaction and human psychology is much more important than mathematics.
Why not teach math + programming together? I didn't seem to see anyone suggest that.
Calculus: simplify and iterate to solve a problem (like Newton's Method). Lots of issues to tackle with. Much more useful than learning formulas, but it can also be interesting to show how converting forms can take an unstable problem into a stable one.
Combinatorics: Explore the small side of a problem, code up the larger version, explore how far one can get, show methods for dealing with the problem beyond the scope.
Graphics, user interface design, etc., are also very big in math. In a course I teach to Enviro Science people, they come in scar(r)ed of math and by the end, they enjoy it. A big trick is getting them to use GeoGebra in an exploratory, visual fashion. It makes the math real.
The same approach in code can help make CS students get math while also getting the issues in CS. Anyone who thinks the exponential as 1+ x+ x^2/2 + .... is useful as is for x = 100 needs some actual experience with it. But at the same time, teaching them how to translate e^100 ~~ e^(43ln(10) + .98) ~~ 10^43 (1 + .98 + .98^2/2 + .98^3/6) = 10^43 * 2.62 has its value (compare to e^100 ~~ 2.69 * 10^43)
This is the kind of math that is useful. Exploratory math that struggles with mathematical truths and practical implementations. Students should get a sense of the limits of computers, what they can handle and not.
And designing a good math interface for these problems can be quite the UI learning experience. There are so many ways to explore math.
Stop teaching dry math and start teaching programming math.
Calculus: simplify and iterate to solve a problem (like Newton's Method). Lots of issues to tackle with. Much more useful than learning formulas, but it can also be interesting to show how converting forms can take an unstable problem into a stable one.
Combinatorics: Explore the small side of a problem, code up the larger version, explore how far one can get, show methods for dealing with the problem beyond the scope.
Graphics, user interface design, etc., are also very big in math. In a course I teach to Enviro Science people, they come in scar(r)ed of math and by the end, they enjoy it. A big trick is getting them to use GeoGebra in an exploratory, visual fashion. It makes the math real.
The same approach in code can help make CS students get math while also getting the issues in CS. Anyone who thinks the exponential as 1+ x+ x^2/2 + .... is useful as is for x = 100 needs some actual experience with it. But at the same time, teaching them how to translate e^100 ~~ e^(43ln(10) + .98) ~~ 10^43 (1 + .98 + .98^2/2 + .98^3/6) = 10^43 * 2.62 has its value (compare to e^100 ~~ 2.69 * 10^43)
This is the kind of math that is useful. Exploratory math that struggles with mathematical truths and practical implementations. Students should get a sense of the limits of computers, what they can handle and not.
And designing a good math interface for these problems can be quite the UI learning experience. There are so many ways to explore math.
Stop teaching dry math and start teaching programming math.
Linear algebra/vector algebra is the single most useful topic for programming I can imagine.
And yet, so many coders don't know linear algebra.
Which area of math isn't useful for computer science/programming? Certainly some areas are more useful than others, but I think rather than looking at areas it matters more how in depth you go in one area. Going super deep into an area is often not a lot more useful than just knowing the basics. Complexity theory is useful, but it's not that practically useful to know deeply about all the complexity classes.
I wrote the original question. I've always been interested in how much math various careers use, but I wrote this question the way I did in a shameless attempt to drive traffic to the site by appealing to the Stackoverflow and reddit communities. Everyone has given me a different answer so far, but that's to be expected, because there are ~1000 subcategories of computer programmers.
> I've always been interested in how much math various careers use
> ... there are ~1000 subcategories of computer programmers.
I'm curious: what about other careers? Are there fewer categories? Do they all do the same type of math? etc.
> ... there are ~1000 subcategories of computer programmers.
I'm curious: what about other careers? Are there fewer categories? Do they all do the same type of math? etc.
What would be a good writeup for understanding term-rewriting? (My current background level: I understand most of what OP has listed in "actually useful" and "can run into", and "automata theory" from the third list.)
I wouldn't recommend it as being as important as the OP claims, but if you must: http://www21.in.tum.de/~nipkow/TRaAT/
Thanks!
Could you also recommend something on how symbolic computation works? I have used computer algebra systems like Mathematica for long; would like to understand how it works internally.
I currently understand some basics like DPLL, semantic first-order unification, methods of solving specific equation systems like linear systems, numerical differential equations, etc. I am missing at least how the "top-level" of symbolic computation works.
For example, from what I currently understand, first-order semantic unification can find "x = Cos[y]" from "Sin[x] = Sin[Cos[y]]", but cannot solve "Sin[x] = Cos[x]" for x, and cannot simplify "[(Sin[x])^2 + (Cos[x])^2] = 1" to True.
I am hoping to find something simpler than reading through SymPy source code. :-)
Could you also recommend something on how symbolic computation works? I have used computer algebra systems like Mathematica for long; would like to understand how it works internally.
I currently understand some basics like DPLL, semantic first-order unification, methods of solving specific equation systems like linear systems, numerical differential equations, etc. I am missing at least how the "top-level" of symbolic computation works.
For example, from what I currently understand, first-order semantic unification can find "x = Cos[y]" from "Sin[x] = Sin[Cos[y]]", but cannot solve "Sin[x] = Cos[x]" for x, and cannot simplify "[(Sin[x])^2 + (Cos[x])^2] = 1" to True.
I am hoping to find something simpler than reading through SymPy source code. :-)
Peter Norvig's PAIP book has a chapter devoted to Student, a computer algebra system. It's very didactic:
http://norvig.com/paip/student.lisp
http://norvig.com/paip/student.lisp
I went to an engineering University. Besides having a wide variety of math required (3 semesters of Calc, 1 semester of either stats or probability, 1 semester of either linear algebra or matrices), we also had to take 3 semesters of physics, and 2 of chemistry. Most of us (those not just looking for a piece of paper) went considerable deeper in at least one area.
No, you don't need to understand organic chemistry to write a CRUD app. But, you don't need university to write a CRUD app.
I think I received an excellent education that prepared me for about any job out there. And, I've done it. I've done cancer statistics for the NIH. I've worked in avionics and simulation. Well, blah blah, no one cares about my resume, I'll just say I couldn't have done any of it without the education I received. I haven't done financial quant stuff, as an example, but how could I without the math background? Or how could I program a controller in a factory without understanding PID (done that)? How can I get a piece of that neat drone project (done that)? Hey, that computer vision stuff looks interesting, all I need to know is ...derivatives, statistics (done that too).
For most of us, university is the last and/or best chance to really understand how the world works. For that you need quite a bit of math and science. Another example. We have a voluntary Arduino robotics workshop going on at work, coupled with 3D printing. Naturally, people are excited, and have all kinds of ideas. But, how do you execute on that if you don't understand how to design an op amp circuit, or filter data with something more sophisticated than a moving average? Robotics spans a number of fields, and to actually produce something more than a gimmick requires a lot of knowledge. Knowledge that you can pretty easily pick up in University, but knowledge you mostly just long for as you have to rush home at 5:30 to pick up the kids and make dinner.
I guess this is a cranky rant from an old guy. But I hear about University programs that are nothing more than Java voc ed systems and I despair. $100K in debt to learn something most anyone on here could just pick up on their own. You don't need university for that stuff.
No, you don't need to understand organic chemistry to write a CRUD app. But, you don't need university to write a CRUD app.
I think I received an excellent education that prepared me for about any job out there. And, I've done it. I've done cancer statistics for the NIH. I've worked in avionics and simulation. Well, blah blah, no one cares about my resume, I'll just say I couldn't have done any of it without the education I received. I haven't done financial quant stuff, as an example, but how could I without the math background? Or how could I program a controller in a factory without understanding PID (done that)? How can I get a piece of that neat drone project (done that)? Hey, that computer vision stuff looks interesting, all I need to know is ...derivatives, statistics (done that too).
For most of us, university is the last and/or best chance to really understand how the world works. For that you need quite a bit of math and science. Another example. We have a voluntary Arduino robotics workshop going on at work, coupled with 3D printing. Naturally, people are excited, and have all kinds of ideas. But, how do you execute on that if you don't understand how to design an op amp circuit, or filter data with something more sophisticated than a moving average? Robotics spans a number of fields, and to actually produce something more than a gimmick requires a lot of knowledge. Knowledge that you can pretty easily pick up in University, but knowledge you mostly just long for as you have to rush home at 5:30 to pick up the kids and make dinner.
I guess this is a cranky rant from an old guy. But I hear about University programs that are nothing more than Java voc ed systems and I despair. $100K in debt to learn something most anyone on here could just pick up on their own. You don't need university for that stuff.
> but how could I without the math background?
You could have just learned it as you went. Done that.
You could have just learned it as you went. Done that.
[deleted]
Even the top-voted response to the OP is obviously biased toward the logic flavor of computer science, with awkwardly scattered recommendations for non-logicish topics that are far more useful for all flavors of computer science ("perhaps even eigenvalues," seriously?!).
These lists even ignore the deeper question being asked: how do you figure out what sort of mathematics you need for the things you're interested in? Not all computer scientists (and programmers) like the same things in computer science and programming. It's much more advisable to figure out what you like before you go around trying to learn all the math there is to learn related to CS, and then ask about what math topics are related to that.