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.
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?
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.
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.
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.
- 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.
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.
* 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.
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.
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
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:
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.
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!)
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.
