https://sites.google.com/site/mathematicalreasoning3ed/
http://www.math.vt.edu/people/day/ProofsBook/
http://giam.southernct.edu/GIAM/
For anybody looking for freely available maths related texts online, three great resources are:
http://aimath.org/textbooks/approved-textbooks/
http://web.archive.org/web/20170126161813/http://people.math...
For proofs, you can find the free Book of Proof online [0]. 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 [1].
[0] http://www.people.vcu.edu/~rhammack/BookOfProof/
[1] https://bentilly.blogspot.com/2009/09/teaching-linear-algebr...
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.
That was one of the high points of the college I went to, and I sure as hell did not take it for granted.
Yes, these are the terms of the license:
https://creativecommons.org/licenses/by-sa/3.0/legalcode
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.
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.
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.
>"Previously I used Epp's book [1] 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.
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'.
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.
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.
So I don't believe the reason for "the production budget".
These "International Edition" usually marked by something "Not allowed in USA" slogan.
Most of that probably went to lobbying public school district administrators to uses Pearson's edition. you know, "greasing the wheels".
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[1]. So they are making out in this scheme as well.
[1]http://www.businessinsider.com/textbook-publishers-going-aft...
It's a product of a capitalist, for-profit producer. The justift for its price is that the market will bear it.
So I don't think your "this is just how capitalism works" argument holds much credibility here.
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.
A central tenet of capitalism is a competitive market though. Where is the competition when I am mandated to buy a single book?
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.
>"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.
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.
>"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 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.
Throughout most of my semesters I just rented the books. Much cheaper than buying.
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.
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.
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?
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?
Anyway...
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.
The other perspective is that if tuition is many thousands of dollars a year, then the cost may be not that dramatic.
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.
Maybe this would be a better first couple of weeks introduction:
http://bookboon.com/en/gentle-introduction-to-mathematics-fo...
More information about BookBoon:
http://bookboon.com/blog/en/bookboon-com/our-mission-and-concept/
http://bookboon.com/blog/en/bookboon-com/about-the-concept-and-books/
Note, I have no affiliation with BookBoon, I've just found their textbooks/books very useful.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?
Any reasoning about loops or recursion requires an implicit understanding of proof by induction. Making it formally explicit seems like a perfectly fine idea.
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:
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 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.)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.)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] == x:
return mid
elif a[mid] < x:
lo = mid + 1
else:
hi = mid
return -1
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:
lo = mid + 1
else:
hi = mid
if lo < len(a) and a[lo] == x:
return lo
else:
return -1
If 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.)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.
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.
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.
I'd suggest teaching mathematical models instead of showing loops and recursion in practical code is a large chunk of the problem.
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.)
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.)
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.
"So many CS educated juniors" being uncomfortable with recursion is not an argument against understanding mathematical induction. Who says they understood induction?
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") [1] .'''
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.
[1]: http://www.geekwire.com/2014/analysis-examining-computer-sci...
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)
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.
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!
[1] https://www.amazon.com/Discrete-Mathematics-Applications-Sus...