4 ms·

> Most areas of CS you do are unlikely to need advanced calculus or topics that depend on it (differential equations, topology, measure theory...). Right. The

> Most areas of CS you do are unlikely to need advanced calculus or topics that depend on it (differential equations, topology, measure theory...). Right. The only advanced calculus text I listed was 'Baby Rudin', and the main contribution there is just to get some of the more important properties of the real numbers, Euclidean n-space, infinite sequences and series, and Riemann integration solid. If a CS student is to stop before these topics, okay, but if they are going to go on then these topics will be part of what is generally assumed. For CS, as we know, it is doing what EE did -- moving beyond its core tools and into what to do with those tools. E.g., EE got into nonlinear filtering and stochastic integration. E.g., CS is now getting into both optimization and statistics. Then being handy with that Baby Rudin material, at least the early chapters, will get to be important. With Baby Rudin already done, there can be a good course in differential equations, and such a course can be a good way to see some of the value of what did in linear algebra and Baby Rudin and to exercise that material. At some point in the future, a CS guy might well get into some work involving differential equations -- viral growth models, flight of airplanes and space vehicles, and much of mechanical engineering. One of the main themes in the future of computer applications is handling 'randomness', and my view is that serious work in that direction should have the measure theory foundations. I did an A/B on that! Early in my career I tried the easy way. After measure theory, Neveu, Breiman, Loeve, Dynkin, Lipster, Shiryaev, etc., I concluded that the measure theory approach to probability, stochastic processes, and statistics was essential. In particular, without measure theory, people too easily get totally stuck in the mud on what 'random' means, while with measure theory Kolmogorov has a really nice answer. My view is that people may not like Kolmogorov's answer but that, with some really simple assumptions, we get forced into that answer anyway! For the rest, the Hilbert and Banach spaces won't go away! E.g., a huge dessert buffet of really finger lick'n good applications of the Hahn-Banach theorem is David G. Luenberger, 'Optimization by Vector Space Methods', and that book will be a nice source of methods for a lot that computing people might encounter. > You left out graph theory and combinatorics, both of which are extremely important to CS. For combinatorics, I assumed that one would get enough, in some ways deeper than in Knuth's TACP, from abstract algebra and elementary probability. E.g., combinatorics is a lot about counting, and so is group theory in abstract algebra. For graph theory, I assumed that one would get enough from optimization on networks. E.g., a 'basis' in the network simplex method on a network is a minimum spanning tree! And the max flow/min cut theorem can follow just from linear programming. Dynamic programming, which I mentioned, can be viewed as graph theory. I did mention linear programming (and so does CLRS), and one reason is that in the CS study of algorithms the algorithms for linear programming are important, and surprising, benchmarks. Also integer linear programming is one of the more important motivations for the question of P versus NP. For some of the surprise, the simplex algorithm has low degree polynomial expected performance (K. Borgward) but exponential worst case performance (Klee and Minty), but the polynomial algorithms (Khachiyan) when they are faster than simplex have both of them too slow for practice! So, at one of the first places we looked at computational complexity for problems more challenging than, say, heap sort and AVL trees, an exponential algorithm turned out to be superior in nearly every sense of interest to a polynomial algorithm! There never was a guarantee that the study of computational complexity would be easy! But there's a lot of overlap: I didn't mention courses in 'finite mathematics', combinatorics, or graph theory, but one way and another what I described should provide enough coverage. I didn't mention the CS book CLRS, but I mentioned good coverage of some of the more advanced topics in that book. Or, there is a lot of blending old wine and pouring it into new bottles. There is a broad point: A major theme in CS now is to borrow, modify, and apply work done some years ago in applied math, especially from operations research, e.g., linear programming, flows on networks, stochastic point processes, and statistics. While CS has some new applications, typically the material is done more carefully in the old applied math sources. So, I emphasized learning the material as math instead of as CS. Besides, the OP was asking about math for CS and not 'mathematical CS'! Also the title asked for the "hard way"! There's another broad point: What to learn and why to learn it? Just a first cut view of what O( n ln(n) ) means should take only a little searching on the Internet. Besides, Knuth's TACP is quite clear on such 'asymptotics'. I wish Microsoft's MSDN documentation of .NET was as clear and easy to read as TACP! One reason not to learn this stuff is to confirm that Knuth, Sedgewick, CLRS, etc. were correct after all! Generally the reason to learn such stuff is for new applications in the future. For that, my view was just to stay with a relatively traditional course in relatively applied math although I leaned away from classic mathematical physics and more to business applications.

btilly 14y ago
Meh. If you want to learn hard math to make it harder, and to give you background for stuff you might encounter, why not go whole hog? Go ahead, learn algebraic topology so that you can understand category theory properly, then when you encounter it in CS you'll know what people are talking about. I think there is a point of diminishing returns. Baby Rudin I'm dubious about. But Royden and big Rudin (both of which you recommended) I have certainty about. There are good reasons that I never saw CS students in my real analysis classes. I don't think it is particularly valuable for CS either then or now, to acquire a deep understanding of real analysis. And yes, I know about measure theory. I know how it applies to probability. But I went the other way. I learned measure theory. Then I learned probability. Then I began having to do probability stuff in the real world. And not once has my measure theory background been particularly relevant. As for Hilbert and Banach spaces, they are key pieces of mathematics. In fields from wavelets to optimization theory, they come up over and over again. But I would wager that most computer science professors do not need to know what Hilbert and Banach spaces are. I'd even bet that most have not heard of the Hahn-Banach theorem. Again, if you find yourself going that way, learn it later. On combinatorics and graph theory, you claim that people will learn enough of that material elsewhere. Maybe, maybe not. But it is clear that programming problems routinely get turned into graph theory problems, many of the most important programming algorithms are about graph theory (start with the traveling salesman problem and work your way through the list of NP-complete problems), and at its heart, analyzing an algorithm's run-time is a combinatorics problem. Acquiring the necessary concepts and vocabulary for those is necessary, whether you classify the book you're learning from as a math text or a CS text.
- ten_fingers 14y ago
  > I think there is a point of diminishing returns. Yes, there is a big question about what to learn, about how much to invest in such things. > Baby Rudin I'm dubious about. But Royden and big Rudin (both of which you recommended) I have certainty about. But Baby Rudin is a prerequisite to Royden and big Rudin. I'm sorry, but probability, stochastic processes, and mathematical statistics were junk for me until I went at them via measure theory. I floundered terribly with random variables until I saw the measure theory definition; it's terrific: Go take 10,000 measurements. Now have the values of 10,000 random variables. Any 10,000 measurements at all. So far, no concept of 'randomness' at all. So, random variables are very general things and, e.g., handle even deterministic processes as a special case. E.g., sufficient statistics is just an application of the Radon-Nikodym theorem, and a total train wreck to do otherwise. Yes, order statistics are always sufficient, maybe nice to know in 'data mining'. That sample mean and sample variance are sufficient in the Gaussian case is mind blowing; nice opportunity for 'data compression'! E.g., measure theory and the Radon-Nikodym theorem define conditional expectation, that is, under mild assumptions, E[Y|X] = f(X) for some measurable f. Then easily f(X) is the best non-linear least squares approximation of Y. Nice. Further, if 'cross tabulate' Y on X, then have a discrete approximation to E[Y|X] which shows that cross tabulation is a discrete version of the best non-linear approximation of Y given X. Measure theory permits working with all the forms of convergence of random variables, especially strong convergence, at least awkward to do otherwise. Then martingale theory makes little sense without measure theory. Measure theory, the Kolmogorov extension, shows that we really can have a collection of random variables with desired properties. Measure theory is crucial in even defining E[Y|U(t), t <- a] since we are conditioning on an uncountably infinite collection of random variables. Measure theory, then, shows that we can replace U(t), t <= a by the sigma algebra they generate and, then, condition on the sigma algebra. Cute. Constructions such as E[Y|U(t), t <= a] are crucial in the nice qualitative, axiomatic definition of the Poisson process. Similarly for independence of two collections of random variables where each collection has uncountably infinitely many random variables. Measure theory was crucial in the standard results of ergodic theory. I wrote a paper on anomaly detection in server farms and networks, and the key idea in the paper was a finite group of measure preserving transformations lifted roughly from ergodic theory. Via measure theory we can show that the space of real valued L^2 random variables is complete, and, thus, a Hilbert space, which continues to blow my mind that any such thing could be true. I'd also like to have locally compact, but that's a bit much to hope for! The Doob decomposition shows that every stochastic process is the sum of a martingale and a predictable process, all measure theory! It's tough enough to believe in probability with the measure theory foundations; otherwise, I couldn't swallow the stuff! There is a broad point: Maybe OP wants to know what to learn for the applications of the future. Then what current CS profs know is not necessarily very relevant!

btilly 14y ago

Meh. If you want to learn hard math to make it harder, and to give you background for stuff you might encounter, why not go whole hog? Go ahead, learn algebraic topology so that you can understand category theory properly, then when you encounter it in CS you'll know what people are talking about. I think there is a point of diminishing returns. Baby Rudin I'm dubious about. But Royden and big Rudin (both of which you recommended) I have certainty about. There are good reasons that I never saw CS students in my real analysis classes. I don't think it is particularly valuable for CS either then or now, to acquire a deep understanding of real analysis. And yes, I know about measure theory. I know how it applies to probability. But I went the other way. I learned measure theory. Then I learned probability. Then I began having to do probability stuff in the real world. And not once has my measure theory background been particularly relevant. As for Hilbert and Banach spaces, they are key pieces of mathematics. In fields from wavelets to optimization theory, they come up over and over again. But I would wager that most computer science professors do not need to know what Hilbert and Banach spaces are. I'd even bet that most have not heard of the Hahn-Banach theorem. Again, if you find yourself going that way, learn it later. On combinatorics and graph theory, you claim that people will learn enough of that material elsewhere. Maybe, maybe not. But it is clear that programming problems routinely get turned into graph theory problems, many of the most important programming algorithms are about graph theory (start with the traveling salesman problem and work your way through the list of NP-complete problems), and at its heart, analyzing an algorithm's run-time is a combinatorics problem. Acquiring the necessary concepts and vocabulary for those is necessary, whether you classify the book you're learning from as a math text or a CS text.

ten_fingers 14y ago
> I think there is a point of diminishing returns. Yes, there is a big question about what to learn, about how much to invest in such things. > Baby Rudin I'm dubious about. But Royden and big Rudin (both of which you recommended) I have certainty about. But Baby Rudin is a prerequisite to Royden and big Rudin. I'm sorry, but probability, stochastic processes, and mathematical statistics were junk for me until I went at them via measure theory. I floundered terribly with random variables until I saw the measure theory definition; it's terrific: Go take 10,000 measurements. Now have the values of 10,000 random variables. Any 10,000 measurements at all. So far, no concept of 'randomness' at all. So, random variables are very general things and, e.g., handle even deterministic processes as a special case. E.g., sufficient statistics is just an application of the Radon-Nikodym theorem, and a total train wreck to do otherwise. Yes, order statistics are always sufficient, maybe nice to know in 'data mining'. That sample mean and sample variance are sufficient in the Gaussian case is mind blowing; nice opportunity for 'data compression'! E.g., measure theory and the Radon-Nikodym theorem define conditional expectation, that is, under mild assumptions, E[Y|X] = f(X) for some measurable f. Then easily f(X) is the best non-linear least squares approximation of Y. Nice. Further, if 'cross tabulate' Y on X, then have a discrete approximation to E[Y|X] which shows that cross tabulation is a discrete version of the best non-linear approximation of Y given X. Measure theory permits working with all the forms of convergence of random variables, especially strong convergence, at least awkward to do otherwise. Then martingale theory makes little sense without measure theory. Measure theory, the Kolmogorov extension, shows that we really can have a collection of random variables with desired properties. Measure theory is crucial in even defining E[Y|U(t), t <- a] since we are conditioning on an uncountably infinite collection of random variables. Measure theory, then, shows that we can replace U(t), t <= a by the sigma algebra they generate and, then, condition on the sigma algebra. Cute. Constructions such as E[Y|U(t), t <= a] are crucial in the nice qualitative, axiomatic definition of the Poisson process. Similarly for independence of two collections of random variables where each collection has uncountably infinitely many random variables. Measure theory was crucial in the standard results of ergodic theory. I wrote a paper on anomaly detection in server farms and networks, and the key idea in the paper was a finite group of measure preserving transformations lifted roughly from ergodic theory. Via measure theory we can show that the space of real valued L^2 random variables is complete, and, thus, a Hilbert space, which continues to blow my mind that any such thing could be true. I'd also like to have locally compact, but that's a bit much to hope for! The Doob decomposition shows that every stochastic process is the sum of a martingale and a predictable process, all measure theory! It's tough enough to believe in probability with the measure theory foundations; otherwise, I couldn't swallow the stuff! There is a broad point: Maybe OP wants to know what to learn for the applications of the future. Then what current CS profs know is not necessarily very relevant!