Math/CS cheat sheet

Here’s something called a theoretical computer science cheat sheet. I don’t know whether I agree with the name, but it’s a nice cheat sheet.

The first two pages of the cheat sheet have to do with sums, combinatorics, and recurrence relations, the kinds of things you’d find in Concrete Mathematics and certainly useful in theoretical computer science. The chart mentions the “master method” that I blogged about here. But a large part of the cheat sheet is devoted to calculus and other general mathematics not as directly related to computer science.

There’s a nice summary of finite calculus on page 8, a useful little area of math that’s not very widely known.

Thanks to Bill the Lizard for pointing out the cheat sheet.

10 thoughts on “Math/CS cheat sheet

  1. Probability is of critical importance when you get to proving bounds on randomized algorithms.

    All the integral identities, however, are a bit much, but they’re useful in computational geometry sometimes.

  2. Pingback: Adriano J. Holanda » Blog Archive » Theoretical computer science cheat sheet
  3. Great stuff! The scary bit was that I understood about 90% of it!

    LOTS of these seem a bit arcane until you start digging into some oddball problem (I’m doing estimation in discrete probability models) and suddenly you’re butt-deep in things like harmonic functions or rising and falling factorials. So far I’ve avoided the wacky integrals, but some of my derivatives are doozies.

    This is gonna be WALLPAPER in my office.

  4. Mike, I agree. The stuff about rising and falling powers seems arcane, but it’s at the heart of hypergeometric functions which have applications everywhere: physics, statistics, combinatorics, etc.

  5. Matthias Vallentin

    I am creating something similar for probability theory and statistics:

    Probability & Statistics Cheatsheet

  6. You’re quite welcome. I was curious why I was picking up so many new Twitter followers yesterday, and now I know why. 🙂

    I also thought the calculus section was pretty long for a CS cheat sheet. There’s quite a bit more calculus represented than I learned as an undergrad in CS, and that’s one area of math that many of us probably don’t use often after graduation.

    There are quite a few other things of interest on the Programmers SE question What would be a few ideas/concepts from programming that I can have on paper and hang on a wall as art?

  7. Spotted a typo on the matrix section:

    In the equation for det A the sign(pi) should be between the sum and product.

    I made this comment to another blog with a picture and higher google rank, but the comment got deleted 🙁

Leave a Reply

Your email address will not be published. Required fields are marked *