Stats for nerds
5recommend
7mentions
6people
2011–2022years
86% recommend14% critical
Mentions per year
What Hacker News says
- Here are 3 applied math gems:
1) Nonlinear Dynamics and Chaos by Strogatz completely changed my relationship with applied math. I'd studied diffyqs and PDEs earlier but that was under duress and hasn't been particularly useful. Traditional books don't tell you that analysis solves only a tiny subset of important real-world problems, and for me, were just another boring dose of plug-and-chug calculus.
Strogatz immediately motivates the subject and uses analysis as a jumping-off point (with some pretty hard analytical HW problems!), but he quickly pivots to numerical methods with a very strong intuitive and visual/geometric approach. Years later, I'm using this knowledge surprisingly often.
https://www.amazon.com/Nonlinear-Dynamics-Student-Solutions-...
2) Linear Programming by Chvatal was the book that made LP duality really click for me. Prior to reading Chvatal I mechanically understood duality but with no intuition. Chvatal explains duality from a bounding perspective, and even better, motivates duality through simple dimensional analysis, just like in physics! (The Strogatz book above also motivates dimensional analysis and dimensionless groups, which has been very useful to me over the long term.)
https://www.amazon.com/Linear-Programming-University-Vasek-C...
3) Statistical Methods: The Geometric Approach, Saville and Wood was my bridge from meaningless opaque algebraic and calculus stats to a solid understanding. The book builds everything on vector space projections at the level of undergrad linear algebra. Even a simple mean of 3 numbers now sparkles with intuition and insight.
https://www.amazon.com/Statistical-Methods-Geometric-Approac...
They also published a short paper that conveys the key ideas https://www.jstor.org/stable/2684537
- In high school I read Vašek Chvátal - Linear Programming after buying it second hand for a few dollars thinking it was a computer text book.
I liked it at the time.
- the optimum is always at a vertex
As you point out in [2], it would be more correct to say that among the optimal solutions there is always one at a vertex of the polyhedron</nitpicking>
Also, simplex methods are very versatile when combined with other methods (see branch-and-bound for mixed integer linear optimization), but are sometimes easily beaten by barrier methods.
Excellent textbooks for LP: Chvátal [4] and Bertsimas and Tsitsiklis [5]. For mixed integer linear optimization: Wolsey [6], Nemhauser and Wolsey [7], and Conforti et al. [8].
[4] V. Chvátal, Linear Programming. MacMillan 1983.
[5] D. Bertsimas, J.N. Tsitsiklis. Introduction to linear optimization. Vol. 6. Belmont, MA: Athena Scientific, 1997.
[6] L.A. Wolsey (1998). Integer programming (Vol. 42). New York: Wiley.
[7] L.A. Wolsey, G.L. Nemhauser. Integer and combinatorial optimization. John Wiley & Sons; 2014 Aug 28.
[8] M. Conforti, G. Cornuéjols, G. Zambelli (2014). Integer programming (Vol. 271). Berlin: Springer.
- I'm glad there's more free material online for optimization modeling and algorithms. Personally, here's my favorite list for algorithms and modeling for optimization:
For learning the simplex method, Linear Programming by Vasek Chvatal (first 10 chapters): https://books.google.com/books?id=DN20_tW_BV0C&printsec=fron...
For learning branch and bound, Integer Programming by Laurence A. Wolsey https://books.google.com/books?id=x7RvQgAACAAJ
For odd modeling tricks for integer programming, Logic and Integer Programming by Williams, H. Paul https://www.springer.com/us/book/9780387922799
For modeling tricks for convex programming, Convex Optimization by Stephen Boyd and Lieven Vandenberghe https://stanford.edu/~boyd/cvxbook/
For basic nonlinear optimization algorithms, Numerical Optimization by Nocedal, Jorge, Wright, S. https://www.springer.com/us/book/9780387303031
I've never really found the ultimate optimization book, but the references above tend to have the right modeling techniques, algorithms, and references. I've found they're a good place to get the right idea and the right words to search for more material.
- Part II
(6) Background. A good way to win a 100 yard dash foot race is to start one foot from the finish line. Otherwise, get a head start. Or, get an 'unfair advantage'.
So, for the approach of 'mathematizing' engineering, start with a solid undergraduate degree in pure and applied math. Then get a Master's concentrating on selected topics in pure and applied math.
E.g., even if you want to get a Ph.D. in computer science, as an undergraduate, mostly just f'get about the undergraduate computer science courses and be a math major instead. The undergraduate computer science material won't much help you in computer science research, but the math can be an overwhelmingly strong advantage.
As a math major, after the usual undergraduate calculus sequence, take theorem proving courses in abstract algebra and linear algebra -- the first is useful at times, maybe more so in the future, and the easy place to learn to prove theorems, and the second is likely the most important material in mathematical analysis and applied math.
To continue, take a second course in linear algebra. A good start is the now classic P. Halmos, 'Finite Dimensional Vector Spaces'. It was written in 1942 when Halmos, a fresh Ph.D. from Doob at U. IL, was an assistant to von Neumann at the Institute in Princeton and is really a finite dimensional introduction to von Neumann's Hilbert space. For more, see the books by R. Bellman or R. Horn.
Work carefully through W. Rudin, 'Principles of Mathematical Analysis.' Supplement that with Fleming, 'Functions of Several Variables', Buck, 'Advanced Calculus', etc.
As a crucial start on optimization, work carefully through, say, Chvatal, 'Linear Programming'.
Somewhere get a good theorem proving course in ordinary differential equations; that can be a good start in a lot in applied math and on deterministic optimal control theory.
At one of the first chances, take a careful pass through Royden, 'Real Analysis' and the real half of Rudin, 'Real and Complex Analysis' -- a good course would help weight the more and less important ideas there.
Then a long dessert buffet is Luenberger, 'Optimization by Vector Space Techniques'.
With that background, you can do probability and stochastic processes the serious way via the more serious authors, e.g., L. Breiman, D. Brillinger, K. Chung, E. Cinlar, J. Doob, E. Dynkin, I. Karatzas, M. Loeve, J. Neveu, S. Shreve, and more.
For more, attend research seminars: Don't often try to follow much of the content but just use the seminars as suggestions for new fields, problems, techniques, names, references, etc. Also you may meet some people or learn about career opportunities that could be helpful.
If after a Bachelor's or Master's want to drop out of school for a while, then do so, get a job, stay single, and outside of work lead a simple life and study some more pure and applied math from some of the best sources. Hopefully get some practice applying math to real problems.
Get a collection of real problems that might use for your Ph.D. research (remember, your Ph.D. is to be in engineering). Make some first cut progress on those problems. If you can get some solutions, then write them up as papers. If some of your papers look publishable, then try to publish them.
(7) Ph.D. Program. Now apply to a Ph.D. program. Include your papers, especially the published ones.
Your mathematical background can be a huge advantage. In particular, consider working in optimization and stochastic processes with a solid background in measure theory and functional analysis. Heck, nearly everything going on in a big application, a server farm, a large network, ..., the economy is a stochastic process where we want to optimize.
Do what the department insists on, and otherwise continue your research. Take your best research and submit it as your Ph.D. dissertation. If there is any question about the quality of that research, then publish it; or just submit work that you have already published. That the work was accepted for publication in a good journal tends quickly to settle all doubts about sufficient quality.
In particular, proceeding in your Ph.D. program as outlined here, you have (A) obtained your own background in pure and applied math, not depended on your department for that background, and have quite likely obtained a better background than any of your professors; (B) have selected your own research problems and not depended on your department or its professors for research problems; (C) have done the core of your research in applied math with theorems and proofs which are comparatively easy to show are correct and difficult to criticize; and (D) have used publication of your work preemptively to establish a respected, outside, objective proof of quality.
(8) How to Do the Research. Mostly the mathematics is just math and not very intuitive and is solid and not just guessing. But finding that math, that is, original math, can use quite a lot of intuition and guessing for finding what might be true and finding ways to prove it is true.
My view is that the most important work in math research is intuitive with a lot of guessing, a lot of simple models, and a lot of simple, intuitive, testing of intuitive guesses.
(9) University. Generally you are better off at the best research university you can get into. The less good universities can force you to jump through no end of silly hoops and be so insecure in their own expertise as to delay and delay saying that your work is good.
(10) Courses. At a really good university, it may be that the graduate courses are not much like undergraduate courses and, instead, are essentially just introductions to narrow parts of research by experts in those parts and, really, intended only for students wishing to pursue research in those parts.
(11) Done.
Accept your Ph.D. and go do something else.
Your professors may have helped you get a job, if so likely an academic job; thank them, and if that job is what you want, then take it; else proceed with your career along lines you've had in mind.
(12) Warning.
A Ph.D. program can be dangerous, harmful to you and your life and career and even fatal. If you are not well protected with your own background in, say, math, your own research problems, your own research, and your own publications, and hopefully your own financial means, then your education and much of your life can be in the hands of others who can be clumsy, competitive, nasty, arrogant, domineering, abusive, destructive, sadistic, incompetent, etc.
It can be that, really, your professors don't have any good research problems for you. E.g., even in an engineering school, they may have nearly no contact with real problems from off campus and, thus, little or no help in finding a real problem for your start. Your background in each of real problems, math, computing, and business can easily be much better than theirs. Each of your professors may have been beating their head against some hard problem for the last 15 years while you have some good insight into some good, new problems you have a good chance of solving. It is accepted that one of the keys to success in research is good problem selection.
You can feel that you are in jail without being accused of a crime, with an indeterminate sentence, tortured by your professors as jailers, and with no chance of parole.
There is a special warning for students who made Valedictorian in high school and PBK, 'Summa Cum Laude', etc. in college. In the text version of D. Knuth's 'The TeXBook' is:
"The traditional way is to put off all creative aspects until the last part of graduate school. For seventeen or more years, a student is taught 'examsmanship', then suddenly after passing enough exams in graduate school he's told to do something original."
So, a student who has done really well based mostly on fantastic memory, pleasing the teachers, dotting i's and crossing t's, doing just what was requested, working desperately for praise and approval from others, terrified of any chance of criticism, out to 'change the world' in major ways or bust, can find themselves in a situation of inhuman stress, then depression, then incapacitation, then more stress, then clinical depression, then death. No joke.
- The article criticizes too soon. Here I explain this point, give some references where can get good explanations of the topics in the article, mention some more topics, and then explain what I believe is a more important guide to success in computing for the foreseeable future and, in particular, a low risk approach to very successful information technology startups. For this last, venture partners listen up.
Maybe the standard reference on design patterns is:
Most of the rest of what is mentioned in the article is in any of, say,o Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides, 'Design Patterns: Elements of Reusable Object-Oriented Software', ISBN 0-201-63361-2, Addison-Wesley, Reading, Massachusetts, 1995.
Two lectures of 90 minutes each are about enough to cover what the article has from the last three.o Donald E. Knuth, 'The Art of Computer Programming, Volume 3, Sorting and Searching', ISBN 0-201-03803-X, Addison-Wesley, Reading, Massachusetts, 1969. o Robert Sedgewick, Kevin Wayne, 'Algorithms, 4th Edition', ISBN-10: 032157351X, ISBN-13: 978-0321573513, Addison-Wesley, Reading, Massachusetts, 2011. o Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 'Introduction to Algorithms, Second Edition', The MIT Press Cambridge. Also known as CLRS. Sometimes can find this on the Internet as a PDF. Amazon currently sells the third edition from 2009.There's an ocean of more such stuff can stuff between ears.
E.g., once I needed something, worked it out, and later discovered I'd reinvented k-D trees. It's in Sedgewick. One project I was on made important use of extendible hashing as in
or inFagin, R.; Nievergelt, J.; Pippenger, N.; Strong, H. R. (September, 1979), "Extendible Hashing - A Fast Access Method for Dynamic Files", ACM Transactions on Database Systems 4 (3): 315–344, doi:10.1145/320083.320092
atExtendible hashing From Wikipedia, the free encyclopedia
In my current project, I needed to be able to read a list of, say, 10 million numbers and end up with the, say, 100 largest. To do that I borrowed the heap data structure from heap sort (in Knuth above).http://en.wikipedia.org/wiki/Extendible_hashingLater I heard that a standard Google interview question asks much the same.
So, since I got some extra mileage out of the heap data structure in heap sort, I would criticize the article for asking for quick sort but not also heap sort: For sorting n items, heap sort is guaranteed to run in time proportional to (n)ln(n), but the corresponding expression for quick sort is n^2 (the guarantee including worst case) -- a bummer. Yes, usually in practice quick sort is significantly faster than heap sort.
There's too much of such stuff to carry it all around between one pair of ears. So, get an overview and use books such as above as references. Each of those algorithms takes only about an hour to understand and an hour to program. So, just wait until need such an algorithm.
Alas, CLRS tries to cover the simplex algorithm of linear programming, and my view that they botch the effort. Good coverage of linear programming takes more than an hour, but there are several good texts, e.g.,
But I believe that the article's author is missing a still bigger point: He is implicitly assuming that for writing a program, it is sufficient (1) to look at the real problem and (2) use knowledge of programming languages and algorithms to write the software. For problems we understand well enough how to do in principle essentially manually, sure. Otherwise, heavily not.Vasek Chvatal, 'Linear Programming', ISBN 0-7167-1587-2, W. H. Freeman, New York, 1983.Here's an example (which we will generalize below): Write software to say how to feed update information to the control of the trajectory of a spacecraft touring the outer planets with, also, the ability to fly between Saturn and its inner most ring.
For this will also need to know (1) Newton's second law of motion, (2) Newton's law of gravity, and (3) how to setup and solve numerically with sufficient accuracy the resulting initial value problems for some nonlinear ordinary differential equations. So, need some physics, differential equations, and numerical analysis.
Note the 'pattern' that is going on here: (1) We start with the real problem, finding updates to the control of the trajectory of the spacecraft, (2) convert that real problem to a mathematical problem, (3) get a mathematical solution to the mathematical problem (e.g., with theorems and proofs from differential equations and numerical analysis), (4) program the mathematical solution.
So, we do not try to go directly from the real problem to a real solution and, instead, take a side detour from the real problem, into some mathematics, into some software, and then back to the real problem.
I claim that this 'pattern' will be of greatly increasing importance and value for computing starting now and for the foreseeable future. That is, we need ways to connect from the real problem to the real solution more powerful than just what we used to do manually or what we might do intuitively, with heuristics, genetic programming, 'machine learning', artificial intelligence, etc.
For an application of this pattern to information technology startups:
(1) Problem. Pick a "big ass" problem, one, say, 1+ Internet users in the US and around the world want solved. Pick a problem where for those users the first good or a much better solution will be a 'must have' instead of just a 'nice to have'.
The example from biomedical technology would be a safe, effective, cheap, patentable one pill cure for any cancer.
Note: Now with such a "big ass" problem we have a good shot at being able to f'get about subtle issues of UI/UX and 'product/market' fit. So, here we reduce 'market' risk.
(2) Do a faithful conversion of this problem into a precisely stated mathematical problem. The math involved might be original with advanced prerequisites. This conversion is usually from challenging to impossible. If cannot make this conversion, then return to (1) and pick another problem. Else continue.
(3) Solution. Find a mathematical solution to the mathematical problem. Want the solution to result, for the real problem, in the first good one or a much better one than anything else. The math involved might be original with advanced prerequisites. Finding this solution is usually from challenging to impossible. If cannot find such a solution, then return to (1) and pick another "big ass" problem. Else continue.
Note: A mathematical solution to a precisely stated mathematical problem is usually easy to check (follow theorems and proofs) with high reliability. So, if we have such a solution that checks, we have lowered project risk.
(4) Computing. Convert the mathematical solution to software to do the data manipulations. This work might be regarded as resulting in an 'algorithm' for the problem, but an 'algorithm' is just some code to do something, and without the mathematics such code has next to nothing to recommend it. So, we don't really want just an 'algorithm'; instead we want something logically solid from some mathematics.
The computing involved might be original with advanced prerequisites. This conversion is commonly from challenging to impossible. If cannot make this conversion, then return to (1) and pick another problem. Else continue.
(5) Deployment. Deploy the software, go live (say, on the Internet), get publicity, users, maybe ads, and revenue.
Note: Starting at step (1), this sequence has high risk. But given success through step (4), due to the big ass problem and the good or much better solution, step (5) has low risk.
So, if we can get through step (4), then we are GO for a valuable solution to a big ass problem, a solution 1+ billion people regard as a "must have" and not just a "nice to have", get to f'get about subtle issues of UI/UX and 'product/market fit' or a 'lean' development process with lots of feedback from the market and revisions of the work.
My view is that this sequence of (1)-(5) will grow rapidly in importance for computing and startups for the foreseeable future. In this case, the key is not some computing skills, classic algorithms, or computer science but some mathematics. possibly new with advanced prerequisites.
So, net my view is that for the future of computing the crucial academic material is from departments of mathematics instead of departments of computer science.
To be more clear, the advantage of the 'detour' into mathematics is get a solid, low risk 'logical chain' from the real problem to the computing and the real solution. That's part of what we want, right?
The only thing that surprises me about this sequence of (1)-(5) is that it has long been so standard in applications of applied mathematics, physical science, and engineering to the solution of important real problems but seems to be totally missing or nearly so from current venture funded information technology startups.
Related
Introduction to Linear Optimization
3 recommend · 4
Integer and combinatorial optimization
2 recommend · 8
The art and theory of dynamic programming
1 recommend · 10
Optimization by Vector Space Methods
7 recommend · 24
Numerical Optimization
6 recommend · 12
Introduction to Algorithms
274 recommend · 880
