Hacker News new | past | comments | ask | show | jobs | submit login
Mathematics for Computer Science (mit.edu)
395 points by moks on Apr 2, 2015 | hide | past | web | favorite | 48 comments

Oh man. This course brings back so many memories of suffering through this material. But I can't emphasize how important this stuff is to know if you want to know anything significant in Computer Science.

What helped me ace the the exam was doing a hundreds of problems. I couldn't answer them most of the time, so I'd need an answer key nearby to get unstuck.

Drill, drill, drill. Just like you'd expect to drill for calculus, you can drill for this class.

What I found helpful was Rosen's "Discrete Mathematics and Its Applications". The material wasn't the best, but the problems are excellent. You can buy an older edition of the book and its solution manual for next to nothing on used book sites like abebooks.com

> I couldn't answer them most of the time, so I'd need an answer key nearby to get unstuck.

This happens with a lot of books out there. It would have been great if the authors of MCS gave solutions for at least some select questions.

I know it's not related to this but if anyone has not watched the Linear Algebra lectures by Gilbert Strang of MIT. They are definitely worth a look as a strong foundation in Linear Algebra never hurt anyone. (http://web.mit.edu/18.06/www/videos.shtml)

Also available on iTunes U.

[Demo] There is also collection of Gilbert Strang lectures here: http://classmill.com/jennathompson/introduction-to-algebra - You'd have to login to watch the whole series, but lets you mark lectures as "done", ask questions, and track progress etc..

Thanks for the resource. I never really paid attention when I took linear algebra, and I've always regretted it since it seems to rear it's head everywhere.

I was the same way. I went through it thinking it was very abstract and had no real application. It wasn't until after that I realized it was basically used (in some way/shape/form) everywhere.

If some of you feel a bit overwhelmed with the material, you may be well served by watching the first few lecture's of the following playlist:


It is Carleton University's freshman/first year Discrete Structures/Math course (COMP1805). They cover a lot of the same material, but at a more leisure pace and assume a lot less background.

Looking over the second part of the MIT course, I see that a lot of the same material is covered in this free textbook.


The reading material is fantastic. If anyone wants a more recent version of it, here's the link:


That's not just "reading material" ... it's a frigging 1000-page book! :-D

It all started with a 300 page reading notes, which, in my opinion, is pretty long already, but, boy, 1000 pages is a lot indeed :).

Easier to search than the videos.

Indicator RVs are introduced on p738 & used all over the book. But on p788, he proves Markov without mentioning indicators. Typically, you create an indicator for the (R>=x) event, compute its expected value & voila Markov! Somewhat atypical.

Are there companion solutions for the problem sets available anywhere?

Seems like you need a MIT certificate.

That's unfortunate. Oh well...

Thanks for that link! It looks like it was just updated today.

I've been trying to self-study mathematics since around the new year. I initially tried following this course, but with only a background of high school math through precalculus I found this to be overwhelming.

So after a bit of research I decided to start working my way through "How to Prove It" by Velleman, which has introduced me to many of the concepts that seem to be pre-requisites for this course: set theory, logic, proof strategies, etc.

I did something similar last year with Statistics and Probability. The best place I've found for a linear course for online math is https://www.khanacademy.org/

I was able to start at the beginning and get all the necessary math to actually step forward to some of the more complex courses. I'd suggest starting there.

I did start there actually. As much as I love Khan Academy there are lots of holes and the quality/thoroughness of video explanations really seem to drop off the further along you go.

To me they were most useful when I just needed a refresher on the precise operations to go through in order to solve a particular kind of problem, but already understood it. It's hard to beat a textbook for learning material that is completely new to me.

This may also help you if you're going the autodidactic route:


Hi there and congrats on working through this course. Most students coming into this class are learning all the formalized truth table/mappings/isomorphism/etc stuff for the first time. I took this class after having failed a course in Real Analysis and ended up appreciating it not so much as a math class but as a good intro to how to think about Theoretical Computer Science.

Looking back at the psets, i think it's actually worth looking at them in reverse order just to not get too discouraged: the class ends on some number theory and begins with the Relation/Axiom/Set/Sequence stuff you see in early high level math classes. Some of that number theory/counting stuff is incredibly accessible from the outset, so the class doesn't just get monotonically more obtuse.

That said, if you've worked through vellman and you finish up this class, you're more than ready to do a class in proper number theory, discrete math or even real or complex analysis. Somebody else said that this course was a prereq for clrs, it is sort of, but you could take them both concurrently if you had to, as clrs doesn't have such a strong focus on proofs (if you're interested, 6.045j is a good followup in automata/computability/etc, lots of regexes, state machines and turing machines)

anyhow, i just want to say that it's ok if you don't get it all at once. i think i ended up seeing lots of these ideas two or three times in a variety of classes. probably the first time i was just mechanically spitting out proofs without understanding them. by the third time i came across them, they actually clicked for me. But there was value (for me at least) to exposure early on because you do know the things that are hazy and it's easier to dive deeper on those the next time you encounter them.

have fun!

Learning those topics will not be a waste of time. You'll see them come up time and time again on your path towards more CS topics.

"Concrete Mathematics" by Knuth is by far the best presented book on maths relevant to CS that I've seen. You could definitely work through it with your background (I did with a similar background), it's challenging but approachable.

I'm working through that as well, it's excellent.

I'm looking to gain the math foundation needed do inch my way towards data science. Could anyone on HN recommend a good path to take? For simplicity's sake, imagine my math level is 0.

Also, curious to know if anyone has good book suggestions or places with practice problems.

Edit: This is the best list I've been able to find so far http://datasciencemasters.org/#math

I am self-teaching myself mathematics for a few years now and will suggest the following: Algebra and Trig, a subset of which is known as pre-calc. Don't short yourself on this because it is basic and you don't want to be struggling with it at the same you are struggling with the higher level stuff. I cannot recommend Sheldon Axler's Algebra and Trigonmetry highly enough. After much searching I found that and have been through it 3 times.

Next Calculus: I recommend Gilbert Strang's text book which will take you through what in uni is called Caculus 3, 1 being intro, 2 being differential and 3 being integral. I in the midst of this book and so can't speak to further but my plan is to move onto Strang's linear Algebra. After that, where to go depends on particular interest but leaving any of that out, in my opinion, will just handicap your further studies. Moder education does a lot of things wrong but the standard math sequence in use everywhere isn't one of them imo.

In addition, get Israel Gelfand's books (http://gcpm.rutgers.edu/books.html).

Sure :)

They are.

Epp's Discrete Mathematics with Applications is a nice book that covers much of the same material as this MIT class, but at a slower, easier pace. It's highly suitable to the beginner.

You should know high school algebra and precalculus to be able to read the book. Trigonometry and calculus are not prerequisites, although you will probably want to learn those too.

In addition to what others are saying I can't stress enough how important combinatorics are as well. Definitely spend some time trying to understand this area. From there move on to stochastic processes.

Thanks for the note! This looks like a good place to start: https://www.khanacademy.org/math/probability/probability-and...

Would you agree?

Looks good. I used "Fundamentals of Probability with Stochastic Processes" by Ghahramani. Very good book.

MIT OpenCourseWare has been a great tool for me as an undergrad. Since the start of year, I've watched the CS and Econ uploads concurrently with the courses I've taken.

It's not that the lectures are better, but getting a second chance to see the topics under slightly different contexts has been pretty effective for study. I've had the same experience with Khan Academy in my lower division courses.

This is a similar course with some overlap: http://www.cs.cmu.edu/~15251/

I haven't looked at the MIT course in detail, but doesn't it seem like Concepts would be more similar to this than 251?

I just want to put a plug in for the video lecture portion of this. Tom Leighton is an excellent lecturer. There is plenty of electronic textbooks/courses, but I really do think he explains the course material in an engaging and lucid way.

This seems extremely useful. My school did not have a consolidated math class like this, although computer science and software engineering students were required to take various courses in math, particularly discrete and combinatorial math and linear algebra.

I do know that there were many students who double majored in Math / Computer Science although there was a restriction on minoring in mathematics as a CS student because of the large number of prerequisites. Still, it seems useful to combine proofs, induction, graph theory and related domains into one course. I did opt for taking a large number of math classes and some fairly high-level electives, and I have to say the most interesting area I came across was the use of generating functions for solving recurrence relations and the study of the Catalan numbers. For those of you unfamiliar with the Catalan numbers, it is the sequence of the number of binary trees that can be created with a certain number of elements. Another area they come up in (among a large number of problems) is creating paths by Manhattan distance.

The Catalan numbers also count the number of expressions with matching pairs of parentheses.

Catalan numbers show up all over the place and are a really useful sequence. My combinatorics course in undergrad had a "Catalan Problem of the Week" where you would have to show that the Catalan sequence solves a particular problem.

Concrete Mathematics is also a good background.

One of my favorite math books ever, but definitely not for the faint of heart. It's starts off slow but gets hard fast.

Having done an equivalent course in Australia I can say: despite being a struggle at the time to get my head around the content, in hindsight knowing this stuff is invaluable as you continue with your degree.

Discrete Mathematics has been invaluable in Formal Languages (Turing machines), Algorithms and Data Security.

Math is just manually running code in your head. Which is just an ignorant and wasteful obsoleted vanity, like remembering and performing a series of notes.

Is thinking obsolete too?

Being a CS student in my Bachelors I was able to spend sometime on Number Theory. But the lectures here blew mind.

I believe this is a pre-req to CLRS too.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact