Mathematics for Computer Science | Hacker News Reader

Mathematics for Computer Science

courses.csail.mit.edu

138 pointsr15habh25 comments

This looks excellent. I also heartily recommend Knuth's Concrete Mathematics (http://www.amazon.com/Concrete-Mathematics-Foundation-Comput...)

This book has a great chapter on recurrence relations. Saved my ass in an algorithms course iirc.

I teach a number theory course to gifted high school students. I've been using these notes for two years now to plan lessons and find exercises. Great resource. You can also find more materials for the same course on MIT OpenCourseWare.

Just a question for CS graduates here, how many Math courses were required to major in CS?

When I was an undergraduate the bare minimum was:

- 2 algebra (number theory + linear algebra)

- 2 calculus (single variable)

- 2 statistics

- 1 logic

- 1 combinatorics (graph theory + enumeration)

There was no "Math for CS" course per say, there was just math you should know. And that was the bare minimum for a BCS, the BMath (CS) had even more. I myself struggled with those courses (mostly the "raw" math courses rather the CS-y ones) but I'm grateful now that I did them. Math and Computer Science are so intrinsically linked.

I'm probably going to be the sore one out when people from better schools start posting replies, but at my school which has a very small computer science department (so small that I'm not even doing the CS major even though I'm a professional) only requires:

- Calculus I

- Calculus II

- Introductory Statistics

Somewhat the same here. My state school required these:

- College Algebra (part of the state-mandated core for all degrees)

- Calculus 1

- Discrete Mathematics

- Probability and Statistics (4000-level course)

At Carnegie Mellon, the following are required:

  * elementary discrete math
  * intermediate discrete math / intro CS theory
  * calculus I
  * calculus II
  * linear algebra
  * probability
  * an "algorithms and complexity" elective:
    combinatorics, graph theory, automata, etc.

I might be missing one or two.

This is assuming you don't count the algorithm design and analysis class as math, or any of the "logic and languages" (Intro PL, constructive logic, Automated program verification, basic logic, computability and incompleteness) as math.

I completed my graduation last year, the compulsory Math courses at my time were:

- Linear algebra

- Calculus (single variable)

- Discrete mathematics

- Probability & Statistics

- Numerical Methods & transforms

Here is what I remember taking for my CS degre at university of KC.

Trigonometry Calculus I Calculus II Calculus III Differential Equations Discrete Algebra I Discrete Algebra II Statistics Applied Probability and Network analysis Numerical Analysis Engineering Physics I Engineering Physics II Algoriths and datastructures

- 3 algebra (linear algebra + number theory + abstract algebra)

- 4 calculus (!)

- 3 statistics (2 basic + stochastic processes)

Besides, there was a quite a bit of discrete math in mandatory theoretical CS subjects: Algorithm Analysis, Graph Algorithms, Formal Languages, Boolean Algebra, Formal Methods, etc. But I wouldn't count these as "math" proper.

We also had 2 or 3 mandatory Physics subjects. I wasn't interested in physics and found them pretty useless. Some professors justified them as an "application of advanced calculus", while the advanced calculus subjects were touted as essential to a proper understanding of physics.

I'm a CS major at MIT.

Single Variable Calc (required for everyone at MIT) Multi Variable Calc (required for everyone at MIT) Math for CS (this class) Diff eq OR linear algebra

You might count the algorithm analysis class as math since it's in both the math and eecs department. Lots of people take both diff eq and linear algebra, and everyone I know also took one statistics class.

http://web.mit.edu/catalog/degre.engin.ch6.html#

I find it somewhat strange that generating functions are introduced significantly before recurrences are (and that recurrences are introduced last!). Does anyone know why the authors did that?

I would guess that it's something like SICP introducing assignment halfway through the book, dramatic, unexpected, and you've been using a weaker version for many chapters now. (Chapter 6 is about recursive data types, and comes immediately after chapter 5's induction to give some perspective.) But it might also be because, as an introductory mathematics course, it wants to stay a good distance away from algorithms and messy concepts like big-O notation.

Recurrences are partially covered in chapters:

  13 (Sums and Asymptotics)
  15 (Generating Functions, as you mentioned)
  19 (Random Processes)
  20 (Recurrences)

and though they're not explicitly named as such in Chapter 5 (Induction), several of the problems in the chapter make use of them.

It seems to me that the first half of the chapter on recurrences covers recurrences more from a CS viewpoint such as the recurrence they list for mergesort:

  T(n) = 2 T(n/2) + n - 1

which is arguably less fundamental than the study of linear recurrences which come up more often in math. The second half of the chapter covers techniques for solving general recurrences, both for general linear recurrences and general divide-and-conquer recurrences using the Akra-Bazzi theorem (which is an extension of the Master Theorem).

Thus, perhaps the chapter "Recurrences" is misnamed – the authors certainly cover elementary recurrences in the earlier chapters and leave more complex topics recurrences (such as how to solve them in general) for the end because they are less important than most of the other topics in the book.

Great to see it completed. The previous draft was salvation for my graph theory course. I think Mathematics for Computer Science offers very good understanding without unnecessary jargon or formalisms that obscure more than they clarify. Truly excellent introduction. In the same spirit I'd like to recommend the books of Walter Warwick Sawyer, and the "How to Ace..." books of Adams/Hass/Thompson.

I took this class (6.042) as a sophomore a few semesters ago. I wasn't terribly good at it. Additionally, the professor and staff were a real pain in the ass, so I didn't really have the best experience. I remember they were writing this text my year. They made us do reading assignments critiquing each section. They were basically having us proofread it for them.

Perhaps a stupid question, but does the class at MIT cover this entire textbook in a semester?

Not stupid at all. Yes, as I remember it, this was pretty much all covered in a single, 14-week semester.

Damn, that's a pretty rigorous schedule. I guess that's why MIT is MIT, haha.

I think this is somewhat standard practice in classes where the prof is writing a book. I think I've done it a couple of times, at least. (By the way, you should've taken it F10!)

>"By the way, you should've taken it F10!"

My god, yes. I wish I would have had the foresight to have done it earlier rather than in the Spring. I am definitely not a fan of TEAL.

I really like this book, it start with the very basics: Discrete Mathematics with Applications (http://www.amazon.com/gp/product/0495391328/ref=oh_o04_s00_i...)

I took this class last semester!

As a mechanical engineering major who is interesting in computer science I really enjoyed it (the Psets were a bit annoying sometimes though). The text is pretty easy to read too.

Was it TEAL last semester? That's really what made me dislike the class the most, as well as the less-than-helpful staff.

Reply on news.ycombinator.com