6 ms·
Discrete Mathematics – An Open Introduction, 4th edition
- phforms 2y agoAs an autodidact without an “official” CS degree, discrete Mathematics seemed to me like a key area to open up more advanced topics and solve many practical problems in programming. And indeed it helped me on many such occasions (although I am still studying). I really like the book “A Primer of Discrete Mathematics”[1] by Finkbeiner II and Lindstrom from 1987. It’s a bit old and unfortunately not free but still holds up pretty well and has many good exercises with selected answers. I will absolutely check out this book though, looks like a more modern approach with interactive exercises and it even is completely free! [1]: https://archive.org/details/isbn_0716718154 https://archive.org/details/isbn_0716718154
- kevindamm 2y agoYou may also enjoy [Concrete Mathematics](https://www.goodreads.com/book/show/112243.Concrete_Mathematics https://www.goodreads.com/book/show/112243.Concrete_Mathemat...) by Graham, Knuth, Patashnik.
- qsort 2y agoConcrete mathematics is significantly more advanced though, if I'm not mistaken it even introduces the basics of analytic combinatorics with OGFs. Something at the same level would be the basic competitive math curriculum in combinatorics and number theory.
- chongli 2y agoAren't generating functions a standard part of a first course in combinatorics? They were when I took introduction to combinatorics in university.
- grepLeigh 2y agoDiscrete Mathematics and It's Applications by Kenneth H. Rosen helped me get an A in CS70 (Discrete Math and Probability) at UC Berkeley this past summer. The textbook is quite large, but the content is very accessible. I'm also self-taught, finally taking formal math/physics coursework in my 30s to fill in the gaps. Another amazing resource has been California Community Colleges. So far every math teacher I've had has been extraordinarily passionate. Most math classes have an async/online section, and it's pretty common for adults to take the classes just for fun/self-improvement.
- deleted 2y ago[deleted]
- yumraj 2y ago> I'm also self-taught, finally taking formal math/physics coursework in my 30s to fill in the gaps. How did you take CS70? Are you enrolled as an undergrad/grad student?
- grepLeigh 2y agoThe summer session is open to the general public, and you can take courses through the Berkeley Extension during Fall/Spring on a space available basis. https://summer.berkeley.edu/ https://summer.berkeley.edu/ https://extension.berkeley.edu/static/studentservices/concurrent/ https://extension.berkeley.edu/static/studentservices/concur...
- nj5rq 2y agoI was intimidated by these math books, but I was able to find a lot of interesting stuff in "Applied Discrete Structures" by Al Doerr and Ken Levasseur[1]. I was attracted by the "Logic" section, and I was not disappointed. You can download it for free from their website. > It’s a bit old and unfortunately not free It's available on Anna's Archive, in case someone is looking for it. [1] https://discretemath.org/ https://discretemath.org/
- christianqchung 2y agoHey, that's my school! I didn't have Doerr or Levasseur (before my time), but James Propp did a phenomenal job of teaching the material. I don't know how discrete is taught in other schools but I thought having two dedicated classes for it was helpful.
- sn9 2y agoThe AOPS Counting & Probability books are shockingly good discrete math books that come with complete solutions manuals: https://artofproblemsolving.com/store https://artofproblemsolving.com/store
- charlesdbecker 2y agoAre these good for general education? I read somewhere they were great but more geared toward math competitions.
- sn9 2y agoThey might be overkill, but I don't see why not. I guess it depends on what you mean by "general education". They have great explanations of the fundamental concepts but use problems that really stretch you more than typical books. Probably better as a second exposure, but doable as a first for a bright and motivated student.
- deleted 2y ago[deleted]
- basedbertram 2y ago> A PDF of the book will be made available by August 15th. On the sidebar: > PDF coming soon :(
- jamesy0ung 2y agoAre you paying for it? If not, you don't have a right to complain.
- DoctorOetker 2y agoDon't turn this into a general rule: Payer Patrick pays molester Maverick to maim or intimidate victim Victor. Is Victor allowed to complain? Or only the person who paid?
- utopcell 2y agoWhat?
- dunefox 2y agoOf course he has a right to say his opinion. And this doesn't even count as "complaining".
- oscarlevin 2y agoThe PDF really is coming soon. I ran into some snags getting it to compile. Should be fixed by Monday
- gowld 2y agoLike too many discrete math texts, the Characteristic Root Technique for Repeated Roots section does not give a proof of the forumla.
- ykonstant 2y agoIt is a consequence of the form of the characteristic equation: if the double root is r, then expanding out x^2 - 2r + r^2 and matching terms we see that a = 2r and b = -r^2; in other words, the recurrence is a(n) = 2r a(n-1) - r^2 a(n-2). Divide by r^n to get the equivalent c(n) = 2c(n-1) - c(n-2), where c(n) = a(n)/r^n But this is the constant difference recurrence: c(n) - c(n-1) = c(n-1) - c(n-2) So c(n) is an arithmetic progression c(n) = x*n + y for some x and y given by the initial conditions. Thus the original sequence is a(n) = c(n) r^n = (x*n + y) r^n.
- YZF 2y agoThis reminded me of something else... I remember contrasting the discrete math course I took (circa 1990) to Knuth's AoCP and how Knuth used generating functions to find the closed form for recursive series (and IIRC didn't even cover any other methods). The course I took didn't touch on generating functions and most other textbooks I read didn't either. Interesting to see that this book does cover the topic. I guess "discrete math" can be a lot of different things.
- scythmic_waves 2y agoI think because a full proof covering existence and uniqueness will either be really long or require tools from outside the scope of the text. E.g. there's a somewhat concise proof using linear algebra which I'll partially reproduce below. (I like this proof because the equation is derived from first principles rather than starting with an ansatz.) --- Let x_n be a sequence defined by the recurrence relation: x_{n+1} = a * x_{n-1} + b * x_n Observe that if we define a sequence of two-element vectors of successive elements: [x_0] [x_1] [x_2] [x_1], [x_2], [x_3], ... then we can form the relation in terms of matrix/vector multiplication: [x_1] = [[0 1]] [x_0] [x_2] [[a b]] [x_1] Let's name the sequence of vectors as y_n and call the matrix M: y_1 = M * y_0 We can get the next term in the sequence with another multiplication: y_2 = M * y_1 = M * (M * y_0) = M^2 * y_0 By induction we have: y_n = M^n * y_0 M has characteristic polynomial: r^2 - br - a = 0 with roots: r_1 = (b - c)/2 r_2 = (b + c)/2 c = √(b^2 + 4a) Therefore we have by diagonalization: y_n = S * [[r_1^n 0 ]] * S^(-1) * y_0 [[0 r_2^n]] where S is the matrix of eigenvectors. From here, we can finish our existence and uniqueness proofs from the existence and uniqueness of the eigenvalues of M.
- hirvi74 2y agoI wish more textbooks, especially free resources like in the link, would be better about providing more solutions. A book with a lack of solutions tends to create a circular problem for me. Knowing whether my solution is correct or not is dependent on how well I truly understand the concepts. However, if I truly understood the concepts, then I wouldn't need to solve the problem in the first place. How is one supposed to learn without feedback?
- j7ake 2y agoThese days chatgpt can fill the gap surprisingly well for many questions.
- yshklarov 2y agoI wouldn't count on it -- LLMs make lots of errors in reasoning, and errors in solutions are very frustrating to most math students.
- BossingAround 2y agoChatGPT can help with very simple problems that people have already solved online. That said, typically, you can search for the actual solution online without the ChatGPT's possible hallucinations. A better use of LLM is to input your reasoning and ask if it is correct, but even then, you can't rely on the output. Probably the best is to ask on the math side of stack overflow and rely on the kindness of a stranger.
- phforms 2y agoWithout any solutions or even problems to begin with and without having a teacher by your side, I found that LLMs can be a good-enough learning assistant. Of course, you cannot rely on their answers and they sometimes lead you astray, but what works for me is to: - throughout the text, use the LLM to ask questions, generate problems (I haven’t tried this yet, so it might not work very well) and give you hints on how to close the gaps in your understanding - reduce a given problem to the simplest possible case and ask how to solve that (if you want to check if your solution seems plausible) or if it can give you hints on how to approach the problem (when you are stuck) - vary the problem description to see if different approaches are suggested - critically ask questions about the (steps to the) solution or any provided hints (does something seem odd or logically inconsistent?) - other LLMs sometimes give you better answers (or contradict each other), so, if possible, try asking different LLMs the same questions Having this “conversation” with the LLM where you need to critically check everything it says has the added benefit of being more actively engaged with the material as opposed to simply looking up the solution. It may be a huge waste of time if you’re not careful, but I think if you use it intelligently to guide your own thinking, it can be very helpful.
- kisonecat 2y agoThe HN community might be interested in the XML-based tech used to produce this book, namely https://pretextbook.org/ https://pretextbook.org/
- scythmic_waves 2y agoIn fact, I came to the comments to ask. Thank you!
- wiktor-k 2y agoSadly the "source on github" links are broken on https://pretextbook.org/examples.html https://pretextbook.org/examples.html
- yawboakye 2y agohttps://github.com/PreTeXtBook/pretext https://github.com/PreTeXtBook/pretext
- OldGuyInTheClub 2y agoI wish I even liked my field the way the folks who write these free textbooks love theirs.
- ntnbr 2y agoSeems pretty cool, especially for being free! I'm taking a discrete math course very soon at UT so this is nice.
- optbuild 2y ago[dead]
- anonzzzies 2y agoAh, my favorite course in uni. It made me pick both math and ai majors; math for formal verification because I like discrete math so much in my first year.
- tucnak 2y agoIs discrete maths a good starting point if I was interested in cryptography? Certainly better than analysis right?
- brendank310 2y agoYeah it's a building block for understanding number theory well, which is important in cryptography.
- YZF 2y agoOne cool thing about math though is that continuous/analysis concepts and discrete concepts interact with each other. There's a fair bit of calculus in e.g. AoCP. At some point number theory as well. Kind of depends on how deep you want to go. You can learn a lot about cryptography without really needing a very strong mathematical base.
- aeonik 2y agoDefinitely, in fact Cryptography was added on as a trailer to my Discrete Math course.
- aanet 2y agoWhat a lovely resource! Thank you, author. I just wanted to thank all the authors, especially of textbooks, who put their work online, for free. Their dedication shows, and how. It is largely due to these free (and free-ish) resources that many people -- including autodidacts and those with limited resources -- are able to further their education. Authors - know that your efforts are very much appreciated!
- elric 2y agoBit late to the party, but I can warmly recommend "Discrete mathematics with applications" by Susanna Epp. There are a couple of books with similar titles, but the ones by Epp are amazingly well written. An incredible amount of care and attention to detail went into this textbook, and it shows. Excellent for self study. The Math Sorcerer did a video on an older edition, which is just a lovely ode to the book, the man is in love. https://www.youtube.com/watch?v=FPr5-X9nZc4 https://www.youtube.com/watch?v=FPr5-X9nZc4