9 ms·

Notes on Discrete Mathematics (2017) [pdf]

334 points by alokrai 8y ago

curiousgal 8y ago
I see notes like these every once in a while and I always wonder, if the material is the same, how come there isn't a unified source for all of it? Why is there a need for every professor to create their own notes that cover the same things? For example, probability theory is still the same after all these years why can't we create a one true reference for people learning it.
- chapium 8y ago
  I have a $250 textbook that not only answers your question, but also has some good insights on the topics referenced in the aforementioned pdf document.
  - vidanay 8y ago
    Discrete Mathematics with Applications by Epp? (I just finished Discrete I & II)
    - chapium 8y ago
      Yup.
    - nobleach 8y ago
      I bought an "only for non-US" version of this book... only to find out it was somehow illegal for me to own it. Doesn't really seem fair. Just because my country is "rich" doesn't mean that I am.
- pfortuny 8y ago
  Because most of the time it is the professor who prefers writing them. At least that is my case. A single source is not better than many.
- hackandtrip 8y ago
  Well, there are books on subjects that are widely used in different countries, Sheldon&Ross for probability, Cormen for Algorithms, etc; Usually a professor choose his own way to teach things, with different example using maybe his own experience in the field, putting more focus into certain things, and students can just do better with a (usually free) reference of what is done in a particular class We can argue if this method, where not every class on the same subject is equal, is good or bad, but till this is what is widely used, it's good for both students and professor to have a reference.
- davidgrenier 8y ago
  Showing the proofs to the theorems taught in university-level math classes is expected. For starter, being that there can be many proofs to the same result you can't expect the teacher to show them all. Opinions also differ on what is valuable and should be taught (you can't teach everything in a finite time), if the teacher can skip some partial result he doesn't find interesting he can opt for a different proof altogether. Thus there'll always be some treasure left for the most ambitious student by tackling various such works.
- wbhart 8y ago
  This is probably an obvious statement, but if you write such a reference, then there will be one more reference, and someone else will have to write a new, more comprehensive reference based on all the existing ones, plus the new one you wrote. And so, on it goes. To answer the question more seriously, there are a number of reasons for this: 1) terminology and notation changes over time, 2) there is not enough space in a standard textbook to include all material on any given subject in mathematics, even at an undergraduate level 3) there have been such standard textbook projects, e.g. the Bourbaki textbooks, but in order to cover everything in complete generality, they had to work at such a high level that the material is all but useless to a beginning student (many French professors may disagree with me on this point). 4) It is not uncommon for textbooks to start with different assumptions, to target the material for certain research applications, to give a different perspective on the material, to promote a favourite notation, to give new proofs or even new theorems, in lecture notes written by professors. What this doesn't answer however, is why there is such a dearth of technological solutions to the problem of disseminating the 40 odd thousand pages of undergraduate mathematics taught around the world today. There are lots of videos at a very superficial level, very few in depth, and piles and piles of books and pdfs. There are virtually zero really well-produced, animated, scripted videos that cover mathematics in great depth. The only reason I can come up with for not having such material is lack of time. Academics, especially professors, who would have to write and edit such material, would have to invest so much time, they would not have time to have families, or do research.
  - mhneu 8y ago
    Teaching styles differ and student populations differ. And re: in-depth, this is a long tail problem. The profit is in the mainstream, not in the tail. Producing really good in-depth work isn’t that rewarding because the market is small.
    - wbhart 8y ago
      I'm still talking about undergraduate mathematics here. There's billions of dollars spent worldwide on providing exactly that. The issue is that a standard undergraduate course, especially in mathematics, is quite deep, relative to, for example, a YouTube "science" video. On the other hand, technology offers new and interesting ways to disseminate this knowledge, but I see very little at the same depth as a standard undergraduate course, which is not just a video of someone doing the equivalent of a chalk-and-talk.
- markhkim 8y ago
  Nobody teaches the same topic in the exactly the same way. There is, for one, far more material in any given subject than an introductory course or textbook can (or should) cover, so the author/instructor must choose what to include. Plus, the order of presentation matters. For example, here are two standard ways of introducing the real numbers: #1 (Dedekind cut). Picture a square of side length 1. The length of the diagonal, √2, cannot be represented by a ratio of integers, so we need a new number system to represent it. These numbers "in between" rational numbers are called irrational numbers, and together they form the real numbers. #2 (Cauchy completion). Non-repeating decimals, such as π ≈ 3.141592, cannot be represented by a ratio of integers. We call such decimal numbers irrational numbers. Any number representable by a (finite or infinite) decimal is called a real number. You can deduce #2 from #1, and vice versa. It's entirely up to the author/instructor to decide which one to start with. Lastly, there is always a better way to explain the same material.
  - mhneu 8y ago
    Nice. I was thinking of real analysis texts as an example here too. Was going to say that not everyone can use Apostol, like Caltech, to teach calculus.
  - facundoq 8y ago
    Besides, books have different levels and audiences. I learned Linear Algebra from three books: 1) Gilbert Strang's "Introduction to Linear Algebra" was great because Gilbert goes straight to intuitions, the proofs are simple, most exercises have answers, but it does not cover advanced material. I used this book for self-teaching. You could probably learn from it with just high-school level maths. Good for engineers. 2) Hoffman and Kunze's "Linear Algebra" was given as a textbook for my first LA course. While it covered some topics that weren't found in many other textbooks and are not really "standard curricula" in many other universities for (jordan normal form, rational canonical form). I found it more similar to a reference than a textbook; it is intended for math majors. The proofs are imho a bit obtuse and it usually introduces topics without much justification. Determinants are introduced early. 3) Axler's "Linear Algebra Done Right" OTOH covered many of the topics in Hoffman&Kunze but the organization and the proofs were (imho) mucho more clear and motivated. Also intended for math majors. No determinants until the end.
- gjm11 8y ago
  Because the material isn't quite the same, and because different people have different teaching and learning styles. The material isn't quite the same because your ideas of what a first-year student needs to learn about probability may differ from someone else's. Not just because your and their prejudices are different: it'll be influenced by what else is in other courses. Imagine two universities with first-year probability courses for their mathematicians. One of them also has a statistics course that everyone takes, the other doesn't. They may make different choices about what goes in the probability course. And it'll be influenced by the students they get. Imagine one of the universities is a very prestigious highly-selective one that lots of good mathematicians apply to, and the other ... isn't. The first will likely want more material in their course. Now, think again about those last two universities. As well as possibly presenting different material, they may well want it presented differently. Fancypants University will want extra-rigorous proofs, connections to other fields of mathematics (measure theory, probabilistic methods in combinatorics, ...), more challenging problems. Slowcoach Polytechnic will want a very clear and straightforward presentation that doesn't leave anything unexplained and doesn't distract students with irrelevancies. So even when they're presenting the same material, the approaches required will be different. Different students will want different things, too. Besides the sort of differences in the previous paragraph (which of course apply between students as much as they do between universities), some students will be interested in the foundations of the subject (what is a probability, anyway?) and some won't; some will be interested in particular kinds of applications; some will like thinking visually and benefit from a lot of digrams, some will find them distracting; etc., etc., etc. Now, with all that in view, imagine you're a professor who's teaching Probability 101 for the first time next year. No matter what, you're going to need to do a lot of thinking about what material you put in your lectures, how you divide it up, how you want to present it, etc. You're going to need some notes for your benefit. (The benefit comes both from making them and from having them.) The extra effort required to polish them up and make them usable by students too is actually pretty small. The fact that other people have presented other similar courses and made similar notes is neither here nor there. You can't just take their notes and avoid all the effort, because their course isn't identical to yours, and their students aren't identical to yours, and their style of presentation isn't identical to yours, and much of the benefit of making the notes comes from actually making them. So, you make your own notes, and then you might as well put them on the internet. And here we are.
- blattimwind 8y ago
  Standard undergrad courses often have kind-of standard literature. In Germany, for example, calculus courses will recommend Heuser. Linear algebra will recommend Beutelspacher. Every EE owns a copy of Tietze & Schenk.
- booleandilemma 8y ago
  Your comment reminds me of this Onion article :) https://www.theonion.com/author-of-introduction-to-algebra-recalls-textbook-be-1823273519/amp https://www.theonion.com/author-of-introduction-to-algebra-r...
- olfactory 8y ago
  Maybe different learning styles? I spoke with one very young math prodigy a few years ago who told me that her secret to self teaching advanced material was that she tries several texts and ends up using the one that teaches the material in the way that she finds most intuitive.
  - fjsolwmv 8y ago
    People say that but usually the truth is the second or third book is the "best" (regardless of which book) but really it's because the material sinks in after multiple itersations, other worse because the material feels familiar even though the student hasn't actually learned to solve problems, they've just memorized bits.
    - bytematic 8y ago
      So how would you solve that problem in a centralized system? I don't think "reread this section 2-3times" would necessary work.
- liaohaohui 8y ago
  Everyone needs to write his or her notes to understand the topic, to include something that he/she feels important. Some people stress the importance of logical flow and theory, whereas some people stress the importance of applications. I believe we all learn by organising knowledge in our own way. So there won't be a single definitive reference text or note.
- baby 8y ago
  I see wikipedia as exactly this.
  - fjsolwmv 8y ago
    Wikipedia is terrible at teaching.
- chatmasta 8y ago
  I took this class, and although I can’t speak for Prof Aspnes, I always imagined he just preferred writing the notes himself (since he can edit them) and might want to publish them into an actual textbook some day. He wrote similarly thorough notes for his Randomized Algorithms class.
- Yhippa 8y ago
  Not sure if anybody else does it this way but sometimes I have to search for multiple sources or explanations of a given topic until I find one that "speaks to me".
floatboth 8y ago
> [Foundations and logic] Why: This is the assembly language of mathematics—the stuff at the bottom that everything else compiles to. > [Basic mathematics on the real numbers] Why: You need to be able to understand, write, and prove equations and inequalities involving real numbers If logic is the assembly, real numbers must be the Enterprise Java frameworks :) But really, aren't they from non-discrete (continuous?) mathematics? How are they useful for computer science? Like, sure we have approximations of them on computers (floats, rationals) but aren't they mostly used for those pesky boring real-world-ish calculations? Isn't CS mostly about integers?
- Eire_Banshee 8y ago
  Yeah, but you got to get that PhD somehow and there are only so many unique topics for your dissertation. Eventually you gotta start reaching!
- markhkim 8y ago
  You can't have calculus without the real numbers, and you can't have asymptotic analysis and probability theory without calculus. There goes the whole field of the analysis of algorithms.
  - fjsolwmv 8y ago
    You can do discrete math (including analysis of algorithms) without reals. Reals are only needed for calculus on infintesimals, which are not relevant to much of CS. Everything you can do with formal Taylor expansions doesn't need reals. In fact knowing calculus on the reals often causes confusion in students learning formal expansions for CS.
    - Ar-Curunir 8y ago
      All of optimization, stats and theoretical ML involves solid grasp of calculus over the reals
- noelwelsh 8y ago
  Doing numerical computation is definitely something that comes up in CS, as well as in applied maths. For example, deep learning is all about basic calculus, and algorithms to do this. Many discrete problems can be posed as a continuous problem, which is usually called a relaxation, and more easily (approximately) solved in the continuous domain.
learner_ 8y ago
Why do most introductory math textbooks not contain solutions? How can a self-learner without access to a university or professor check their work? The common answer I get is solutions "rob" the student of learning. Why should the fear of the lazy student cheat those that actually attempt their work and want to see if their solution is correct? Additionally, I heard the argument that "you should know" if your solutions are correct. A beginner is probably prone to subtle mistakes and may think their reasoning is rational. Thus they are probably unaware of any subtle logic errors and could easily fool themselves into thinking their proofs are correct. Is it partially laziness from the authors in creating new problems for homeworks/exams? Or do people think a literal beginner in math can be their own proof checker? I wouldn't want a beginner programmer writing "production ready" code without code review, so why should we expect a beginner math student to write error free proofs? What is the point in not allowing solutions? As great as these text may be, I couldn't and wouldn't recommend them for the beginner. These text seem to be designed solely for a classroom where students will get assistance and feedback from TAs and professors. They seem useless for a beginner to learn on their own without outside proof checking.
- chalmette 8y ago
  > The common answer I get is solutions "rob" the student of learning. If you study math for some time, you'll realize that people in math community (especially students) like to repeat math related cliches (not necessarily true) over and over again. This is that sort of folk lore. If I were to guess the whys of not including the solutions, I'd say it is to save space as detailed answers to even half the exercises take up considerable space; also "laziness" because writing detailed, explanatory answers is no different from writing the rest of the book. Who wants to do double the work ? :
- ghc35365 8y ago
  Just wanted to add MIT notes on discrete mathematics have the solution manual.
- jimhefferon 8y ago
  > Why do most introductory math textbooks not contain solutions? I offer a couple of Free texts, one of which is pretty popular (http://joshua.smcvt.edu/linearalgebra/ http://joshua.smcvt.edu/linearalgebra/). The answers, completely step-by-step solved, are available. I can give you two reasons. 1) Preparing good questions and giving answers is about half the work. On my page you'll see that the book is 500 pages and the answers are 400 pages. And it is not the half that is fun, or that gets you credit. I find that compiling the answers greatly increases the quality of the book because I keep going back and adjusting the presentation, etc. But others don't think that. Rather the opposite; I have been told that it is work only appropriate for grad students. 2) I have gotten a fair number of emails along the lines of "I'd like to adopt your book but since anyone can download the answers, I cannot teach out of it." It has not in the past proven to be a fruitful strategy for me to inform the email writer that the first thing any 2018 undergrad does on getting a text asignment is to google for the answers pdf, and that those students always succeed. So one reason to not provide answers is to get more adoptions. This ties in with (1) because my five year reviews are not impressed that random self-learners find the text useful. They ask about adoptions.
mlthoughts2018 8y ago
I studied so much discrete math in undergrad. Characteristic polynomials, rook polynomials, derangements, counting, recurrence relations, elementary number theory, elementary p-adic numbers, logic, geometric series, abstract algebra. I have never needed any of it, and never faced a situation where knowledge or intuition in those topics helped me to think differently about a problem, never faced any type of computational complexity questions that I didn’t solve just by looking various things up as-needed. The only thing discrete math did for me was help me boost my GRE math score to get into a good math grad program, where I switched to machine learning and MCMC topics. Very occasionally you might encounter a simple permutation or combination counting argument in a paper or something, but it’s rare. I enjoy discrete math, but really felt misled about it’s actual usefulness in almost any corporate software / research / engineering job. If you don’t know this stuff but you can grok most basic counting arguments after looking a few things up on Wikipedia, you’ll be fine. Deeper command of these topics really doesn’t yield economic returns to your effort in almost all cases, unfortunately.
- noelwelsh 8y ago
  You might see the value of knowing some abstract algebra in "Monoidify! Monoids as a Design Principle for Efficient MapReduce Algorithms" https://arxiv.org/abs/1304.7544 https://arxiv.org/abs/1304.7544 In general, if you can model a distributed or concurrent system in terms of a monoid (or better, a commutative monoid) you're onto a winner.
- fjsolwmv 8y ago
  Sounds like you did a basic pure math curriculum (or minor) at a high-end school, which is probably 4 semesters of extra depth than a computer scientist needs, let alone a programmer. State school applied math / CS does not cover p-adics. Anyway, part of the value isn't in the material itself, but in the practice of learning hard novel ideas, not just the mechanical fundamentals that you could coast through because you are smart, but then hit a wall when you face hard problems later I life.
- bytematic 8y ago
  Do you think you are adequately able to judge how it has benefited yourself?
amai 8y ago
Not complete without some finite calculus: https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20finite%20calculus.pdf https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%...
- mikhailfranco 8y ago
  Thanks for the link, very nice. It also led me to Concrete Mathematics by Knuth, et al ... https://www.csie.ntu.edu.tw/~r97002/temp/Concrete%20Mathematics%202e.pdf https://www.csie.ntu.edu.tw/~r97002/temp/Concrete%20Mathemat...
wiz21c 8y ago
Any analysis aside, the introduction chapter (chap. 1) is really pleasant to read.
chatmasta 8y ago
I took this class. Professor Aspnes is a great teacher and his notes are ridiculously thorough. On the first day of class he told us (paraphrasing) “I never went to class in undergrad, so I don’t expect you to. But the lectures will help you on the problem sets, so I encourage you to attend.” For those of us who may have had... less than thorough attendance... these notes were a real godsend! He also has some for his randomized algorithms class: http://www.cs.yale.edu/homes/aspnes/classes/469/notes.pdf http://www.cs.yale.edu/homes/aspnes/classes/469/notes.pdf And also for his other classes which you can find here: http://www.cs.yale.edu/homes/aspnes/ http://www.cs.yale.edu/homes/aspnes/ (Professor Aspnes is now the DUS of the CS department at Yale)

334 points by alokrai 8y ago

I see notes like these every once in a while and I always wonder, if the material is the same, how come there isn't a unified source for all of it? Why is there a need for every professor to create their own notes that cover the same things? For example, probability theory is still the same after all these years why can't we create a one true reference for people learning it.

chapium 8y ago
I have a $250 textbook that not only answers your question, but also has some good insights on the topics referenced in the aforementioned pdf document.
- vidanay 8y ago
  Discrete Mathematics with Applications by Epp? (I just finished Discrete I & II)
  - chapium 8y ago
    Yup.
  - nobleach 8y ago
    I bought an "only for non-US" version of this book... only to find out it was somehow illegal for me to own it. Doesn't really seem fair. Just because my country is "rich" doesn't mean that I am.
pfortuny 8y ago
Because most of the time it is the professor who prefers writing them. At least that is my case. A single source is not better than many.
hackandtrip 8y ago
Well, there are books on subjects that are widely used in different countries, Sheldon&Ross for probability, Cormen for Algorithms, etc; Usually a professor choose his own way to teach things, with different example using maybe his own experience in the field, putting more focus into certain things, and students can just do better with a (usually free) reference of what is done in a particular class We can argue if this method, where not every class on the same subject is equal, is good or bad, but till this is what is widely used, it's good for both students and professor to have a reference.
davidgrenier 8y ago
Showing the proofs to the theorems taught in university-level math classes is expected. For starter, being that there can be many proofs to the same result you can't expect the teacher to show them all. Opinions also differ on what is valuable and should be taught (you can't teach everything in a finite time), if the teacher can skip some partial result he doesn't find interesting he can opt for a different proof altogether. Thus there'll always be some treasure left for the most ambitious student by tackling various such works.
wbhart 8y ago
This is probably an obvious statement, but if you write such a reference, then there will be one more reference, and someone else will have to write a new, more comprehensive reference based on all the existing ones, plus the new one you wrote. And so, on it goes. To answer the question more seriously, there are a number of reasons for this: 1) terminology and notation changes over time, 2) there is not enough space in a standard textbook to include all material on any given subject in mathematics, even at an undergraduate level 3) there have been such standard textbook projects, e.g. the Bourbaki textbooks, but in order to cover everything in complete generality, they had to work at such a high level that the material is all but useless to a beginning student (many French professors may disagree with me on this point). 4) It is not uncommon for textbooks to start with different assumptions, to target the material for certain research applications, to give a different perspective on the material, to promote a favourite notation, to give new proofs or even new theorems, in lecture notes written by professors. What this doesn't answer however, is why there is such a dearth of technological solutions to the problem of disseminating the 40 odd thousand pages of undergraduate mathematics taught around the world today. There are lots of videos at a very superficial level, very few in depth, and piles and piles of books and pdfs. There are virtually zero really well-produced, animated, scripted videos that cover mathematics in great depth. The only reason I can come up with for not having such material is lack of time. Academics, especially professors, who would have to write and edit such material, would have to invest so much time, they would not have time to have families, or do research.
- mhneu 8y ago
  Teaching styles differ and student populations differ. And re: in-depth, this is a long tail problem. The profit is in the mainstream, not in the tail. Producing really good in-depth work isn’t that rewarding because the market is small.
  - wbhart 8y ago
    I'm still talking about undergraduate mathematics here. There's billions of dollars spent worldwide on providing exactly that. The issue is that a standard undergraduate course, especially in mathematics, is quite deep, relative to, for example, a YouTube "science" video. On the other hand, technology offers new and interesting ways to disseminate this knowledge, but I see very little at the same depth as a standard undergraduate course, which is not just a video of someone doing the equivalent of a chalk-and-talk.
markhkim 8y ago
Nobody teaches the same topic in the exactly the same way. There is, for one, far more material in any given subject than an introductory course or textbook can (or should) cover, so the author/instructor must choose what to include. Plus, the order of presentation matters. For example, here are two standard ways of introducing the real numbers: #1 (Dedekind cut). Picture a square of side length 1. The length of the diagonal, √2, cannot be represented by a ratio of integers, so we need a new number system to represent it. These numbers "in between" rational numbers are called irrational numbers, and together they form the real numbers. #2 (Cauchy completion). Non-repeating decimals, such as π ≈ 3.141592, cannot be represented by a ratio of integers. We call such decimal numbers irrational numbers. Any number representable by a (finite or infinite) decimal is called a real number. You can deduce #2 from #1, and vice versa. It's entirely up to the author/instructor to decide which one to start with. Lastly, there is always a better way to explain the same material.
- mhneu 8y ago
  Nice. I was thinking of real analysis texts as an example here too. Was going to say that not everyone can use Apostol, like Caltech, to teach calculus.
- facundoq 8y ago
  Besides, books have different levels and audiences. I learned Linear Algebra from three books: 1) Gilbert Strang's "Introduction to Linear Algebra" was great because Gilbert goes straight to intuitions, the proofs are simple, most exercises have answers, but it does not cover advanced material. I used this book for self-teaching. You could probably learn from it with just high-school level maths. Good for engineers. 2) Hoffman and Kunze's "Linear Algebra" was given as a textbook for my first LA course. While it covered some topics that weren't found in many other textbooks and are not really "standard curricula" in many other universities for (jordan normal form, rational canonical form). I found it more similar to a reference than a textbook; it is intended for math majors. The proofs are imho a bit obtuse and it usually introduces topics without much justification. Determinants are introduced early. 3) Axler's "Linear Algebra Done Right" OTOH covered many of the topics in Hoffman&Kunze but the organization and the proofs were (imho) mucho more clear and motivated. Also intended for math majors. No determinants until the end.
gjm11 8y ago
Because the material isn't quite the same, and because different people have different teaching and learning styles. The material isn't quite the same because your ideas of what a first-year student needs to learn about probability may differ from someone else's. Not just because your and their prejudices are different: it'll be influenced by what else is in other courses. Imagine two universities with first-year probability courses for their mathematicians. One of them also has a statistics course that everyone takes, the other doesn't. They may make different choices about what goes in the probability course. And it'll be influenced by the students they get. Imagine one of the universities is a very prestigious highly-selective one that lots of good mathematicians apply to, and the other ... isn't. The first will likely want more material in their course. Now, think again about those last two universities. As well as possibly presenting different material, they may well want it presented differently. Fancypants University will want extra-rigorous proofs, connections to other fields of mathematics (measure theory, probabilistic methods in combinatorics, ...), more challenging problems. Slowcoach Polytechnic will want a very clear and straightforward presentation that doesn't leave anything unexplained and doesn't distract students with irrelevancies. So even when they're presenting the same material, the approaches required will be different. Different students will want different things, too. Besides the sort of differences in the previous paragraph (which of course apply between students as much as they do between universities), some students will be interested in the foundations of the subject (what is a probability, anyway?) and some won't; some will be interested in particular kinds of applications; some will like thinking visually and benefit from a lot of digrams, some will find them distracting; etc., etc., etc. Now, with all that in view, imagine you're a professor who's teaching Probability 101 for the first time next year. No matter what, you're going to need to do a lot of thinking about what material you put in your lectures, how you divide it up, how you want to present it, etc. You're going to need some notes for your benefit. (The benefit comes both from making them and from having them.) The extra effort required to polish them up and make them usable by students too is actually pretty small. The fact that other people have presented other similar courses and made similar notes is neither here nor there. You can't just take their notes and avoid all the effort, because their course isn't identical to yours, and their students aren't identical to yours, and their style of presentation isn't identical to yours, and much of the benefit of making the notes comes from actually making them. So, you make your own notes, and then you might as well put them on the internet. And here we are.
blattimwind 8y ago
Standard undergrad courses often have kind-of standard literature. In Germany, for example, calculus courses will recommend Heuser. Linear algebra will recommend Beutelspacher. Every EE owns a copy of Tietze & Schenk.
booleandilemma 8y ago
Your comment reminds me of this Onion article :) https://www.theonion.com/author-of-introduction-to-algebra-recalls-textbook-be-1823273519/amp https://www.theonion.com/author-of-introduction-to-algebra-r...
olfactory 8y ago
Maybe different learning styles? I spoke with one very young math prodigy a few years ago who told me that her secret to self teaching advanced material was that she tries several texts and ends up using the one that teaches the material in the way that she finds most intuitive.
- fjsolwmv 8y ago
  People say that but usually the truth is the second or third book is the "best" (regardless of which book) but really it's because the material sinks in after multiple itersations, other worse because the material feels familiar even though the student hasn't actually learned to solve problems, they've just memorized bits.
  - bytematic 8y ago
    So how would you solve that problem in a centralized system? I don't think "reread this section 2-3times" would necessary work.
liaohaohui 8y ago
Everyone needs to write his or her notes to understand the topic, to include something that he/she feels important. Some people stress the importance of logical flow and theory, whereas some people stress the importance of applications. I believe we all learn by organising knowledge in our own way. So there won't be a single definitive reference text or note.
baby 8y ago
I see wikipedia as exactly this.
- fjsolwmv 8y ago
  Wikipedia is terrible at teaching.
chatmasta 8y ago
I took this class, and although I can’t speak for Prof Aspnes, I always imagined he just preferred writing the notes himself (since he can edit them) and might want to publish them into an actual textbook some day. He wrote similarly thorough notes for his Randomized Algorithms class.
Yhippa 8y ago
Not sure if anybody else does it this way but sometimes I have to search for multiple sources or explanations of a given topic until I find one that "speaks to me".

floatboth 8y ago

> [Foundations and logic] Why: This is the assembly language of mathematics—the stuff at the bottom that everything else compiles to. > [Basic mathematics on the real numbers] Why: You need to be able to understand, write, and prove equations and inequalities involving real numbers If logic is the assembly, real numbers must be the Enterprise Java frameworks :) But really, aren't they from non-discrete (continuous?) mathematics? How are they useful for computer science? Like, sure we have approximations of them on computers (floats, rationals) but aren't they mostly used for those pesky boring real-world-ish calculations? Isn't CS mostly about integers?

Eire_Banshee 8y ago
Yeah, but you got to get that PhD somehow and there are only so many unique topics for your dissertation. Eventually you gotta start reaching!
markhkim 8y ago
You can't have calculus without the real numbers, and you can't have asymptotic analysis and probability theory without calculus. There goes the whole field of the analysis of algorithms.
- fjsolwmv 8y ago
  You can do discrete math (including analysis of algorithms) without reals. Reals are only needed for calculus on infintesimals, which are not relevant to much of CS. Everything you can do with formal Taylor expansions doesn't need reals. In fact knowing calculus on the reals often causes confusion in students learning formal expansions for CS.
  - Ar-Curunir 8y ago
    All of optimization, stats and theoretical ML involves solid grasp of calculus over the reals
noelwelsh 8y ago
Doing numerical computation is definitely something that comes up in CS, as well as in applied maths. For example, deep learning is all about basic calculus, and algorithms to do this. Many discrete problems can be posed as a continuous problem, which is usually called a relaxation, and more easily (approximately) solved in the continuous domain.

learner_ 8y ago

Why do most introductory math textbooks not contain solutions? How can a self-learner without access to a university or professor check their work? The common answer I get is solutions "rob" the student of learning. Why should the fear of the lazy student cheat those that actually attempt their work and want to see if their solution is correct? Additionally, I heard the argument that "you should know" if your solutions are correct. A beginner is probably prone to subtle mistakes and may think their reasoning is rational. Thus they are probably unaware of any subtle logic errors and could easily fool themselves into thinking their proofs are correct. Is it partially laziness from the authors in creating new problems for homeworks/exams? Or do people think a literal beginner in math can be their own proof checker? I wouldn't want a beginner programmer writing "production ready" code without code review, so why should we expect a beginner math student to write error free proofs? What is the point in not allowing solutions? As great as these text may be, I couldn't and wouldn't recommend them for the beginner. These text seem to be designed solely for a classroom where students will get assistance and feedback from TAs and professors. They seem useless for a beginner to learn on their own without outside proof checking.

chalmette 8y ago
> The common answer I get is solutions "rob" the student of learning. If you study math for some time, you'll realize that people in math community (especially students) like to repeat math related cliches (not necessarily true) over and over again. This is that sort of folk lore. If I were to guess the whys of not including the solutions, I'd say it is to save space as detailed answers to even half the exercises take up considerable space; also "laziness" because writing detailed, explanatory answers is no different from writing the rest of the book. Who wants to do double the work ? :
ghc35365 8y ago
Just wanted to add MIT notes on discrete mathematics have the solution manual.
jimhefferon 8y ago
> Why do most introductory math textbooks not contain solutions? I offer a couple of Free texts, one of which is pretty popular (http://joshua.smcvt.edu/linearalgebra/ http://joshua.smcvt.edu/linearalgebra/). The answers, completely step-by-step solved, are available. I can give you two reasons. 1) Preparing good questions and giving answers is about half the work. On my page you'll see that the book is 500 pages and the answers are 400 pages. And it is not the half that is fun, or that gets you credit. I find that compiling the answers greatly increases the quality of the book because I keep going back and adjusting the presentation, etc. But others don't think that. Rather the opposite; I have been told that it is work only appropriate for grad students. 2) I have gotten a fair number of emails along the lines of "I'd like to adopt your book but since anyone can download the answers, I cannot teach out of it." It has not in the past proven to be a fruitful strategy for me to inform the email writer that the first thing any 2018 undergrad does on getting a text asignment is to google for the answers pdf, and that those students always succeed. So one reason to not provide answers is to get more adoptions. This ties in with (1) because my five year reviews are not impressed that random self-learners find the text useful. They ask about adoptions.

mlthoughts2018 8y ago

I studied so much discrete math in undergrad. Characteristic polynomials, rook polynomials, derangements, counting, recurrence relations, elementary number theory, elementary p-adic numbers, logic, geometric series, abstract algebra. I have never needed any of it, and never faced a situation where knowledge or intuition in those topics helped me to think differently about a problem, never faced any type of computational complexity questions that I didn’t solve just by looking various things up as-needed. The only thing discrete math did for me was help me boost my GRE math score to get into a good math grad program, where I switched to machine learning and MCMC topics. Very occasionally you might encounter a simple permutation or combination counting argument in a paper or something, but it’s rare. I enjoy discrete math, but really felt misled about it’s actual usefulness in almost any corporate software / research / engineering job. If you don’t know this stuff but you can grok most basic counting arguments after looking a few things up on Wikipedia, you’ll be fine. Deeper command of these topics really doesn’t yield economic returns to your effort in almost all cases, unfortunately.

noelwelsh 8y ago
You might see the value of knowing some abstract algebra in "Monoidify! Monoids as a Design Principle for Efficient MapReduce Algorithms" https://arxiv.org/abs/1304.7544 https://arxiv.org/abs/1304.7544 In general, if you can model a distributed or concurrent system in terms of a monoid (or better, a commutative monoid) you're onto a winner.
fjsolwmv 8y ago
Sounds like you did a basic pure math curriculum (or minor) at a high-end school, which is probably 4 semesters of extra depth than a computer scientist needs, let alone a programmer. State school applied math / CS does not cover p-adics. Anyway, part of the value isn't in the material itself, but in the practice of learning hard novel ideas, not just the mechanical fundamentals that you could coast through because you are smart, but then hit a wall when you face hard problems later I life.
bytematic 8y ago
Do you think you are adequately able to judge how it has benefited yourself?

amai 8y ago

Not complete without some finite calculus: https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20finite%20calculus.pdf https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%...

mikhailfranco 8y ago
Thanks for the link, very nice. It also led me to Concrete Mathematics by Knuth, et al ... https://www.csie.ntu.edu.tw/~r97002/temp/Concrete%20Mathematics%202e.pdf https://www.csie.ntu.edu.tw/~r97002/temp/Concrete%20Mathemat...

wiz21c 8y ago

Any analysis aside, the introduction chapter (chap. 1) is really pleasant to read.

chatmasta 8y ago

I took this class. Professor Aspnes is a great teacher and his notes are ridiculously thorough. On the first day of class he told us (paraphrasing) “I never went to class in undergrad, so I don’t expect you to. But the lectures will help you on the problem sets, so I encourage you to attend.” For those of us who may have had... less than thorough attendance... these notes were a real godsend! He also has some for his randomized algorithms class: http://www.cs.yale.edu/homes/aspnes/classes/469/notes.pdf http://www.cs.yale.edu/homes/aspnes/classes/469/notes.pdf And also for his other classes which you can find here: http://www.cs.yale.edu/homes/aspnes/ http://www.cs.yale.edu/homes/aspnes/ (Professor Aspnes is now the DUS of the CS department at Yale)