Books linking Problem Solving to Math Concepts (like discrete mathematics)?

Question

Hi! I'm a few years into my Computer Science Education, and I had to transfer to a new school in the between years. The problem I'm having is that the "intro" classes at my first school focused first on Mostly professional programming skills, like problem design, and put the mathematics concepts in later courses, and when I transferred, it's completely opposite at my new school!

So I'm missing a big foundation for problem solving in good algorithm design! I have plenty of math classes and plenty of experience programming and programming concepts, but nothing really to link the two (I.E. barely any discrete mathematics classes).

Are there any books you would recommend to someone who's essentially had plenty of actual programming experience, but little to no experience in design concepts and mathematics?

EDIT: I saw the discrete mathematics recommendations, what i meant is that I've taken most mathematics courses, such as calculus, linear algebra, discrete mathematics, it just feels like I'm missing something integral between relating these concepts with algorithm design and implementation. Does anyone know of a book that relates the two similar yet different fields?

Answer 1

I recommend you start with books on the following topics:

1. Digital Systems
2. Discrete Maths
3. Linear Algebra
4. Calculus
5. Probability

Then start reading data-structures and algorithm books, then more advanced topics like operating systems, parallel and distributed programming.

Try searching (in this site for instance) for good books on each topic.

Answer 2

Based on your edit, it looks like you've got the math courses you need (though you may want to take one on numerical methods). You imply (though it's not explicitly stated) that you've had coursework on data structures. What you seem to be missing are the computer science theory courses that you probably would have gotten later in your first school that you've apparently missed in the second. Topics that you should look into are:

Computational Theory: This covers topics like finite state machines, formal grammars and Turing machines. There are a number of books on the subject. As an undergrad I used the first edition of Lewis and Papditriou and Brookshear at the graduate level. Both are reasonable for under grad work, though. Most software development activities are probably not going to require much of this with the largest exception being compiler design and implementation. Still I personally think it's important foundation to have in any computer science education.

Analysis of Algorithms: This topic is primarily concerned with determining the asymptotic time and space performance of algorithms which helps you to understand which algorithms may be suitable for a particular purpose and gives you the tools you need to assess the theoretical performance of algorithms that you design or implement. The current standard text for this is probably Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein though your school may differ. This content will have very wide applicability to software development.

Computational Complexity: There's an overlap that you'll see in both of the areas above in this. This classifies certain types of problem domains based upon the time and space requirements for solving elements of those domains (perhaps you've seen P = NP question pop up every now and again). Any book on computational theory or analysis of algorithms will cover computational complexity, so the references above should suffice for this as well.

As an aside, I think as soon as your advisor notes the discrepency in your classwork, you're probably going to end up taking these courses before being able to graduate. You probably want to bring this up at your earliest opportunity so as not to encounter any problems closer to graduation.

Good luck.

Answer 3

The majority of the math classes you've taken sound (at least to me) computational; that is, here is a formula/integral/relation/etc., solve it and give me an answer. The majority of mathematics involves logic and explanation more than straight calculation; it requires delving into what things mean as opposed to figuring out what the answer is. Working on developing the reasoning and logical side of mathematics might translate to being a better programmer.

A great book to check out is Smith's Transition to Advanced Mathematics. It's one of the first books I came across in my career that made math more about reasoning and explanations and less about number crunching and calculation, and used copies of the 5th edition (the one I own and heartily recommend) go for under $20 on Amazon. It'll probably make the heftier (though very important) tomes like the previous suggested Introduction to Algorithms easier to work through, because books like that often require a high level of mathematical maturity to tackle the concepts involved.

Good Luck!