[ioli]

The Algorithm Design Manual by Steven Skiena

Amazing book. Very readable. I highly recommend it. The book has a section call "War story" at the end of each chapter in which Skiena shares his real life experience of when the contents from that particular chapter came in handy for him.

Go through it. You won't regret

https://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena...

[MarvelousWololo]

Not OP but I’m interested in this subject as well. I took a look at this book and others that are similar and I’ve realized my foundations on math are really lacking to even understand the given examples. Since I only had the opportunity to finish my high school diploma and this was several years ago I wonder if you could have any suggestion to brush my math knowledge up in order to properly understand the examples of these books. The thing for me is that I’m not sure where I should start. Would you know any resource to introduce me to the math foundations in order to understand such texts? Or maybe math concepts that I should study before I dig in. I really appreciate it. Thanks.

[wheelinsupial]

I'm not sure if this is universally true or not, but the algorithms courses at the universities I'm familiar with require a course in discrete math as a prerequisite.

You can find Discrete and Combinatorial Mathematics (an Applied Introduction), 5th Edition, Ralph P. Grimaldi online and an answer key can be found online as well. (This book covers two discrete math courses. Chapters 1-5, 7, 8, 12 is a first course in discrete math. I'm not sure what chapters the second course covers, but that requires linear algebra as a prerequisite.)

It's not perfect, but it's a start. I think you need to be familiar with some high school algebra, exponents, and logarithms. You can find some review information in the appendix. If you have troubles with recalling that information, then you can try Khan academy. (It really is an if you don't use it, you lose it situation with much of math.)

You're probably aware of this already, but most people don't read the book and come away with the knowledge required to solve the problems. You'll need to work through the examples in the chapter, be able to recall the definitions and theorems, and then work the exercises at the back of the book.

I think the discussion of proof methods is pretty poor in the book. You can find many intro to proof method type supplemental notes online to help fill in the details.

There really is so much information out there that you can pretty much always find an alternative explanation or viewpoint for undergrad level material. Many profs will post their own lecture notes, homework, and solutions. There are some math forums that have explanations. So find a book you're reasonably comfortable with and supplement it with extra material.

[LAIFscratch]

The best book if you have any programming background is 'Mathematical Modeling and Applied Calculus' by Joel Kilty and Alex M. McAllister reviewed here: https://www.maa.org/press/maa-reviews/mathematical-modeling-...

There's a small workshop for it here: https://learnaifromscratch.github.io/calculus.html throwing in some youtube tutorials. The book presents everything as functions and their parameters, like linear functions, trig, sigmoidal, e and logarithms, you learn all the parameters to these functions and can type into desmos online graph to see what they're doing visually. You don't have to do the whole thing just use it for background material when an algorithm text uses calculus methods like L'Hopital's rule.

Poh-Shen Loh has a discrete math course open on his youtube channel https://www.youtube.com/c/DailyChallengewithPoShenLoh/search... you can use the book he recommends to look up anything that is assumed knowledge in lectures. Discrete Mathematics, by L. Lovász, J. Pelikán, and K. Vesztergombi. A book called Asymptopia by Spencer is well done too, good chapters for learning everything you want about big-O/omega/theta some topics are advanced and some anyone can do.

[ramesh31]

>Since I only had the opportunity to finish my high school diploma and this was several years ago I wonder if you could have any suggestion to brush my math knowledge up in order to properly understand the examples of these books.

You should really consider taking a few community college math courses if you're serious. Math is extremely difficult to learn on your own. Not only because of not knowing what you don't know, but because it requires intense effort and repetition which is very hard to force yourself to do. You can work through the concepts and delude yourself into thinking you understand something when really you're just hand waving it. Taking an actual course and being faced with the gaps of your knowledge by someone else is very humbling and essential to actually learning it.

[HarryHirsch]

That of course assumes the community college is serious about its mission to educate. Most of the students just want to pass because the math course is required for this or that vocational program, and in this age it's wiser to humour the students and wave them through.

[mathhh]

> You can work through the concepts and delude yourself into thinking you understand something when really you're just hand waving it

I keep seeing this and I don't quite understand how this one works.

If I were studying math on my own (which I've done and still do), I'd do the following:

1. Pick a book. Say, Rudin's Principles of Mathematical Analysis[0]. Read a section, then attempt problems. Pick a problem. Say, "prove {1/n: n is natural} U{0} is compact directly from the definition(not using Heine-Borel)". It's guaranteed your "proof" is not a proof.

2. Compare your solution to existing solution manuals or ask a question on MSE[1]. Since the given book by Rudin is super-massively famous, each question has probably been asked/answered about a bagillion times each on MSE, so just searching MSE alone would likely to spit out many answers to your questions. People on MSE will tell you exactly why your "solution" is wrong and where you tripped up. Sometimes even the clarifying answers are hard to understand. But then you can ask new questions, think more, correct your misconceptions until it all finally clicks. Do that with all the rest of the problems[2].

I don't see how the process above is delusional.

[0] This book is not a realistic fit for a novice, though. Instead, one would start with books like [3], [4], [5], [6] to learn how to prove things and think like a mathematician would.

[1] https://math.stackexchange.com/

[2] In reality, the more math you see and do, the more mathematically mature and less dependent on others(to check your work) you become. In fact, if you can solve any problem in "B@by Rudin" and some famous abstract algebra textbook (say, Dummit & Foote's "Abstract Algebra") cold, you're way ahead of most any undergrad math major in the world! Because standards on undergrad math majors are not that high, nor that brutal the world over no matter what they say. If, additionally, you can solve any given problem in a book like, say, Hatcher's "Algebraic Topology" or any other famous grad level textbooks on, say, differential geometry or, uhh, functional analysis, you're officially in the big leagues. Again, if you're worried about being delusional about your proofs, you can always present them on MSE.

[3] "Book of Proof" by Richard Hammach. It's online free.

https://www.people.vcu.edu/~rhammack/BookOfProof/

[4] "Discrete Math" by Susanna Epp

https://www.google.com/books/edition/Discrete_Mathematics_wi...

[5] "How to Think About Analysis" by Lara Alcock

https://www.google.com/books/edition/How_to_Think_about_Anal...

[6] "Linear Algebra" by Kuldeep Singh

https://www.google.com/books/edition/Linear_Algebra/BJNoAgAA...

[wheelinsupial]

> I keep seeing this and I don't quite understand how this one works. > I don't see how the process above is delusional.

Because those that are just starting to learn math don't take your approach to learning.

I had a lot of bad habits that I had to break when I was learning math that really caused me to do poorly in many classes. If you are coming at it from a more qualitative field, then it's very easy to read the book and come away with nothing from it.

I'm taking a discrete math course and I was trying to offer up some advice on the school's subreddit to someone struggling in the class. They mentioned something about me taking the easier prof, so that's why I'm doing well. I said that I had fully worked at least 50 problems in each chapter we covered and asked how many they had done. The response was I went to lecture, read the notes once, and attempted the homework exercises; I didn't know you had to do some much work in this class.

[mcguire]

Step 1.5: Decide you're not making progress on the problem, look up the answer on MSE, say, "OK, I get that" and go on.

Alternate: Ask a question, get a not-quite-right answer, and find yourself completely stuck two chapters further in with no way of figuring out where you went wrong.

[bakuninsbart]

Concrete Mathematics by Graham/Knuth/Patashnik is still a great resource on the kind of mathematics and mathematical thinking we need in CS, but I'm not sure if it is fully accessible with a high-school level of Maths.

To be perfectly honest, I doubt I would've ever gotten through college-level maths without being forced to do it, as it can be very frustrating and difficult in the beginning. Unless you are quite confident in your self-discipline and enthusiasm to learn maths, rather than books I'd recommend something interactive (online course, forums, challenges).

If you are interested in a starting point to learn mathematics that are relevant for CS, I'd start with propositional logic and boolean algebra, as well as proofs via induction.

[dragontamer]

Art of Computer programming starts at a high school level.

It's very rigorous and considered one of the more difficult reads. But if you start at chapter 1 page 1, it covers all the math you'll ever need for the rest of the books (which is sufficient maths to reach masters or even PH.d level comp sci)

I know I've recommended it to high schoolers. A lot of math is just getting used to the nomenclature and vocabulary. The sooner you get used to rigor the better

[exdsq]

AoCP is an absurdly inefficient way to learn algorithms that 99.999% of people won’t need

[LAIFscratch]

TAOCP is probably the best book if you approach it as infotainment/puzzles casual reading on the weekend reading about the history of trees and their mathematical properties kind of reading not anxiety filled interview passing cramming. Even autodiff online algorithms is in there something heavily used right now.

[exdsq]

I've bought them and looked through it but if someone asks how they should go about learning algorithms for leetcode there are so many better options thank Knuth. That is years of effort to get through.

[dragontamer]

Most algorithm books don't cover the math like summations or generating functions.

Chapter one of TAOCP for better or worse, is a very rigorous mathematics introduction.

I'm not recommending it for it's algorithms (which are unfortunately somewhat out of date). I'm recommending it because it's an incredible mathematics introduction, albeit a very difficult one.

[56V9qtdGKWy4q8p]

Can you elaborate on "out of date"? I've seen a lot of books considered out of date because of their publishing date, but to what's exactly being compared to be considered so?

[dragontamer]

Well, Volume 4 was released in 2016 and is not out of date at all. Its a very good read, but on an obscure subject.

But Volume 1 has lots of out-of-date advice and is somewhat of a shame, because its otherwise an excellent introduction to computing + the mathematics needed to understand computing. For example, the assembly language is based on the 1960s computers, such as decimal computing and 6-bit numbers (based on the days of old, before 8-bits were standardized).

Functions are introduced by self-modifying code first and foremost: by rewriting "jump" instructions at the end of functions as a return. No one does this anymore: pretty much all compilers do the stack-thing instead. (Push return address onto a stack register).

The Fascicle on MMIX updates a lot of those sections to a modern-like 64-bit assembly language. However, the sections on cofunctions, arrays, garbage collection aren't part of that update... and should be updated (Knuth's discussion on these concepts is great, but are told in an "old way" based on 1960s tech)

Volume2: Seminumerical Algorithms (chapter 3 / 4) is again, a decent introduction to the subject. But the RNG stuff is fully obsolete. The statistical tests may have passed muster in the 1970s or 1980s, but today's statistical tests (aka: PractRand) go above and beyond what Knuth discusses.

There's a lot of interesting discussions in the randomness chapters: such as the efficacy of multiplication when it comes to bit-mixing (and I feel like modern RNGs are sleeping on that tidbit), but modern RNGs are generally based on a simpler sequence of ADD / XOR / SHIFT instructions based around the concept of permutations / perfect bijections.

----------------

Ironically, I consider the section on "tape sorting" to be "suddenly up-to-date" again. Modern RAM acts more like a tape (sequential is far faster than random), meaning that thinking of sorting problems in terms of external-sort is surprisingly relevant.

Given that today's cache is 768MB (see AMD's Milan-X CPUs: expected to be a ~$5000 CPU-server chip), we see that L3 cache basically serves as the RAM from Knuth's time, while today's DDR4 RAM really acts as the fast-sequential / slow-random layer that Knuth studied so much.

[exdsq]

The obvious example for me is the chapter on tape merging

[gtirloni]

This is a good starting point: https://youtube.com/playlist?list=PL7wAPgl1JVvUEb0dIygHzO469...

[nickkell]

I had exactly the same issue with this book. It brought back memories of seeing teachers solve problems on the board and skipping some obvious (to the teacher at least) step.

This prompted me to check out khan academy. Man, that is an incredible resource. I really envy the schoolchildren of today that have instant access to this incredibly smart tutor, who can be rewinded at the touch of a button.

[joemidgett]

Check out the course 6.042J from MIT (Mathematics for Computer Science).

https://ocw.mit.edu/courses/electrical-engineering-and-compu...

[clumsysmurf]

Note, there seems to be a 3rd Edition in 2020

https://www.amazon.com/Algorithm-Design-Manual-Computer-Scie...

[musicale]

> The Algorithm Design Manual by Steven Skiena

And his CSE 373 course lectures: https://www3.cs.stonybrook.edu/~skiena/373/videos/

[omerhj]

I bought the PDF last year for $7 (a very steep discount) during Apress/Springer's Black Friday sale. If you don't need the book right now or are on a budget, it may be worth waiting until next week in case they repeat the offer.

[MonkeyClub]

I came here precisely to suggest Skiena. Excellent book that gives you a good grounding in both theory and practice, and opens the road for further study, if you're so inclined.

[codegeek]

Wow. I actually took one of his classes way back at Stony Brook. Great guy.

[lma21]

It's unfortunate that it costs 77$ :(

Edit: unfortunate for me ofc.

[cols]

Goodwillbooks.com had it for $11.50. As an aside, I really love that website. I am not too picky about the books I buy being in perfect condition, so it works out well for me. YMMV.

[bufferoverflow]

$30 used on ebay