Hacker News Comments on
Discrete Mathematics with Applications
Hacker News Stories and CommentsAll the comments and stories posted to Hacker News that reference this book.
I am not sure to be honest, but if you want a book with answers, try Discrete Mathematics with Applications by Epp 
It has a very large number of answers in the back, but not all of them. You'll come out ahead even if you only do the problems with an answer as each section has anywhere between 30 to 60 problems. If you want to try every problem (or some of the interesting ones that don't have answers), there's an instructor's manual for 3rd edition. The one I linked is the 4th ed. No problem as the editions 3 and 4 mainly differ in numbering of their sections and chapters, so if you match a chapter from 4 ed to the one in the instructor's manual for 3rd ed, the answers are identical and in the same order. If none of this works for you, either just google the problem or visit MSE  as almost none of the problems in the undergrad books are original and many people before you have asked the same questions many times over.
Note, the price of the book is steep, but I am sure you know of libg3n.
⬐ LordarminiusGreat! Thanks.
My answer to your question is math. Learn to read and write proofs. Any intro to proofs will do: those employed in discrete math, the ones in analysis, the diagram chasing ones, whatever...Working with math proofs will definitely straighten out your thinking and whip your mind into shape.
Some suggestions to get you started:
Book of Proof by Richard Hammack: https://www.people.vcu.edu/~rhammack/BookOfProof/
Discrete Math by Susanna Epp: https://www.amazon.com/Discrete-Mathematics-Applications-Sus...
Mathematical Proofs: A Transition to Advanced Mathematics by Chartrand et al: https://www.amazon.com/Mathematical-Proofs-Transition-Advanc...
How to Think About Analysis by Lara Alcock: https://www.amazon.com/Think-About-Analysis-Lara-Alcock/dp/0...
Learning to Reason: An Introduction to Logic, Sets, and Relations by Nancy Rodgers: https://www.amazon.com/Learning-Reason-Introduction-Logic-Re...
Mathematics: A Discrete Introduction by Edward Scheinerman: https://www.amazon.com/Mathematics-Discrete-Introduction-Edw...
The Real Analysis Lifesaver: All the Tools You Need to Understand Proofs by Rafi Grinberg: https://www.amazon.com/Real-Analysis-Lifesaver-Understand-Pr...
Linear Algebra: Step by Step by Kuldeep Singh: https://www.amazon.com/Linear-Algebra-Step-Kuldeep-Singh/dp/...
Abstract Algebra: A Student-Friendly Approach by the Dos Reis: https://www.amazon.com/Abstract-Algebra-Student-Friendly-Lau...
That's probably plenty for a start.
⬐ mezodgreat, thank you!⬐ agentultraA more graduate-level book but one I found pleasing:
A Logical Approach to Discrete Mathematics: https://www.amazon.com/Logical-Approach-Discrete-Monographs-...
And a more pragmatic approach to the same material (with a lot of cross-over in terms of proof-style, etc):
Programming in the 1990s: http://www.springer.com/gp/book/9780387973821
But one I particularly enjoyed early on was written for liberal-arts level students of maths (who might've been traumatized by maths in the past):
Introduction to Graph Theory: https://www.amazon.com/Introduction-Graph-Theory-Dover-Mathe...
It will actually get you into writing proofs in set theory within the first couple of chapters.⬐ bordercasesOh gosh the equational logic rabbit hole.
To add to the fire: http://mathmeth.com/
This fall I will be teaching the required "Discrete Math for CS course" to about fifty students at the University of South Carolina. Previously I used Epp's book  which in my opinion is an outstanding book but regrettably is $280.44. Many of our students are working minimum wage jobs to make ends meet, and I don't want to make them pay so much if I can at all help it.
Lucky I saw this!!
I do have one reservation though -- many of our students come in with a weaker mathematical background than MIT students; for example we spent several weeks doing proofs by induction (and no other kinds of proofs) and this text doesn't seem to feature a couple of weeks worth of examples.
I think I'll probably go with this and supplement as needed. Really it looks quite wonderful. (And hell, the book seems to be open source which would mean that I could potentially write supplmentary material directly into the book and make my version available publicly as well.)
This thread seems like a particularly good place to solicit advice: experiences with this book or others, what you wished you'd learned in your own undergraduate course on this subject, etc. I've taught this course once before -- I feel I did quite well but I still have room to improve. Thanks!
⬐ sn9A Schaum's book can be a cheap supplement with lots of solved example problems.
For proofs, you can find the free Book of Proof online . It includes solutions to the odd exercises.
Velleman's How to Prove It is also a great text, though not free.
Regarding math pedagogy, I think this post might prove useful .⬐ llzesYou're the type of professor everyone wishes they had. That's so phenomenal you're looking out for your students like this. That and if you end up writing supplementary material for the book.⬐ Sean1708⬐ saycheeseIs it an American thing to force your students to buy textbooks? In Britain (at least at the universities that I know about) there tends to be 2 or 3 recommended texts, of which the library will have several copies, and they're meant for reference when you get stuck rather than learning the entire course.⬐ mvindahlIn Denmark, at least at the uni where I went in the 1990s, courses would use certain books which we were expected to purchase. Also, the university offered access to photocopiers at reasonable rates. Using photocopied books was not officially encouraged, for obvious reasons, but I don't think anyone ever got into trouble on that account. Personally I bought my books.⬐ JemmehYes, in USA you generally have to buy the book. In fact, because our teachers tend to get paid so little here, sometimes they will write a book, and then require the students buy that book to learn out of for the class. While this kind of sucks, I also understand them doing it because they get paid so poorly. The one thing I really hated though were the times we were required to buy a book and then barely used it. Which was often.⬐ clapintonI got through 5 years of Engineering without buying a book. Between a bunch of copies of newer versions, some of older ones, some in English (this was in a Portuguese-speaking country) and some that couldn't be checked out from the library, there was always a copy available.
That was one of the high points of the college I went to, and I sure as hell did not take it for granted.⬐ eximiusI had a fair number of classes I simply did not attend because the material was basically taught from the book, verbatim. Class was only needed if you didn't understand the book. I showed up to turn in the homework, get assigned the next set, and for exams.⬐ reducesufferingAt UC Irvine, almost all CS classes have either: free online textbooks, just suggested textbooks to help read along with the class, or a PDF that is widely distributed between students themselves. Most students end up never buying a $200 CS textbook⬐ jinfiestoLots of instructors assign from books without reproducing the problems for students without books. Hence, it's typically required to have a book for a class. US University libraries will typically have copies of all textbooks used in any university class. Whether or not they have enough copies at any given time is another issue.⬐ wazanatorIt has been my experience that text books are available for checkout but only for two to three hours at a time. That way you can study there at the library and do your homework then return the book.⬐ midwestcodeAlso whether or not they have the updated edition with all questions...
I ran into that problem with my Operating Systems course this semester, I was just going to scan the problems I needed, but then found out they were different since the book was 4 editions behind.>> "the book appears open source"
Yes, these are the terms of the license:
Webpage for the course is here: https://learning-modules.mit.edu/class/index.html?uuid=/cour...
That page includes an email contact for the course; ([email protected]). If you're planning to release an edit, I'd reach out as soon as possible to give them time to get back to you on if they'd be interested in working with you and the best way to do so, since you posting it randomly somewhere on the net would likely do less good in my opinion, but would be a huge help if done with them.⬐ jlyThe textbook prices are ridiculous. I buy a lot of textbooks for personal library/study, and I have found for 'classic' texts that have many editions, going back 2-3 revisions can be super cheap. I have purchased many used from Amazon in great condition for $5-10 that cost $100-200+ new in the latest edition. This might not work for a class, but it's been indispensable for my personal use.⬐ dizzystarI'm not very mathematical, and I was much less mathematical when I worked that book (calc 1, not calc 2 yet, etc).
I found it highly accessible and fun to work through. The concepts are all well-explained and I don't recall anything that would be out of reach for someone with some probability and foundations in classical logic. If they are at discrete math, this book is well withing their reach.
It doesn't teach hard math per se, but how to think in a mathematical way, showing how to break apparently diabolical problems into manageable pieces, and how to reconsider the perspective of the problem, if that makes sense. The book is among the most mind-expanding books I've ever read.
I'm fully autodidact and far from MIT pedigree.⬐ kayoone⬐ dave1629I am interested in which book you are referring to, the Book on Amazon Op lined too or the MIT material linked in this thread ?⬐ dizzystarBook linked in the thread.I used this book for my course at the University of Virginia last semester, https://uvacs2102.github.io/.
The book is terrific, and wonderful that it is available under a CC license. Most students found it accessible. We covered about Chapters 1-8 (and some things not in the book). (This is only the first part of the book, so a much slower pace than the MIT course. Some of this is to have more time for additional background and to go in depth in things, but also that our courses are scheduled with about 2/3 the amount of time per class as an MIT course is.⬐ chrisweeklyhttps://betterexplained.com/ is hands-down the most transformative free resource for understanding math I've ever encountered.⬐ bogomipzI appreciate your practical comments. This particular caught my eye:
>"Previously I used Epp's book  which in my opinion is an outstanding book but regrettably is $280.44."
This is extortionate. What is the justification for a book being priced at nearly $300? This is one book of how many a student will need that semester? Are school's getting a piece of this as well? Is this why such a racket is permitted?
Sorry I know its tangential to your original comment but I would be curios to hear anyone's feedback, especially someone from Europe or elsewhere. I wonder if this pricing is specific to the U.S.⬐ dboreham⬐ pasbesoinPerhaps those of us who seek to make money from entrepreneurial activities should instead wonder at the business skills of people who are able to extract $300 from their customers for a book?⬐ babygoat⬐ dragonwriter"How can I get in on that extorting?"> What is the justification for a book being priced at nearly $300?
It's a product of a capitalist, for-profit producer. The justift for its price is that the market will bear it.⬐ bogomipz⬐ feyman_rIs that a real market though when it is mandated that I must purchase one specific book?
So I don't think your "this is just how capitalism works" argument holds much credibility here.⬐ dragonwriter> Is that a real market though when it is mandated that I must purchase one specific book?
A real market? Absolutely. An idealized free market, no, but real markets never are.
> So I don't think your "this is just how capitalism works" argument holds much credibility here.
This is, in fact, just how capitalism works, and has always worked, in the real world.⬐ bogomipz>"This is, in fact, just how capitalism works, and has always worked, in the real world."
A central tenet of capitalism is a competitive market though. Where is the competition when I am mandated to buy a single book?⬐ dragonwriter> A central tenet of capitalism is a competitive market though
It's true that a lot of the defense of capitalism that was ginned up (long) after the system was described and named by its critics involves invoking all kinds of hokum about markets which are both free and competitive which not only has nothing to do with anything in the history of capitalism, but isn't even all that internally consistent because of the tendency toward monopoly in unregulated markets where producers experience economies of scale (and in some other common cases.)
But this is a (deeply flawed) rationalization of capitalism, not its foundation.⬐ bogomipzAgain I was responding to your comment:
>"The justift for its price is that the market will bear it."
The market will bear it and the market has no choice to bear it are two different things. I have not "rationalized" anything.⬐ dragonwriter> The market will bear it and the market has no choice to bear it are two different things.
With textbooks, there is a choice: go without (either taking the class anyway or not.)
That your perceived cost from going without is higher than the cost of paying for the book is, arguably a sign that the book is priced correctly for value. You seem to think that the book "ought" to be priced by cost to produce as they would be in a perfectly competitive market, but that's very often not a feature of real markets. The pricing is based on conditions in the market, which is very much a real -- if very much not an ideal -- market.⬐ bogomipzDo you actually believe the things you are writing? No, going without a text book is not actually a viable choice if you want to pass a class is it? Are you just trolling?
>"You seem to think that the book "ought" to be priced by cost to produce as they would be in a perfectly competitive market"
Nowhere did I articulate that sentiment at all. There is plenty of room to make a tidy profit without resorting to punitive pricing, even in a captive market.I heard an interesting take on this on the Planet Money podcast. While I still think books are over-priced here, it allowed me to think of different 'forces' that shape book prices: http://www.npr.org/sections/money/2014/10/03/353300404/episo...⬐ jcranmer> This is extortionate. What is the justification for a book being priced at nearly $300? This is one book of how many a student will need that semester? Are school's getting a piece of this as well? Is this why such a racket is permitted?
That is a bit high for textbooks, most textbooks are usually "only" in the realm of $80-160. That said, math textbooks are usually far more expensive than others.
The excuse given for high prices is that there is a strong used book market for college textbooks, as most students sell off their textbooks at the end of the semester, so from the point of view of the publisher, they see only one sale in 5-20. Of course, publishers discovered that the "cure" for this is to release new editions of textbooks with minor updates (most importantly, reorder the questions in the question banks!) every few years to kill off the used textbook market and haven't lowered their exorbitant prices to compensate.
As an undergrad, I did have one semester where my total book costs were about $1000. Most of the semesters, they were more like $500.
Oh, and the prices usually go to lining the publishers' pockets. Not the authors', not the schools'.⬐ bogomipz>"The excuse given for high prices is that there is a strong used book market for college textbooks, as most students sell off their textbooks at the end of the semester, so from the point of view of the publisher, they see only one sale in 5-20."
Right, and couldn't they make up for this by issuing e-Textbooks with lower prices that would much higher volume in terms of sales?
Also I believe the book stores themselves are in this farce, as large percentage of the bookstores are not run by the schools but private companies such as Barnes and Noble and Follet. So they are making out in this scheme as well.⬐ FinnucaneI spent a little time working at Pearson on a textbook project, and yeah, they're pretty profitable, but the up-front costs are enormous. The production budget for the biology book I worked on was $10 million. And that was for a book that would be widely used at the high-school level.
For a math book like this, I'd guess they spent more like a million getting it done. I wouldn't be surprised if it was $50-100K just for the typesetting.⬐ w22116972This book for "International Edition" costs roughly $35 in Asia. ($35 vs. $280)
So I don't believe the reason for "the production budget".
These "International Edition" usually marked by something "Not allowed in USA" slogan.⬐ impendiaYou've gotten me extremely curious. How did they manage to spend $10 million?⬐ gech⬐ digler999Transparency from business, transparency from govt, is a future we can aim for> The production budget for the biology book I worked on was $10 million
Most of that probably went to lobbying public school district administrators to uses Pearson's edition. you know, "greasing the wheels".⬐ tzsThere is something more than just high production costs going on, though, for math books. Consider Apostol's "Calculus". Volume I new is $150-270 on Amazon. Volume II new is $160-270.
These were first published around 1961. A second edition of Volume I was published in 1967, and a second edition of Volume II in 1969. There have been no further editions. The schools that use Apostol today are still using those late '60s second editions.
They were about $20 per volume when I bought them in 1977, which is equivalent to about $80 per volume in today's money.⬐ jcranmerI estimate the "fair" price of a textbook to be around $50-80; math (particularly calculus) is a textbook price I consider to be more naturally expensive, since they tend to cover more material. Your estimation of decades-old textbooks costing about $80 in today's money seems to vindicate that viewpoint.⬐ FinnucaneA book that cost $20 in 1977 and was made to the same standards today--some paper and binding quality, etc.--would probably have to cost at least $100 today retail. Unfortunately, costs for paper and printing have outpaced inflation generally. Most trade books now are printed very cheaply--the paper and binding are crap.$280??!!
I knew prices were "high", but good grief! I guess I really am out of touch.
Glad I held onto my vintage copy. Don't imagine the intervening 20-ish years have added circa $200 (at a guess) of value to the latest edition.⬐ mljoe⬐ devnonymousTextbook prices and college costs in general are amongst the most notable products outpacing inflation.⬐ jinfiesto⬐ chrisperI think basically unlimited borrowing has a lot to do with this.Yes. But why people buy books is what I don't understand. At least for college and if it's not something you want to own for the future.
Throughout most of my semesters I just rented the books. Much cheaper than buying.⬐ richardwhiuk⬐ nathanyoI saw some information the other day which suggested that books can with access codes for online material (tests/exams etc) which was required for the course.
The other perspective is that if tuition is many thousands of dollars a year, then the cost may be not that dramatic.⬐ chrisper⬐ joepvdYeah, when you need an access code you are out of luck. Thankfully many professors don't do that.
In a science major, if you take 4 classes every semester and then you assume that each book costs $250, then that's $1000 right there every semester. That money can be spent for rent and other more high priority stuff.It really is a shame that this is a rational solution.
University text books should be material to get back to later in life, when confronted with a related problem. Part of university education should be a complete book shelf of well-understood books.
This just exemplifies the new nature of university education: An ephemeral experience where the most durable result is debt /cynisism.⬐ chrisperI'd agree with you if a book was $50 and not $250 each. I really cannot justify $250 x 4 (4 classes per quarter /semester) every semester just for the sake of collecting books that I will, to be honest, never look at again. If I have a certain problem I need to revisit, I can find everything online.
There are a few exceptions, of course, which is why I said that buying books that one wants to keep for the future (and also reference it in the future) is fine.
But should I really buy books for general education that I have to take and has nothing to do with my major?⬐ pasbesoinI held onto my books to have as references. Of course, this was back when the ubiquitous Internet and "instant access to everything" was some years away.
Why should I be reduced after leaving an education, to solely what I can remember in my head and what my current circumstances keep refreshed in my mind and memory? Education was an enormous investment not just of money but also of time and effort. It makes sense to me to keep the resources I used at hand; it helps keep my access to that education at hand.
Seen that way, while book prices are ridiculous, that expense as compared to the entire expense not just in money but in time and effort, is relatively small. It's an investment I've made against the future, where the best recollection and use of my education may be paramount.
And... Those prices are simply unfair. For a system that purports to provide its students tools for life -- not just formulae, but ways of thinking and being. To then increase the burden on those students of taking with them the references they used and might wish to retain as part of retaining that education... It seems that their actions in this matter oppose their rhetoric.
Then again, even when prices weren't so high, I saw a lot of my fellow students simply discarding their books -- at the end of semester, not just after graduation. Many people do "move on" and live "in the present."
Except, those people then seem to be the ones who can't recall what they learned, and who don't do as thorough and good a job in their work.
Living in the present, without the full benefit of history. And reacting based upon a more or less vague impression, rather than detailed knowledge.
What, really, do our institutions want us to retain? How do they want us to live our lives. As demonstrated through their actions -- e.g. these book prices -- rather than their rhetoric?
As for electronic copies. I find I read a lot better from printed pages than from screen. And, as others have pointed out, the "legitimate" electronic versions all too often come with electronic leases -- leashes -- with access deniable purposefully or inadvertently at any point in the future.
My Discrete Math book is still as accessible to me, today -- with any particular personal notes of interest and focus I may have added -- as it was when I bought it. I had to pay for it, and I've had to schlep it around. But I've also had to do that with my education, taking up premium space in my gray matter. I paid a lot more for the education; I hope and believe keeping the book handy helps me retain that larger value.
P.S. And I still find that the good books provide me more useful and valuable access to their information than an ever more cluttered and noisy Internet -- for all that their are many gems -- resources and contributors -- on it. These days, if you can only find them.⬐ auggieroseI'd advise people just to get an iPad Pro and get electronic versions of these books. Makes for an eternal and ever growing bookshelf, and has been much cheaper to maintain than my previous physical library.⬐ dwringerI find it much easier to recall details of material I've read in a physical textbook rather than an e-book. The unique cover, weight, texture, etc. of a physical volume provides more context cues that flag the experience of reading as noteworthy, and thus as something that tends to stick out relative to other memories.⬐ sreanThat's the received wisdom, yeah. The party line etc etc. I am not so sure though.
One has to factor in the possibility and ease of losing the device, or rights to the content that I have backed up on the cloud. Way too many people have the ability to intervene between me and the content. I appreciate the convenience of not having to move shit ton of bleached and pulped wood, but then I have to worry less about DRM, some raid in New Zealand, govt ordered deactivation of device, reading something that powers that be may not be to pleased about
I would like to read what the fuck I want with less power on others to influence that.⬐ auggieroseNone of the books in my electronic library comes with DRM ;-)⬐ sreanAs they say, 'small mercies'I took a course that used that textbook last semester and I got the international edition for around $30, and it was the exact same book with less problems.> many of our students come in with a weaker mathematical background than MIT students;
Maybe this would be a better first couple of weeks introduction:
More information about BookBoon:Note, I have no affiliation with BookBoon, I've just found their textbooks/books very useful.
http://bookboon.com/blog/en/bookboon-com/our-mission-and-concept/ http://bookboon.com/blog/en/bookboon-com/about-the-concept-and-books/⬐ primodemusBuy older or used my friend:⬐ trentmbMargaret M. Fleck at UIUC has one for their Discrete Math course:⬐ x0x0I waffle back and forth on my opinion of scihub and genlib, but ffs, $280 plus tax is simply theft. Don't forget the $90 student solutions manual!⬐ mattmanserHonest question, why would you spend weeks doing proof by induction?
Looking it up, I think I did that when I was 16, but I've never used it while programming. I can't see a single benefit to knowing it for programming. Been programming professionally for 12 years now. What am I missing?
Why do you think it's important?⬐ gjm11⬐ NoneIn some sorts of code, you can get a lot of mileage from "loop invariants" and "loop variants". Understanding these is more or less the same as understanding proof by induction.
Whether you are missing anything depends on whether you ever write the sort of code that benefits from this. (Even if you do, you still might not be missing anything. You might be comfortable with loop invariants but not have connected them with proof by induction. Or you might be good at reasoning about these things in other ways that don't involve invariants.)
(You can stop reading here if you're already very familiar with loop variants and invariants.)
Here's the sort of thing I mean by loop variants/invariants. Suppose you're writing a binary search. (Don't write a binary search. Use someone else's that's already had the bugs taken out.) This is basically pretty simple but surprisingly easy to get subtly wrong, which means it's the sort of code it may be useful to write and document in such a way that you have an informal proof of its correctness. Like this:The above is pseudocode in no particular language. Is it correct? Those variants and invariants (1) divide that question in two and (2) provide a strategy for answering the second half of the question. First sub-question: if the (in)variants always hold, does that imply that the code is correct? Second sub-question: do they always hold? (Strategy for second sub-question: proof by induction on array size and/or number of iterations.)
function find(a, x): # find x in sorted array a; return index i such that a[i]==x # or -1 if no such index exists. Takes time at most # proportional to log(#elements). lo,hi = a.index_bounds() while lo<hi: # INVARIANT: min index <= lo < hi <= max index+1 # INVARIANT: if x is in the array then lo <= its index < hi # VARIANT: D := hi-lo reduces to at most D/2 next iteration mid = lo + floor((hi-lo)/2) # may equal lo, can't equal hi if a[mid] == x: return mid # done! if a[mid] < x: lo = mid+1 else: hi = mid # INVARIANT: if x is in the array then lo <= its index < hi # now lo >= hi which means there's nowhere for x to live return -1
The first invariant implies that since mid is always between lo (inclusive) and hi (exclusive) it's safe to access a[mid]. The second, given that it holds at both start and end of the loop body, implies that if we exit the loop then indeed x isn't in the array. The only ways to leave the function are via the return in the middle, which only happens when we have explicitly found x, and via the return at the end, which only happens when x is known to be absent; therefore, if we return anything, we return the right thing. And the variant says that the quantity D, which starts by equalling the number of elements in the array, is reduced by a factor of at least 2 at each step; as it's always a (strictly) positive integer, this implies that the number of steps is at most log_2(n), so the function does return.
(Note that that last bit is more or less a proof by induction on array size that the function always returns.)
So if the invariants hold then the function does the right thing in the right amount of time.
Proving that the invariants hold is the induction-like bit. The first invariant holds at the start (since lo,hi start out being exactly min index and max index + 1). Each time around the loop we replace either lo or hi with something in between the two, so we still have min <= lo <= hi < max+1; and we will exit the loop unless in fact lo<hi. So the first invariant always holds.
The second invariant holds at the start (since lo,hi are bounds on the entire array). Because the array is sorted, our adjustments to lo/hi make this invariant true again for the next time around the loop. So the second invariant holds at the end of the loop -- and of course therefore at the start of the next iteration.
(Note that those were both proofs by induction, though I wasn't super-explicit about the fact.)
The variant works because if we write D = hi-lo and E = floor(D/2) then the new value of D is, depending on which branch of that if we take, either E or D-E-1; note that D-E-1<=E; so new-D <= E <= D/2 as claimed.
It's probably pretty clear what sort of code this is useful for: highly "algorithmic" code that's basically doing something fairly simple but that's tricky to think about and easy to get wrong. If you're writing a language's standard library, or implementing some sort of iterative mathematical algorithm, then you're quite likely to find it useful. The less like that your code is, the less often this technique will be useful to you. (Fairly extreme example: if you are writing a CRUD webapp then it is unlikely that anything you do will benefit from this.)⬐ hackermailman⬐ popcorncolonelAnybody interested in invariants for reasoning about correctness of loops/data structures, CMU has a good set of intro lecture notes here https://www.cs.cmu.edu/~rjsimmon/15122-s16/schedule.html⬐ mattmanserI'm afraid you're not very good at explaining yourself, I've no idea what point you're trying to make.
Sorry to burst your bubble, but any moderately complex LOB CRUD app usually has a large amount of far more complex algos than a binary sort. Your off-hand comment shows a total ignorance of what's involved in writing a LOB CRUD web app.
In my experience, algos are the really easy part of programming. The hard part is managing complexity.⬐ gjm11⬐ garethrees(It looks like you've been downvoted a lot. For what it's worth, it wasn't me.)
I didn't claim that CRUD apps don't have complexity in them. I claimed that CRUD apps don't typically have the sort of thing in them for which this kind of small-scale semi-formal stuff is useful in them. I am happy to stand by that claim; do you actually disagree with it?
I get the impression that you think I was being sniffy about CRUD apps. I wasn't. In particular, (1) I don't think CRUD apps are low-value. There are plenty of CRUD apps that add much more value to the world than almost any piece of code of the sort that invariants are super-helpful for. And (2) I don't think that CRUD apps are easy. Well, doubtless some are, but as you say they commonly have huge amounts of complication in them, of a sort that isn't amenable to the kind of formalized reasoning I was talking about.
To answer the implied question in your first sentence: I wasn't trying to make a point, I was giving an answer to a question you asked, namely why mathematical induction might be important for programmers.
Briefer and more explicit version of that answer: For people writing certain kinds of code, understanding mathematical induction makes it easier to reason about that code via techniques such as loop invariants, which makes it easier to make that code bullet-proof. There are many other kinds of code for which nothing closely related to mathematical induction is of any value at all.
(And, to reiterate lest I set the bee in your bonnet buzzing again: Whether a kind of code benefits from this sort of technique has basically nothing to do with how important it is, or how difficult it is to write overall, or what anyone should think of the people writing it.)⬐ sornaensis> In my experience, algos are the really easy part of programming.
His point is that when you design an algorithm you need to be able to reason about why it works.
Based on the rest of your comments in this thread, it sounds to me like you have something against the mathematical background of CS? Writing code is not the same thing as doing computer science. Plenty of people are perfectly happy doing the former, but CS as an academic discipline is rooted in discrete math so any school that teaches it should also teach the background.⬐ mattmanserAh, the old "but it's not a programming degree, it's about theory". I thought we were past that these days.
Notice how it took you just one sentence to summarise the few hundred words he wrote.
We've a fairly big problem in this industry that "qualified" CS graduates don't actually signal anything about their suitability for the profession. A significant chunk can't even fizzbuzz.
Oh, come on. What sornaensis's one sentence summarizes is ... the one sentence at the start of my comment. It's true that his is shorter; it also gives less information.
(For the avoidance of doubt, that isn't a problem. Since you declared yourself unable to understand what I wrote, it's fair enough to try to simplify it.)
The rest of what I wrote was (1) an answer to your subsidiary question "What am I missing?" plus (2) an explanation of what I was talking about, in case it was stuff you weren't familiar with.
(Of course if I'd known you'd respond as unpleasantly as you did, I wouldn't have bothered trying to be helpful. But at the time I thought you might well be asking a sincere question rather than just wanting to vent about how out of touch those hoity-toity theoreticians are.)(Slightly off topic, but maybe still interesting.) I used to write binary searches like yours, with two tests per iteration:But then I discovered that there's an alternative approach which has only one test per iteration:
while lo < hi: mid = (lo + hi) // 2 if a[mid] == x: return mid elif a[mid] < x: lo = mid + 1 else: hi = mid return -1If comparisons are expensive compared to other operations then this is twice as fast as the variant with two comparisons per iteration. (If comparisons are cheap, as they are if you are searching an array of numbers in a compiled language, then it doesn't make much difference.)
while lo < hi: mid = (lo + hi) // 2 if a[mid] < x: lo = mid + 1 else: hi = mid if lo < len(a) and a[lo] == x: return lo else: return -1It's helpful for truly understanding recursion.⬐ mattmanser⬐ tarsingeIf it's so useful for "truly" understanding it, why do I have to show so many CS educated juniors how to use recursion? Have to point out to them to use it instead of doing crazy nested loops or other stupid solutions to a problem simply solved using recursion?
Given that I obviously don't "truly" understand it, having never done a CS degree.
I'd posit that most CS students don't truly understand recursion, they just vaguely know the theoretical basis behind a practical skill they have no experience in.⬐ babygoatYou can get a CS degree without understanding induction, and you can understand induction without a CS degree.⬐ data4scienceI don't know which languages you and your CS educated juniors ("juniors") use.
While "juniors" = employees subordinate to you & "so many "juniors"" = high turnover & you = positive senior employee & college educated graduates = smart: "posit that most CS students don't truly understand recusion" = False '''Smart, being distinct from intelligent, indicates a propensity to make decisions that maximize benefit for the person described as smart. A smart CS student would work for a company that valued intellectual capital instead of a company with high turnover.'''
While "juniors" = employees subordinate to you & "so many "juniors"" = hyperbole & you = positive senior employee: "posit that most CS students don't truly understand recusion" = False '''It is dubious that more than 171.5k CS graduates worked subordinate to you from 2004-2010, or that an unbiased sample of CS graduates from 2004-2010 worked subordinate to you (see previous While "loop")  .'''
The proof that the previous comment's posit is not provable follows by induction.
Note_0: While loops can use "&" or "and" operators in some languages without nested loops (unless the programmer chooses to implement a break line) to achieve much of the effect of recursive functions. While statements, as implemented in the example above, offer nearly as much access to the input stack as recursive functions; about equal risk of an infinite loop; and don't risk stack overflow.
Note_1: I have a bachelors in Math. So, I was likely taught a more substantial "theoretical basis," and less "practical skill" than the curriculum most CS graduates were taught.⬐ mattmanser⬐ markhkim10 I don't see what you added to the discussion
20 But I have to ask, if you have a bachelors in Maths, why do you not know about sample sizes? Or about the flaws in assuming perfect knowledge of actors in a system?
(on reply, GOTO 10)eh, I posit that you already understand induction and just don't know that you do.
"So many CS educated juniors" being uncomfortable with recursion is not an argument against understanding mathematical induction. Who says they understood induction?They are the basis of recursive algorithms proofs, sure you may not need them for everyday programming but that's different for computer science⬐ jimhefferonYou need it for a follow-on course, Theory of Computation.⬐ naasking> Looking it up, I think I did that when I was 16, but I've never used it while programming.
Any reasoning about loops or recursion requires an implicit understanding of proof by induction. Making it formally explicit seems like a perfectly fine idea.None⬐ bloodbeardimpendia,
I'm currently taking a discrete mathematics class that Applied Discrete Structures by Alan Doerr and Kenneth Levasseur (http://faculty.uml.edu/klevasseur/ads2/). It's freely available, though I recommend steering away from the PDF on their site as it's got quite a few errors that are corrected in the source on Github.⬐ xenihnI'm a big fan of these books:⬐ mindcrimeThere are a number of freely available online resources for proofs & mathematical reasoning. Besides the already mentioned "Book of Proof", try:
For anybody looking for freely available maths related texts online, three great resources are:
I recommend learning discrete mathematics, then data structures and algorithms.
I cannot stress enough how important mathematical foundations is. It'll make everything else much easier to learn. I haven't read the book but heard good things about: https://www.amazon.com/Discrete-Mathematics-Applications-Sus... as a beginner text.
Coursera has multiple offerings on Data Structures / Algorithms -- find one that works best for you.
By doing all of those you'll get a good introductory exposure to the topics.
You should also look at a rigorous course offering of Algorithms. MIT has a few online to view.
Some readings for a beginner are:
https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press... (not beginner level but classic)
After all of this you should be fine with diving into interview books. You'll want to whiteboard solutions and be able to do all the difficult problems. Look into sites like leetcode, glassdoor and be able to do the difficult problems posted there.
⬐ 40acresThanks, there are some good resources here. I rushed through CLRS to help prepare for these interviews but I failed at the phonescreen, which was mostly comprised of Leetcode / Hackerrank type questions. I'll definitely take a look at the coursera course specialization but it seems as though these interviews comprise of a 'programming challenge' type question for the phone screen and more with a focus on data structures, algorithms and system design for the onsite.
These books will kick your teeth in if you're not prepared. You either get a teacher who'll hold your hand or you need to gear up for fight(develop math maturity and learn all the tricks and tips). To the latter end, you can check out the Book of Proof by Richard Hammack and Discrete Math by Susanna Epp.
To start from absolute zero, check out Suzanna Epp's Discrete Math. I believe even a motivated high school student could get started with it and even finish it. If your proof-writing is shaky, the book provides a very good workout. From there it will be easy to choose the areas of discrete math to specialize.
⬐ chris11Thanks, I'll check it out. My proof-writing is definitely shaky. I can clearly see the relationship between programming on writing proofs, but I can't get immediate feedback on the validity of my mathematical proofs like I can with code.⬐ gocQuestions in Epp are by no means unique. If you search MSE, you'll see that every question in Epp has probably been asked and reasked about a thousand times each. That goes for subjects like Real Analysis, Abstract Algebra, Topology as well.
Would somebody please disrupt the textbook publishing industry?
$264.39, for students that work part time jobs at $7.00 an hour (before taxes).
Not only students are angry about this. Professors are angry, and authors are angry too. Bitter fights between professors and publishers are common.
Everybody wants to see the big players in this industry fail. Please, someone, make it happen.
⬐ jeyThis only works because there's a captive audience, and the publisher knows that they can get away with charging anything since the students feel they have no other choice but to buy a copy. Far more specialized textbooks with far smaller audiences are routinely available for much cheaper (e.g. http://amzn.to/1ByBDLG).
The right place to target reform would be professors. They should take a stand to write and use only open textbooks that can be freely downloaded and distributed. This is already common at the research level, but it doesn't seem as common for intro textbooks.⬐ personlurking⬐ rcarrigan87Do you or does anyone know if there's any kind of existing market for pirated textbooks? I'm not a student but if music and films are pirated in large doses, it seems textbooks geared towards the same demographic would be popular.⬐ evincarofautumnYes, textbook piracy is commonplace. When I was a student, I always pirated the textbooks that I could, using the student file sharing service at my university or the Pirate Bay. Eating food and saving my parents’ money were more important to me than having dead-tree copies of textbooks that I would use for ten weeks then never read again.The bigger question may be why do we even still have "textbooks," at least in their traditional form? Are textbooks the optimal way to learn given all the technology we have today? I'm sure there are quite a few start-ups working on this problem.⬐ afontaine⬐ Nicholas_CThat's the main issue, textbooks are not the ideal form of learning for some subjects.
Studies have shown that text is not the ideal format for novices to learn a subject for the first time.
I'm a co-founder at https://www.clutchprep.com and that's what we're tackling. Students go to 300+ student classrooms, don't learn much and then have to rely on a $250 textbook to teach themselves (doesn't work well for most). It's a broken system.
Edit: fixed the link⬐ cgagI think it's pretty hard to find something more efficient than sitting down and reading a textbook and doing the exercises to learn something you actually want to learn.⬐ plojI thought textbooks was a bad fit for me until I started my university studies. Turned out to be the most superior option...⬐ namenotrequiredKhan Academy comes to mind.⬐ theoutlander⬐ cgagFor software related jobs, pretty soon I'm going to start accepting candidates with substantial coursera credits. Furthermore, we'll be looking at courses in related fields.... Epidemiological Modeling in our case. Students who have successfully completed those core courses and have gained actual knowledge will easily come through in the interviews.I think it's pretty hard to find something more efficient than sitting down and reading a textbook.⬐ bcohen5055I'd have to say there is a good use case for textbooks in engineering. Go into any mechanical engineer or chemical engineers cubical and you will find that they all have many of their college textbooks. Textbook chapters are a way better organized than websites when you are looking up values in tables, applying them to equations, and adapting example problems.⬐ prawnThat's not anything that couldn't be solved with a better designed informational website or app. Those textbooks persist only because someone's making a lot of money from making them required parts of a course.Is there no crowd sourced, open sourced textbook non-profit organization? Sort of like Wikipedia/Wikimedia but with textbooks. Ideally there would be a Wiki-like website with people constantly editing and revising and arguing over texts/chapters/paragraphs. A cursory Google search yields the site https://openstaxcollege.org/, which appears to be supported by Rice University. This has open sourced texts, but not crowd sourced.
As a recent graduate I remember shelling out thousands of dollars during my undergrad years to pay for textbooks. It was always a crapshoot because you never knew if the professor would not use the textbook at all or would heavily rely on it and assign reading/problems from the book.
There are definitely ways around purchasing expensive textbooks, but most are illegal, and none are convenient or guaranteed.⬐ ethanhunt_⬐ arjieA wikipedia for textbooks? There's exactly that, though I can't comment on the quality. http://en.wikibooks.org/wiki/Calculus/Limits/An_Introduction...⬐ guynamedlorenI'm trying to do this with Penflip (https://www.penflip.com). It's like GitHub, but for writing. Just like GitHub, there are public and private projects. Anybody can contribute to a public project by submitting a pull request. A big hurdle is that the concept of 'open source' is a bit foreign outside tech, but I think there is some potential.
Here's an open source Java book on Penflip: https://www.penflip.com/lynnlangit/tkp-lesson-plans⬐ ac29I came across this nice looking statistics textbook a couple years ago:
Free online, <$10 in print. There is a high school level stats text book available as well. Its also not "crowd sourced", but the results seem solid.⬐ webmavenYes, several:Students are just pirating the books. If money issues are hindering your education, then it's easy to justify that.
Listen, Uber is an example: Not playing by the rules makes it easier to win and when you do a few will complain about your lack of ethics but only a tiny fraction will make that count against you.
JustFab? You may be upset about dark patterns but people love them. Apple, Google, et. al. intentionally breaking the law? No one cares, people still want to work for them. Intel's illegal anti-competition activities? Microsoft's? People still love them.
No one cares about the guy who worked his ass off so he could afford a book, if that work cut into the time needed to study, leaving him less educated. People celebrate the guy who, having pirated books, was able to concentrate on learning and has the free time to become better at many other things.⬐ TeMPOraLScrew the unversity, at this level people stop buying books anyway; if the book is too expensive, it's better to get a bootleg PDF or just borrow one from a library and xerox it for the whole year. No one cares, you don't need a textbook on lectures anyway.
But please oh please disrupt textbooks for schools. Parents are forced to buy new books every year because of social pressure. After all, you wouldn't want your kid to be known in class as "the one with parents too poor to even buy a textbook" and bullied for it. Not that adults would care about someone having a copied book - but the kids do. Recognition and respect of their classmates is of paramount importance to every kid in the school; publishers know this and they can charge whatever they like, and parents have to pay.⬐ christiangencoI have a side project I started in college for this: http://textbooksplease.com
The big problem I'm facing right now is how to subvert universities requiring super specific and customized versions of their textbooks. I think the solution is a crowdsourced list of textbook alternatives (ie: "your university says you need Biology Harvard Custom Edition, but that book is the same as Biology minus chapters 6 and 11. You can get the generic edition for $11").
That's really just a bandaid, though. A real solution would look something like https://www.boundless.com/ or Khan Academy.⬐ zo1One thing that they did at my university about 5 years ago to disrupt just this. A group of ex-students (I think) setup a container outside the main entrance, across the street. There they bought old textbooks from students that just finished a subject, and then sold it back to the students using it the following year.
Obviously the books changed slightly. But they kept change lists, so you always knew if you had the latest info or not. Sometimes, even the lecturers did this. E.g. "If you have ed4, it's on page 400-403, otherwise it's page 389-392 on the latest edition, etc".⬐ gohrtThere are plenty of less expensive books available for professors who care.⬐ johan_larson⬐ CyranixYes, the problem is that the one picking the book (the professor) isn't the one paying for it (the student).
Some useful discussion here, including indications that cheaper options exist: http://suburbdad.blogspot.ca/2014/08/oer-erps-and-idea.html
Maybe what's required is a company that a) publishes cheap (probably older) textbooks, and b) rouses student organizations to push for their adoption.
Part b) is by far the harder one, and probably doesn't have a technical solution. It's a marketing/consciousness-raising thing.It seems to me that the most powerful opportunity here would be not only to disrupt textbooks but also academic journals; in the process of tackling both areas as a unified problem of knowledge distribution, one might shorten the distance between the latest research and the established curriculum, as well as opening an avenue for better modes of teaching (as per the point made by `rcarrigan87).⬐ untilHellbanned⬐ yumrajWe're working on disrupting academic journals at Onarbor, https://onarbor.com⬐ ac29I really like what PeerJ is doing in that space: https://peerj.com/
Really takes open access (which is great, but still expensive) to the next level. Very inexpensive publishing, and free preprints.I'm currently looking at textbook industry and believe it's a part technology and part business model solution where we can draw from trends in some other industries. We have some ideas but it's a work in progress.
If anyone is interesting in this domain and would like to chat, please ping me. I'm in SF Bay Area, email is in my HN profile.⬐ karatekidd32vCheck out boundless (boundless.com). They offer alternatives to the typical intro college textbooks for $20 each by leveraging open educational resources (OERs).⬐ wellboyChegg is doing this big time and they are already IPOd.⬐ superuser2It doesn't matter that a student can't afford their books on $7/hour. No one seriously expects a kid to make even a dent in the cost of his education anymore, because relative to cost of attendance (except at community colleges) kids in general just don't have the earning power.
Cost of attendance at my state flagship is $24,000. Full time at minimum wage is $15,080. Any education worth that kind of money is hard enough that you physically can't work full time while doing it. Student labor is pretty miniscule as a source of funding.
In other words, $264.39 is not actually 37 hours at McDonalds. It's a rounding error on a parent's 6-figure contribution over 4 years. Or a rounding error in your monthly loan payment when you're making $50k instead of $8k. Or it's coming out of interest on the school's endowment if the school is good enough and your family poor enough. Or it's coming from whoever funds your scholarship if you are one of the handful of people smart enough to get a merit-based full ride. Etc.
(No, your experience of putting yourself through a state flagship in the 80s is not relevant. Minimum wage is roughly what it was; tuition is decidedly not.)
I believe the textbook publishing industry could adapt (or be disrupted) to be more cost-efficient, but you would first have to vastly reconfigure the higher education system such that it's reasonable for students to pay their own way. Then you'd actually have incentives to price things for students.⬐ OlognI take classes at a decently ranked public school, and many of the students are not having tuition paid by scholarship or endowment. Their parents are certainly not paying the full ride - they may contribute a little, if anything. Students can't always get all the loans they would need, and it doesn't make financial sense to pile too much of that on. So plenty of people are paying out of their salaries. I do this and many of the people I speak with do this.
You talk about full-time classes and a full-time job. Actually some of my classmates are raising children or that sort of thing as well. But beyond that, you're correct that it is hard to take a hard STEM major full-time and also work full-time. It would be almost impossible to maintain a 4.0 or 3.9 or whatnot. The solution is obvious, don't take a full course load - take three classes a semester, or perhaps two, or perhaps one. It takes longer, but what is the alternative for those who can't afford full-time study?
If some 18 year old can't really afford full-time study...then don't do full-time study. Why make your parents shell out thousands they can't afford, as well as burdening yourself with enormous loans, for something you may very well not complete in four years. Some kids graduate and are not working - a lot nowadays. On this public school commuter campus, the smarter half of the CS major seniors I know have never heard of software version control, have no idea what git, Perforce, cvs etc. is. Most of our professors are good too - most of them understand their topics, and some are even good at explaining it. A dedicated person can get a lot out of the education, and then perhaps go get a Masters at a more prestigious school afterward if they want.
If people can't afford fulltime, don't go fulltime. Maybe the government should help more, maybe not, but if someone can't pay fulltime they should go parttime.⬐ impendiaA large proportion of my students work part time jobs for 20+ hours a week.
I don't really understand how they can afford tuition + room + board but need the $140 (less taxes) a week, but as it turns out this is very common.
It made a big impression on me when a student walked in to turn in his homework wearing a Chick-Fil-A cap. Asking around, I learned that this is typical at the university where I teach.
So, yes, here at least, $264.39 is 37 hours at McDonalds. Well.... taxes.... so make that more like 50.⬐ sanderjdIt's pretty simple: grants and loans cover tuition, fees, housing, and very little else, so that $150/week from working part time is what students are living off of.⬐ BrandonMWhen I was a working student, I was maximizing my student loans every quarter. My wages were going toward rent, credit card payments, and anything else I couldn't pay with credit cards.
I also worked 40-50 hours per week during the summer. Between that and loan distributions, I could just barely keep up with my typical costs. If anything went wrong--e.g., an injury (yep!), car repairs (yep!), fines (yep!)--the credit card debt didn't get paid off.
You might predict that I would graduate with a lot of debt. You would be right. In spite of having a merit scholarship for full tuition and $4500/year, I had over $35,000 in student loans and another $5000-10,000 in credit card debt when I graduated.⬐ superuser2I also work 20 hours/week, but it's still nowhere close to covering room and board, let alone tuition.⬐ jkimmel>I don't really understand how they can afford tuition + room + board but need the $140 (less taxes) a week, but as it turns out this is very common.
As a student, maybe I can shed a little light on this. There are a few reasons working part-time at minimum wage can make economic sense for a student.
At least at my institution, few kids whose parents foot the tuition bill work.
The students most likely to be working 20 hours/week are the same students likely to receive some form of financial aid/merit scholarship. As such, the tuition + room + board costs may be significantly less than the sticker price. Considering this reduced expense, the ~$200/week from part-time work may make a considerable contribution to a student's budget.
Even if these students aren't able to completely cover the remaining cost of school not covered by financial aid, there are many instances where that part-time job replaces a potentially high interest student loan, reducing the overall cost of education in the long run.
In some instances, even students whose parents assist them with educational expenses require a part-time job for discretionary expenditures. I have more than one friend whose parents pay tuition, but do not cover the cost of gasoline/car repairs necessary for the student to go to class.
I actually just bought Rosen's 'Discrete Math and Applications' on amazon. My college education was in art, so needless to say, not much mathematical training in my undergrad education. In my current job I'm a web developer and I've been trying to cover a CS knowledge base through self study. Through reading reviews about discrete mathematics books I was pointed towards Epps' 'Discrete Math with Applications' http://amzn.com/0495391328 and Rosen's book. I was told Epps' book doesn't go into as much depth, but doesn't assume any prior knowledge from the student. This is great for someone like me with an art degree and the will to learn discrete math. All this is tangentially related to why I'm posting. All of these books mentioned are really expensive, mostly because they are used in college classes. A trick I've started using is buying previous additions of these books for pennies on the dollar. I got Rosen's fifth edition for $7 as opposed to ~$160 for the seventh. After reading the update pages online, I don't think I really miss all that much doing this either.
I really like this book, it start with the very basics: Discrete Mathematics with Applications (http://www.amazon.com/gp/product/0495391328/ref=oh_o04_s00_i...)