What Math topics & resources to consider as beginner to indulge the book - Introduction to Algorithms (CLRS)?

Question

I'm a programmer who's beginning to appreciate the knowledge & usability of Algorithms in my work as I move forward with my skill-set. I don't want to take the short path by learning how to apply algorithms "as-is" but would rather like to know the foundation and fundamentals behind them. For that I need Math, at which I'm pretty "basic". I'm considering getting tuition's for that.

What I would like is to have a concise syllabus/set of topics/book which I could hand over to my math tutor to get started.

HIGHLY DESIRED: one book. the silver bullet. (fingers crossed!)

PS: I've got some leads but want to hear you guys/gurus out: Discrete Math, Combinatorics, Graph theory, Calculus, Linear Algebra, and Number Theory.

Looking forward to your answers. Thanks!

Answer 1

PS: I've got some leads but want to hear you guys/gurus out: Discrete Math, Combinatorics, Graph theory, Calculus, Linear Algebra, and Number Theory.

Depends on what you want to do with it.

Number theory? I'd cross that off the list.

Calculus is a very big topic. It'd be very important if you wanted to do scientific computing; less so otherwise.

I'd add numerical methods to the list. "Numerical Recipes" is a book that I would say is good, but it has its detractors. You'll find a lot of these topics described within, with working code. The prose is excellent.

But it's not for beginners; it's not introductory.

HIGHLY DESIRED: one book. the silver bullet. (fingers crossed!)

You're going to be disappointed here, I'm afraid.

Answer 2

Discrete Math will be your most important topic.

I highly recommend Discrete Mathematics and Its Applications. It teaches you lots of relevant stuff to computers, such as number bases, probability, proofs, the list goes on. It actually is written to focus on providing examples that relate to computers and computation. At my college (Purdue), this book is used in the CS AND Math department, which I think is a vote of confidence.

As for graph theory, that's very important, but Introduction to Algorithms will more than take care of you on that subject.

Maybe also pick up Calc 1. It might not be directly applicable to your work, but it teaches you some different thought patterns and if you ever run into calculus notation (pretty common), you'll have more of an idea of what's going on. Other than that, the other maths are useful basically depending on what you want to do.

I found linear algebra to be interesting, but not really applicable to anything I've done. Though, I focus more on security than on scientific computing, where it might be more useful.

Answer 3

After following a lot of discussions on stackoverflow, I'd also add a basic primer in other problem solving techniques and algorithms beyond the scope of Corman's book. This would include linear, integer, and non-linear programming, constraint programming, queueing theory, simulation modeling, and the use of various search algorithms like genetic algorithms, simulated annealing, and tabu search. You won't necessarily find a book to cover ALL these subjects, but many programmers have only limited exposure to these concepts in school. A good course in probability and statistics couldn't hurt either. I agree that calculus and its followup, differential equations, won't be of much help. But a good course in linear algebra forms a foundation for alot of material in the study of algorithms and statistics. I'd recommend Strang as a start there.

Answer 4

I would like to advocate for linear algebra. When you run into a calculus, probability, or most other high level math problems, it is often obvious what type of math is required. With linear algebra, many problem have complex but rudimentary solutions using basic math. This leads to naive developers to construct overly complicated algorithms to solve trivial linear algebra problems.

I've seen really bad code that would have been much cleaner if the developer had basic understanding of vectors and linear algebra. In one of my computer graphics courses, the bulk of my classmates used lines and lines of trig functions to solve what was essentially an addition and subtraction problem.

My favorite example comes from an online tutorial, where the author normalized a vector by computing the angle between the x-axis, and computing the sin and cos of the angle.

Answer 5

CLRS states in the introduction the math prerequisites:

You should have some facility with proofs by mathematical induction. A few portions of the book rely on some knowledge of elementary calculus. Beyond that, Parts I and VIII of this book teach you all the mathematical techniques you will need.

The majority of it is in part eight.

The text also has a comprehensive bibliography. Here are some that come up repeatedly:

1. Even, Shimon. Graph Algorithms. Rockville, MD: Computer Science Press, 1979. ISBN: 0914894218.
2. Feller, William. An Introduction to Probability Theory and Its Applications. 3rd ed. 2 vols. New York, NY: John Wiley & Sons, 1968, 1971. ISBN: 0471257087. ISBN: 0471257095.
3. Lawler, Eugene L. Combinatorial Optimization: Networks and Matroids. New York, NY: Holt, Rinehart, and Winston, 1976. ISBN: 0030848660.
4. Liu, Chung L. Introduction to Combinatorial Mathematics. New York, NY: McGraw-Hill, 1968. ISBN: 0070381240.
5. Niven, Ivan, and Herbert S. Zuckerman. An Introduction to the Theory of Numbers. 4th ed. New York, NY: John Wiley & Sons, 1980. ISBN: 0471028517.

Answer 6

At MIT, students are required to take Mathematics for Computer Science before taking Intro to Algorithms which uses CLRS. The lecture notes (PDF) from the Math class are pretty good and self-contained.

Answer 7

I doubt just one, single book would satisfy all your needs. When it comes to number theory, I would recommend the book "Number Theory for Computing". I used it for some undergraduate courses and I like its style, not too complicated, but not "dumbed down" either.