6 ms·

Mathematics for Computer Science

138 points by r15habh 15y ago

dhconnelly 15y ago
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.
joshzayin 15y ago
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?
- drostie 15y ago
  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.
- spicyj 15y ago
  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.
duaneb 15y ago
This looks excellent. I also heartily recommend Knuth's Concrete Mathematics (http://www.amazon.com/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025/ref=sr_1_1?ie=UTF8&qid=1332445763&sr=8-1 http://www.amazon.com/Concrete-Mathematics-Foundation-Comput...)
- swordswinger12 15y ago
  This book has a great chapter on recurrence relations. Saved my ass in an algorithms course iirc.
halayli 15y ago
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_i00_details http://www.amazon.com/gp/product/0495391328/ref=oh_o04_s00_i...)
etiam 15y ago
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.
strawbucks 15y ago
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.
- swordswinger12 15y ago
  Perhaps a stupid question, but does the class at MIT cover this entire textbook in a semester?
  - strawbucks 15y ago
    Not stupid at all. Yes, as I remember it, this was pretty much all covered in a single, 14-week semester.
    - swordswinger12 15y ago
      Damn, that's a pretty rigorous schedule. I guess that's why MIT is MIT, haha.
- daveed 15y ago
  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!)
  - strawbucks 15y ago
    >"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.
k3fernan 15y ago
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.
- jc4p 15y ago
  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
  - techsupporter 15y ago
    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)
- spicyj 15y ago
  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.
  - joshzayin 15y ago
    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.
matlaber 15y ago
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.
- strawbucks 15y ago
  Was it TEAL last semester? That's really what made me dislike the class the most, as well as the less-than-helpful staff.

138 points by r15habh 15y ago

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.

joshzayin 15y ago

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?

drostie 15y ago
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.
spicyj 15y ago
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.

duaneb 15y ago

This looks excellent. I also heartily recommend Knuth's Concrete Mathematics (http://www.amazon.com/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025/ref=sr_1_1?ie=UTF8&qid=1332445763&sr=8-1 http://www.amazon.com/Concrete-Mathematics-Foundation-Comput...)

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

halayli 15y ago

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_i00_details http://www.amazon.com/gp/product/0495391328/ref=oh_o04_s00_i...)

etiam 15y ago

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.

strawbucks 15y ago

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.

swordswinger12 15y ago
Perhaps a stupid question, but does the class at MIT cover this entire textbook in a semester?
- strawbucks 15y ago
  Not stupid at all. Yes, as I remember it, this was pretty much all covered in a single, 14-week semester.
  - swordswinger12 15y ago
    Damn, that's a pretty rigorous schedule. I guess that's why MIT is MIT, haha.
daveed 15y ago
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!)
- strawbucks 15y ago
  >"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.

k3fernan 15y ago

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.

jc4p 15y ago
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
- techsupporter 15y ago
  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)
spicyj 15y ago
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.
- joshzayin 15y ago
  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.

matlaber 15y ago

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.

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