Math ∩ Programming

by robdoherty2 • 13 years ago

282 37 13 years ago

porter• 13 years ago

I was just looking for something like this the other day. What a great way to keep the skills sharp.

It seems there are a lot of gaps in his primers -- he includes topology and some intro to Python, but the actual heart of programming -- algorithms and algorithm techniques -- is mostly missing.

This is of course his right -- it's just a collection of blog posts after all -- but caveat lector.

I would probably go for textbooks instead. Textbooks usually do give a bigger picture in the topics mentioned and they usually have an acceptable learning curve, so no additional primer is required (though as always, googling additional info is a plus).

If you're learning CS, it's often super useful to mix and match two or three textbooks to get a nice picture of things. For example, when you're reading an Algorithms book about graph traversal, it's nice to read a book on graph theory as well. Conversely, several equalities in graph theory can be proven by a simple algorithm (greedy or DFS, for instance).

My personal favourite is mixing up Dynamic Programming (from an Algorithms textbook) with recurrence solving in a discrete math book (which is what DP is actually about) and mixing all that with a more advanced chapter of discrete math -- generating functions.

infrec• 13 years ago

I think there are a lot of gaps within the primers too. With a degree in Mathematics and CS, I can only follow through midway most primers before requiring to find additional sources of information.

That being said, I really like them and I am a big fan of Jeremy's writing.

nikomen• 13 years ago

I agree it would be nice if the gaps in his primers were filled in, but it's to have a resource like this that can help give an understanding of at least some of the topics related to math and programming.

I know from my experiences that trying to read a discrete math or algorithms and data structures textbook can be very daunting. I've also tried viewing the lectures of the algorithms class on Coursera and usually give up because of the difficulty of trying to learn these things after spending 8 hours coding at work. Not having a background in computer science makes this into an uphill battle. Any resource to make this struggle easier is greatly encouraging to me.

doorhammer2• 13 years ago

I have a similar problem. It's really hard to work 8 - 10 hours then come home and try to have the steam to dive into a mathematics or algorithms textbook and go through it in a way that really lets me internalize the material.

Could be that I just haven't found the right books or rhythm for this kind of learning, though. Doesn't help that I'm a pretty disorganized person with my time outside of work, heh.

I've read a few posts on this blog before, and remember enjoying them. I'll have to read a few more. I think it's partly because of how much I hated formal education, and partly because a blog doesn't have the same physical presence as a textbook, but blog posts are less psychologically draining to think about than a book, for me.

pfarrell• 13 years ago

If you're serious about wanting to get better at math, I recommend going to sleep, and getting up earlier. I have done this for a while and find it a great way to have some distraction free focus time. In the end, You need to protect some of your time for your own advancement. It's your responsibility, not your employers. Give it a shot.

ciniglio• 13 years ago

Since it sounds like you've done it a few times, can you recommend some specific textbook combinations which you've enjoyed?

NotOscarWilde2• 13 years ago

Some general hints: don't be afraid to skip. It may happen that some books have an intersection, even though they complement each other -- usually the authors try to be self-contained.

Also, most of the books I mentioned have about 50% dedicated to core ideas in the field and 50% dedicated to some specific tools that may not be that useful to you. More often than not the second 50% is the latter part of the book, but in say Concrete Mathematics it is spread throughout the book entirely. I know it's hard to find the balance between reading fast (and then realizing you don't remember anything from the basic tools and you can't even apply them well) and reading slow (and realizing you're trying to memorize some obscure recurrence involving binomial coefficients). Reading is hard.

Now, for the tips for the CS/discrete math students among you. Feel free to add some of yours, I'm hardly the veteran educator here.

Knuth, Graham, Patashnik's Concrete Mathematics, after a few chapters, goes well with Flajolet, Sedgewick's Analytic Combinatorics. You should mix that up with some Discrete Mathematics introductory book, especially one dealing with counting objects, so you can apply the techniques almost immediately on simpler examples.

Papadimitrou, Dasgupta, Vazirani's Algorithms is one of the better books on algorithms out there, in my opinion. As for the graph theory books I read, I liked Bondy, Murty's Graph Theory style the most, so I'd probably go with that, though I haven't really read them in parallel yet.

For the discrete math students out there, after learning the basics of probablistic method (Alon, Spencer's Probabilistic Method being the seminal textbook, I think), you could continue with both some probabilistic algorithm book to apply what you've learned in CS (I did take a course in that, though, so I can't vouch for the best book out there) and you could also grab Tao, Vu's Additive Combinatorics for how to apply probability in number theory (probabilistic method is chapter one in there).

j2kun4• 13 years ago

Blog author here (all of my friends tell me immediately when I get on HN). I appreciate the criticism.

I'm aware of the huge gaps, and I've had low-priority goals to fill them in. The reason is because my blog is not intended to be a replacement for a standard education, but rather a place for me to explore and write about the stuff that I personally find cool. Usually this means I find an interesting application first, and figure out what background information I should present (admittedly tersely) to support it.

Algorithmic techniques are fine and dandy (I do talk about dynamic programming a few times when it invariably comes up in my applications posts), but more often than not I'm simply bored by the standard algorithms lessons and I believe there's a bigger lack of mathematics background in my audience than algorithmic background. Everyone likely knows (at least vaguely) what a hash table is and what it's for, but asking about a group is more likely to receive blank stares, despite the awesome applications to cryptography.

Though I may be wrong about my audience. I have no way of measuring that except to see what sorts of news sites it shows up on; so far no professional mathematicians have seemed to care except to say the equivalent of "that's a cute hobby."

That being said, I do intend to focus more on graph theory in the future. My own research is taking me more into random graphs, randomized algorithm analysis, and related topics. I also want to start a data structure series, where I go through all of the standard examples: red black trees, prefix trees, fibonacci heaps, etc. I would absolutely love to see more applications of these ideas, and I already have quite a few in mind for graph algorithms.

e12e• 13 years ago

Judging by the article on Bezier curves, I'd say you're doing fine. Very interesting stuff, and a great approach. It even made some linear algebra stuff click for me -- that I should've internalized long ago from my linear algebra class...

cube13• 13 years ago

>My personal favourite is mixing up Dynamic Programming (from an Algorithms textbook) with recurrence solving in a discrete math book (which is what DP is actually about) and mixing all that with a more advanced chapter of discrete math -- generating functions.

This is what makes a "simple" primer on algorithms difficult. In order to prove running time or correctness, you need to have a decent command of basically everything else in that list before you start.

It's relatively simple to understand how Dijkstra's algorithm works by iterating through the steps, but it's much more difficult to prove that it works for a generalized graph. Or prove it's running time.

Algorithm theory is basically the end point of an undergrad CS education. It's the point where you take all the theory you've learned up until that point, and turn it into something that can really be applied to computing.

gizmo686• 13 years ago

Why does proving algorithms involve understanding basically every else. The almost every proof (of correctness) I've seen has been simpler and easier to understand than most of the proof I saw or was asked to do in high school math. Proofs for the running time tend to be trivial (in terms of getting a reasonable big-O, big-Omega. Getting big-Theta is often more difficult, but still tends to be relatively simple).

looki3• 13 years ago

Thanks - I'm currently studying comp. sci. and we have a linear algebra courses in the first two semesters - reading this surely won't hurt.

prezjordan• 13 years ago

Linear algebra is great. It wasn't required for my major, but it really should've been. Definitely check out Salman Khan's videos [0], I found the KhanAcademy selection for linear algebra to be especially helpful. I took a grad course titled "Axiomatic Linear Algebra" and even at that level, the videos were helpful.

[0] https://www.khanacademy.org/math/linear-algebra

looki3• 13 years ago

Thanks! These videos do seem quite useful, I'll make sure to check them out.

jeffasinger• 13 years ago

If you really want to understand the theory behind Linear Algebra, "Linear Algebra Done Right" by Axler is a good choice of book, it's very approachable, but is completely axiomatic.

looki3• 13 years ago

Duly noted! Accepting "doing this will result in this" often just doesn't cut it, and I've been in need of a good source of information. The lectures can be very overwhelming...

ninetax• 13 years ago

Thanks! That stats stuff looks exactly like what I need. I have been really disappointed with my current stats class, and I am actively looking for more computer science related stats stuff. Any suggestions?

I am more looking for places where stats has been applied to CS related problems, rather than the other way around.

j2kun4• 13 years ago

Machine learning sees a lot of stats. See "Elements of Statistical Learning" http://www.stanford.edu/~hastie/local.ftp/Springer/OLD//ESLI... though it may be more advanced (a graduate student friend of mine is reading this right now)

achompas• 13 years ago

I would recommend familiarity with linear algebra before cracking EoSL open.

kyllo• 13 years ago

Bookmarked. Thanks Jeremy, this seems like an excellent reference. I've been taking a few Coursera courses on this subject matter, and this will be a good supplement to that.

tedkalaw• 13 years ago

What communities are best for discussing mathematics when learning? As Jeremy describes in another post (http://jeremykun.com/2013/02/08/why-there-is-no-hitchhikers-...), it's really difficult to learn math without talking to other people. StackExchange seems alright, but are there other good places to ask questions? Maybe an IRC channel?

jckt• 13 years ago

Not exactly a place to ask questions, but this (to me at least) serves as a pretty good Q&A resource: http://www.tricki.org/ "a Wiki-style site that is intended to develop into a large store of useful mathematical problem-solving techniques"

j2kun4• 13 years ago

It's a tough challenge and I don't know of any such (digital) forums. StackExchange does have a chat channel, but last time I visited I saw mostly crickets chirping.

bcuccioli• 13 years ago

I'm idling in freenode ##math always, as long as you observe the etiquette there are extremely smart people who are willing to help.

jimmaswell• 13 years ago

##math on freenode is a good choice.

aditgupta2• 13 years ago

You might find this interesting - http://functionspace.org/discussion/new There is lots of interesting stuff on Math, Physics and Computer Science

P.S -I founded it.

auvrw• 13 years ago

it would be slick if your site could store notes of this sort. perhaps that's what the articles feature is for?

but what about storing notes mainly intended for personal use and referencing in discussions? other users could see these by viewing a profile or following a link in an article or discussion, but such notes wouldn't necessarily appear under a navbar link.

then, after there was this notion of personal space, there could be a feature like the github activity tracker (on saturday you pushed 2 definitions and a lemma), content could be reviewed (so-and-so agrees that this proof is correct), and these notes could be restructured into discussion topics, articles, and whatnot.

mathattack• 13 years ago

As much as people point out things that are missing, I gotta believe that this does fulfill the "Help me get a job" purpose of the posts.

salimmadjd• 13 years ago

Bookmarked! I'm a visual learner and there is not much out there for visual learners. Just a suggestion :)

auctiontheory• 13 years ago

The level seemed mismatched to the audience for a "Primer." I clicked on the Fourier series link. Anyone who needs a basic explanation of a Fourier series doesn't know enough mathematics to understand the explanation provided.

Next looked at the Linear Algebra link - another example of making something much harder than it needs to be. Sorry.

j2kun4• 13 years ago

Did you read up until the part of the Fourier series post that is just calculus? There's some linear algebra stuff at first, but it's just an overview intended for someone who is mathematically inclined.

conradcb• 13 years ago

Just as a quick note: I'm a counterexample to the assertion that anyone who needs a basic explanation of Fourier Series doesn't know enough maths to understand the primer.

I've got a strong (pure) mathematical background (degree in Maths & Philosophy from Oxford), and am now doing a PhD in CS, but my degree was entirely pure maths, and I never did any applied calculus. Admittedly, this isn't a common background, but one of the joys of writing on the internet is that you can write for whatever audience you choose!

Jeremy: thanks very much for providing these primers! For me, they've been great: there are lots of areas of maths which I've not looked at, and for a while I'd been wanting a good introduction to them which was at the right level for me: i.e. mathematically clear, without having to go into too much background, and these have been great at that.

dermutch• 13 years ago

Wow, really nice! I need to catch up on my math work :-)

Math ∩ Programming

Related Stories