Mathematics for Computer Science (2018) [pdf]

Context:

Thomson Leighton is the founder of Akamai

Lectures here: https://www.youtube.com/playlist?list=PLB7540DEDD482705B

One of the set of lectures on the internet I loved the most.

Each section is quite standard in presentation which isn't a bad thing.

I love that each citation has back references to _all_ the places that it is cited from.

I wish more books did this.

I really love this book, it is hard af but I still can understand 1-2 pages of each paragraph. I have received some great insights, like the function is the endless lists of inputs and outputs, and some really great humour, such as all is not lost in mathematical notation. I really wish I can understand this book completely before I die.

I always see lists of like 100 MUST HAVE books for Computer Science. Is there like a top 5 must have books for Computer Science?

I like this book. The probability section is great, especially how they handle the Monty Hall paradox. They use "four step method" that breaks it down perfectly - way clearer than the explanations you get in movies like 21 or numb3rs.

I took a look at the table of contents and found that the second chapter is about the well-ordering principle. That’s surprising to me because I’ve only heard of the well-ordering theorem by Zermelo, which is a fundamental theorem in set theory, stating that any set has a well-ordering assuming the axiom of choice. It’s amazing and mind-bending in its own right (imagine a well-ordering for reals), but is clearly not very relevant to computer science.

I find the well-ordering principle slightly bewildering. It seems to presuppose the existence of an ordering on natural numbers and then prove this principle. But I’ve never been taught things this way; you always construct the natural numbers from Peano and define the ordering first, then you can actually prove the well-ordering principle rather than leaving it as an axiom.

re: Chapter 15.8 on the so-called pigeonhole principle

Following Dijkstra’s EWD1094, here’s a way to solve the hairs-on-heads problem eschewing the language of pigeonholes and employing the fact that the mean is at most the maximum of a non-empty bag of numbers.

We are given that Boston has 500,000 non-bald people. The human head has at most 200,000 hairs. Show that there must be at least 3 people in Boston who have the same number of hairs on their head.

Each non-bald Bostonian must have a hair count between 1 and 200,000. The average number of such people per hair count is 500,000 / 200,000 = 2.5. The maximum is at least that; moreover, it must be a round number. So the maximum >= 3. QED.

I've not worked through a large book of problems like this before. At risk of sounding silly, are there solutions to the sample problems? I've given a few a go but can't find the answers anywhere to check my work.

This is a very valuable resource for me. Thanks for posting!

This is why I love Hackernews - I've literally been looking for this recently and now I get it as a full PDF.

Does anyone have recommendations for better screen readers?

I'm not such a fan of trying to cram everything-mathematically-relevant into a single huge book (and it is huge - 1048 pages).

Anyway, this reminds me of a rather different initiative in the same vein: The building of Mathematical principles based on the expediences of Computer Science: CONCRETE MATHEMATICS

by Donald Knuth, Ronald Graham and Oren Patashnik.

https://www-cs-faculty.stanford.edu/~knuth/gkp.html

https://en.wikipedia.org/wiki/Concrete_Mathematics

available on the Internet Archive: https://archive.org/download/concrete-mathematics/Concrete%2...

It did not see the proof of the correctness of circular buffers? one consumer, one producer, parallel execution, 2 atomic pointers, one read pointer, one write pointer and the cycle bits.

[dead]

[dead]