Cheat Sheet

As some feel that LtU is too math bound, there's only one solution for us underachievers - a Theoretical Computer Science Cheat Sheet.

(Most of it is vaguely familiar, as I've taken a lot of math courses over the years. Sadly though I'd need a much longer set of crib notes to jog my memory. Personally I think most CS based math is really simple, but it also is quite terse - much like many PLs.)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

In theory, theory really refers to theory

"Theoretical computer science" is usually complexity in time and space. (This is an unfortunate historical accident, but what can you do if the complexity people claimed the name first.) Accordingly, the cheat sheet is full of integrals, recurrences, Stirling encounters of the 3rd kind... all very useful numerical stuff for approximating and comparing costs of computations.

A cheat sheet for LtU readers should feature lambda calculi, lattice theory, and logics.

That said, who is going to write it? I hands are full...

Looks indeed like one year

Looks indeed like one year of calculus shall be enough to deal with denotational semantics ;)

A comprehensive survey of at least the most important notations ( the syntax ) if not the content ( the semantics ) of PL research is urgently needed. I was actually already thinking about extracting those from a range of articles quoted here at LtU and try to find out if they converge. However I do think this kind of task is an academics job.

Good point

Though a designer still has to be cognizant of computational complexity when designing and implementing PLs. A PL ends up as just another program from the machine's perspective.

About the only thing I could provide at the moment is a cheat sheet for Smulyan's combinator birds.

(probably only need S K I and Turner's B C W).

very useful!

very nice! Next time I have to read a Siggraph article I'll have to whip this out.

Not at all my undergrad course

That material was covered in courses named "Algorithms" and "Discrete Mathematics." In my "Theoretical Computer Science" course we learned about different classes of formal languages (regular, context-free, recursively enumerable), and how to do proofs about them.

lambda math

Very nice reference; however, I also would have expected things like lambda/pi/actor/relational calculus, logic, set theory, etc.

Perhaps we can get a cheat sheet version of Pierce's TAPL.

In any case, such references will be great for the eventual LtU wiki ;)