Mathematics for Computer Science Students
[+44] [14] Mike B
[2008-09-29 23:14:19]
[ math computer-science education ]
[ http://stackoverflow.com/questions/151147/mathematics-for-computer-science-students ] [DELETED]

To cut a long story short, I am a CS student that has received no formal Post-16 Maths education for years. Right now even my Algebra is extremely rusty and I have a couple of months to shape up my skills. I've got a couple of video lectures in my bookmarks, consisting of:

My aim as of today is to be able to read the CLRS book Introduction to Algorithms and be able to follow the Mathematical notation in that, as well as being able to confidently read and back-up any arguments written in Mathematical notation.

Aside from these video lectures, can anyone recommend any good books to help teach someone wishing to go from a low-foundation level to a more advanced level of Mathematics?

Just as a note, I've taken a first-year module in Analytical Modelling, so I understand some of the basic concepts of Discrete Mathematics.

EDIT: Just a note to those that are looking to learn Linear Algebra using the Video Lectures I have posted up. Peteris Krumins' Blog contains a r un-through of these lecture notes [7] as well as his own commentary and lecture notes, an invaluable resource for those looking to follow the lectures too.

[+27] [2008-09-29 23:24:26] TimB

Concrete Mathematics: A Foundation for Computer Science [1] is a fairly well-known book that might help -- Donald Knuth is one of the authors.

(2) The book is both fantastic, and fantastically challenging. You should be able to get through it with dedicated study, but it's not easy. One of the most rewarding books I've read (although not done all the questions!) - HenryR
Great book -- but insanely hard! You will almost certainly need external help with most of those exercises. - Alex Budovski
1
[+9] [2008-09-29 23:25:40] Jason Baker

Well, there's always the canonical Discrete math text [1]. I think being able to advance your discrete math skills past the basics will probably be the biggest help in getting through algorithms.

(1) I've had Rosen for all my CS Math classes, and I must say it's good. - Flame
I'm currently reading this book, it's awesome ! - Attilah
2
[+8] [2008-09-29 23:51:23] HenryR [ACCEPTED]

What's missing in your list is I think one of the most fundamental topics: probability (although statistics will have some overlap).

If you want to follow CLRS, you need to understand how probability works. For example the proof of Quicksort's average case behaviour requires an expectation argument that isn't too hard, but might throw you if you don't understand it.

This [1] book by Mitzenmacher and Upfal is my favourite probability introduction. It's not easy, but it's very readable and gives a proper feel for applications as well as theory.

You can leave differential equations for a while as they're not tremendously vital for the areas you're looking at.

Discrete mathematics is the all important, catch-all topic. Know some basic combinatorics: formulae for n choose k, permutations etc. Make sure you understand what a relation is. Basic set theory is important, and you should know what someone means when they say "Consider a graph G=(V,E)". Any introductory text will get you to those levels, but if you really want to say you've nailed it the hard (and perhaps most rewarding) way, get cracking on Concrete Mathematics [2].

You should also know a little number theory, just enough to be dangerous. This is again important for some stuff in CLRS. If you know a little something about prime numbers, and modulo arithmetic you're probably good to go, but keep a reference nearby when you meet a proof step you're not expecting.

3
[+3] [2008-09-29 23:31:52] Vincent McNabb

I've found Discrete Mathematics for Computing [1] by Peter Grossman to be quite helpful. It's basically an introduction to different parts of CS maths. It includes chapters on algorithms, number bases, computer arithmetic (at the binary level), logic, sets, induction & recursion, boolean algebra, graph theory, and trees. A really wide range of material, with exercises.

4
[+3] [2009-04-17 16:45:14] mandaleeka

In your list of topics, I think some are definitely more important than others. Certainly, this depends on the industry you go into, but I've reordered and modified your list based on priority:

(highest priority)

• Boolean Algebra (Boolean logic, gates, state machines, etc.)
• Discrete Mathematics
• Probability and Basic Statistics
• Linear Algebra
• Pre-Calculus Algebra
• Calculus
• Differential Equations

(lowest priority)

And, other than all of these formally defined fields, please, PLEASE be able to do basic math in your head. It bothers me to no end when I see programmers around me not be able to convert 101 from binary to decimal without calc.exe.

+1 for requesting basic computations in your head. (Although I wouldn't call them “math” really … :-)) - Christopher Creutzig
5
[+3] [2009-05-25 22:48:37] Zoli

Robert Breezer: "A First Course in Linear Algebra " The first hit with Google.

Not only free as free beer, but also free as in freedom. Very good both for total beginners and for advanced students. I have learned it through. I have never seen another math book with such good quality.

Here's the url: linear.pugetsound.edu - Brian Maltzan
6
[+2] [2008-09-29 23:24:16] Daniel F. Hanson

If you've only got a couple months to catch up on your math skills, unless you're inherently sharp at math, you'll find it extremely difficult to catch up. I would strongly recommend focusing on a few core areas and not worrying about the higher level math subjects. In particular, pre-calc algebra, discrete math, and statistics are the areas you'll want to concentrate on, and probably some basic geometry and trig, too. Calculus is a nice-to-have if you can squeeze it in, but differential equations is a little overboard, in my opinion. I would also consider linear algebra to be fluff as well, unless you plan on going into computer graphics.

This is all just my opinion, of course.

7
[+1] [2008-09-29 23:31:19] kjensen

You should look into logic. To be able to model and reason about complex systems is invaluable. (Yeah, yeah - I took the line from the cover of the book)

8
[+1] [2008-09-29 23:40:29] Maitus

Do not try to shortcut your math education! My experience has been that the highest level math classes still rely on very solid algebra skills.

Look at the first math class your curriculum requires and make sure you understand the final from the prereq courses.

9
[+1] [2008-09-29 23:53:05] dlamblin

I can't say I read the whole book, but this one seemed comfortably comprehensive while thankfully brief and direct with a focus on mathematics for the science and engineering student.

And I actually studied in an American curriculum so yes, it translates just fine.

Here are the sections I wish my high school (and first year of undergrad CS) had actually taught me as well as this book did:

7) Binomial series and proof by induction;

8) Differentiation;

9) Integration;

10) Complex numbers;

11) Working with vectors.

that numbering should go from 7 through to 11. Markdown's messing with me.

[1] http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=9780521017077

That book is currently on my shelf and I have to say that I've found it to be very bloated. Despite that, it's very solid, but not really what I'm looking for. - Mike B
Well my choices were sort of limited by the couple of months limitation. Most material is gears at you spending 1/2 a year on each subject, and thus more bloated still. - dlamblin
10
[+1] [2008-09-30 00:04:18] Ray Vega

Check out similar asked question: Useful math for programmers [1]

[1] http://stackoverflow.com/questions/11743/useful-math-for-programmers

11
[+1] [2009-04-17 16:26:16] Amit

You might want to get your hands on " What is Mathematics? [1]

12
[0] [2008-09-29 23:37:06] Jared Updike

I took a Discrete Math class with a text by Biggs. Discrete Math is your programming friend.

13
[0] [2010-07-14 06:39:13] SDX2000

http://www.cs.princeton.edu/courses/archive/spring10/cos433/mathcs.pdf

I have not read this book in it's entirety but it looks very promising.

14