3
$\begingroup$

I am student of CS. Problem is, I feel that I don't have enough math knowledge to solve mathematical problems. When some programming problems arises which needs some math skills to solve then despite of the fact that I know how to code I can't solve it. For example, if I don't know the formula for area of circle, I can't find it no matter how good I am at coding.

Have a look at this problem from a programming competition, I did not know how to solve it until Tad posted that it was Assignment Problem and it can be solved with Hungarian Algorithm.After knowing Hungarian Algorithm it was pretty easy to solve. Now you can see problem is with my math skills. I am looking for some resources where I can find such ALL(if not ALL then MOST) algorithms which a programmer/software engineer is supposed to know.

$\endgroup$
  • 1
    $\begingroup$ Math courses are usually part of the CS program, at most universities. Doesn't your faculty offer any such courses? Perhaps you can take some basic courses at the math department. There is no one resource for "all math", and more importantly - it's not just about reading the material, it's about practicing and understanding it. $\endgroup$ – Shaull May 18 '15 at 5:23
  • $\begingroup$ Well they did but not for this kind of problem. And these are problems which appear in programming contests hence it becomes my nightmare. @Shaull $\endgroup$ – user4904589 May 18 '15 at 5:26
6
$\begingroup$

I find it surprising and unfortunate that you didn't get to study algorithms and discrete math more in your university studies. As you seem to have realized, a person can know how to code, but without math, won't be able to solve really interesting problems.

Unfortunately there is no "Learn all algorithms you'll ever need in 21 days for dummies" book. There are hundreds, possibly thousands, of algorithms—even more if you also consider data structures—and it just isn't possible for anyone to know them all. There are no shortcuts to algorithms and math, something which has frustrated me numerous times too. All you can do is throw yourself in and let the knowledge slowly build up.

I would recommend getting yourself a good book on algorithms—my choice would probably be Steve Skiena's The Algorithm Design Manual since it assumes less math background than the more popular Introduction to Algorithms—and a good book on discrete math, of which there are several. I've heard good reviews of Concrete Mathematics but haven't read it as it's a little pricey. Sometimes books use the term "discrete math" in confusing ways; make sure the one you get covers at least graph theory, recurrence relations, Boolean algebra, basic set theory, basic combinatorics, and basic probablity, as those are the most vital topics for a software developer. A book on statistics and probablity, like this one, freely available online and written by a professor from my university, wouldn't go amiss either. And both linear algebra and abstract algebra are useful surprisingly often; I like Gilbert Strang's Linear Algebra and its Applications and Charles Pinter's A Book of Abstract Algebra for these topics.

Of course, just buying these books isn't enough, even if you then proceed to read them. Doing every exercise is a decent start, though probably too dry. I would do exercises until I had drilled down the basics. To really get into these topics, you have to work on problems that use them, which aren't really as hard to find as they might seem. A simple spell checker might calculate Levenshtein distance to suggest corrections for a misspelled word, which allows you to practice dynamic programming. Games and simulations have all sorts of uses for graph algorithms; I implemented the Floyd-Warshall Algorithm in Javascript for a game once, and Dijkstra's Shortest Path algorithm and A* are widely used in games. Project Euler is a great source for number theoretic and combinatorial algorithms. Also make sure not to neglect data structures; try solving some problems that revolve around sets or maps in a lower level language (C, C++, or Java) and implementing your own skip list or red-black tree or hash set. Although these data structures are often available in libraries, the concepts you learn by implementing them are widely applicable (e.g. I never would have understood the Rabin-Karp Algorithm without knowing about hash tables, because it uses hashing, in addition to number theory).

The great thing about this is that not only will you learn algorithms, you'll also get better at coding, and get more familiar with your chosen programming language, by being forced to solve unfamiliar problems. If there's some feature of your language that you've always wanted to use and never been able to, these kinds of exercises are a great way to do that too; I first really dug into Java generics while working on a problem about binary trees.

Finally, just remember that you don't have to know every algorithm off the top of your head. The Hungarian Algorithm in the question you linked is a special purpose algorithm for linear algebra. It's not something most programmers ever have to deal with. Contests do not reflect reality in that way. A contest might expect you to have memorized obscure algorithms and be able to implement them from scratch without any references in a short period of time. When you encounter problems in the wild, it's much more vital that you can clearly state the problem, identify what kind of technique or approach might be helpful, and do research to find something that can solve your problem. In my opinion, it's much more important to look at a problem about matrices, be able to think "This problem is about matrices. I should look at some linear algebra algorithms. Those are probably in a book about numerical algorithms", and then be able to find the Hungarian Algorithm and implement it, than it is to memorize that algorithm and be able to code it off the top of your head.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.