Mathematics for Computer Science: Readings

It looks even better than the MIT course itself. I hadn't heard of Wigderson before, but now I'm definitely going to keep an eye on his work. Thank you for sharing this.

I guess the book is more like “additional math for CS students beyond what a common CS curriculum has”.

Doesn't look like it.

One might argue that linear algebra is slightly more niche than stuff like graph theoretic algorithms. There are applications to broadly useful things like gradient descent, but that seems to fall under numerical linear algebra which probably deserves its own course in the Applied Math department.

N.b. just playing devil's advocate, I don't have a strong opinion either way.

Because 6.042J is "an introduction to discrete mathematics, probability, and mathematical thinking for computer scientists".

For linear algebra, see https://ocw.mit.edu/courses/mathematics/18-06-linear-algebra...

I'll admit I don't know how the MIT CS curriculum is structured, but I suppose it is in there, just not in this particular course.

This is a discrete math course.

edit: originally had posted, "This is a discrete math textbook."

There are a few reasons.

First, the purpose of a class like this is to prepare students for further coursework in algorithms and automata/complexity. You need logic, graphs and combinatorics for those a lot more than you need linear algebra.

Second, the math department teaches a class in linear algebra. This is a collection of topics that you wouldn't ordinarily find in undergraduate math classes.

Third, there's a limit on how much linear algebra you can cover in part of a course like this. Better to give it its own semester so you can treat the subject in some reasonable breadth.

It's the textbook for a course calls "Mathematics for Computer Science" at MIT. Linear algebra is a separate course (18.06 or 18.700).

There's a set of 2015 lectures to go with it https://ocw.mit.edu/courses/electrical-engineering-and-compu...

There's also the CMU intro to proofs/reasoning lecture notes here https://infinitedescent.xyz/ though you would learn much of this material from the introduction of Apostol's Calculus. The advantage of the CMU lecture notes is the author based it on his findings in evidence based learning IIRC.

I took a look at the first four or so chapters and I'm not really a fan of the organization. But I think you could self-study the material and be fine. The introduction of the book explains that it's very focused on proofs, and it feels to me like it's more of an applied mathematics book than it is discrete mathematics (i.e. computer science) book. That's a subtle distinction, but I'd summarize it by saying this book feels as if it was written more for math majors than computer science majors. That doesn't mean you shouldn't read it; rigor and formalization are important! It just means that (as I interpret it), the authors are focusing more heavily on mathematical formalization and foundations than most "discrete mathematics" treatments.

For the context of my opinion: my favorite math textbook for computer science is Chapter 1, Section 1.2 of The Art of Computer Programming ("Mathematical Preliminaries"). That's pretty dense though, so I usually recommend Concrete Mathematics, which was also (co)authored by Knuth. The benefit of Concrete Mathematics is that it spreads the information out with more examples and better exposition. It also includes an expanded section on probability. But in my opinion, the failing (if you could call it that) of both is that there isn't a dedicated section on set theory. I really think that should be covered alongside the introduction to various types of proof.

Which brings me back to this textbook...I personally think it spends too much time building logic and proof machinery in the first chapter. Sets and functions have sections that are only pages long, but there is a large focus on logic. I understand it's a mathematics for computer science treatment and not a pure mathematics treatment, but that's actually pretty dry in my opinion - I think a treatment that focuses more on sets is more intuitive. One of the things I like about Knuth is that he covers these topics in a slightly irreverent and humorous way. He also engages the reader by jumping more directly into arithmetic operations, functions, basic number theory, the binomial theorem and combinatorics, etc.

Some of this is admittedly my own bias. I've never enjoyed staring at things like e.g. truth tables. It's important to know, but this actually seems excessively formal for a discrete mathematics course. Reading through the algebra of propositions isn't exactly riveting. I think that, for self-study at least, exposition and organization of topics is just as important (probably more so) than complete coverage of topics. All of the material you'd want to know is there, it's just that the treatment might be a bit suboptimal for self-study. It probably depends on what you find interesting and how quickly you'd like to do interesting things with what you're learning. It would probably also be beneficial if some people who have actually learned from this textbook for their first encounter with the material could chime in, because that might be more relevant to your question.

I've read the probability part a couple of years ago to make up for missing formal knowledge, and it was easy to grok and helped me.

Yes.

Out of most math texts, this is very accessible and mind-expanding. Even if you don't get everything on the first pass, you'll come out with a lot of interesting insight into the field.

I don't know your level, but I don't recall anything too insurmountable for someone with a decent base in math.

I'm currently taking a near-identical course as a CS freshman, and while I lack the programming expertise to adequately explain the importance in that field, it's definitely valuable to learn. I've never enjoyed a maths class more, really.

It offers so many 'hacks' to working with numbers, which I could imagine would make code more efficient and avoid unnecessary computations when dealing with very large numbers.

Separately, my increased mental efficiency with problems involving numbers is really surprising. There have been interview questions I've read about in the past where I've thought "someone must be a genius to be able to answer that through mental math," and it all makes so much more sense now! It's taught me about dozens of visualizations that can break down these problems in much more manageable ways.

As an example of a mental maths problem on my midterm: How many numbers between 1 and 99,999 have digits that add up to 10? (23,500 would work whereas 23,510 would not). While initially I would have no clue how to answer this, learning about the balls-in-bins method solves it in an incredibly simple manner.

I am also taking a course similar to this at my own university, actually using the same text-book. I guess the knowledge and skills gained from this course only apply to a small subset of problems, specifically those requiring some heavier theoretical / algorithmic thinking before implementation. While this only goes over a few algorithms in the chapters I have studied, it gives a very strong background which I'm sure would help in any other studies of algorithms you would pursue. Just by being introduced to the basic notation and language of some of the mathematics, I've found that I can read on different algorithms (in context of an academic paper / report) that I would like to implement with much more ease.

Nearly 0 in practice. It's great if you want to get a CS PhD and off to high-paying jobs in SV/WS. Rite of passage mostly.

I've been collecting some books on proof to build a foundation for better learning formal verification of software. The capabilities of modern provers, esp if combined with automated methods, can handle a lot more practical software than in the past. Even those like SPARK Ada with a lot of automation has properties that require manual proof. Certain things might also be easier to prove manually with a more powerful logic.

My hope is that I find enough feedback on good/bad of cheap or free resources on this topic that I can determine some default recommendations for people curious. The problems can be addressed with supplementary material. Eventually, the defaults would be good enough that the process would happen faster. A larger number of people centering on the same resources might become a community for helping new people. That might increase the inflow. Simultaneously, some percentage of these people are working on tools, esp automated, to make the proof process more productive. Over time, we might have a much larger segment of people working on formal verification than we do now. Maybe even large enough to sustain more tool development by contributions or licensing.

So, that's why I'm looking at books like this with what I think they might help us achieve. I'm way too out of my depth to know if it will work. I just know accessibility, better learning materials, and network effects always help.

Example tools below for sequential programs, concurrency, and hardware:

https://en.wikipedia.org/wiki/SPARK_(programming_language)

https://learntla.com/introduction/

http://prod.sandia.gov/techlib/access-control.cgi/2014/14205...

In my experience, it's been helpful occasionally. I've used techniques from it once or twice when writing algorithms to figure out what exactly the constraints on their inputs would be, however, other than that I don't think I've ever used it.

The text book says:

"The analogy between good proofs and good programs extends beyond structure. The same rigorous thinking needed for proofs is essential in the design of criti- cal computer systems. When algorithms and protocols only “mostly work” due to reliance on hand-waving arguments, the results can range from problematic to catastrophic. An early example was the Therac 25, a machine that provided radia- tion therapy to cancer victims, but occasionally killed them with massive overdoses due to a software race condition. A more recent (August 2004) example involved a single faulty command to a computer system used by United and American Airlines that grounded the entire fleet of both companies—and all their passengers! It is a certainty that we’ll all one day be at the mercy of critical computer systems designed by you and your classmates. So we really hope that you’ll develop the ability to formulate rock-solid logical arguments that a system actually does what you think it does!"

Because it's not Mathematics for Programmers?

I wonder how one would read 1000+ pages of a technical book like this.