Home

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.)

By Chris Rathman at 2006-11-29 01:57 | Teaching & Learning | other blogs | 23563 reads

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...

By Albert Y.C. Lai at Wed, 2006-11-29 02:45 | login or register to post comments

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.

By Kay Schluehr at Wed, 2006-11-29 03:35 | login or register to post comments

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).

By Chris Rathman at Wed, 2006-11-29 18:55 | login or register to post comments

very useful!

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

By shavenwarthog at Wed, 2006-11-29 03:59 | login or register to post comments

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.

By steven_h at Wed, 2006-11-29 14:15 | login or register to post comments

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 ;)

By shahbaz at Thu, 2006-11-30 14:31 | login or register to post comments