Links to fun and useful supplemental material related to 251.

Links will be added progressively over the semester -- links for each lecture, and random links in the Sandbox. Let me know what you think, and please submit links if you find good ones! -Jevan

Lecture 1: Abstract Representation: Your Ancient Heritage

Karl Friedrich Gauss (1777-1855) was quite a character. Besides the story about "Little Gauss" that we heard in lecture, you can also read about how Gauss determined the date of his birth.
Curious about many of the mathematical discoveries of the ancient world? Take some time to learn more about Ancient Egyptian mathematics here.

Lecture 2: Unary, Binary, and Beyond

Minus Zero Logic

How'd you like to program on a machine where you have positive zero and negative zero -- and they aren't equal? Find out what that's like, and learn lots more about various integer representations in this entertaining and informative essay.
+0 + +0= +0
+0 + -0= +0
-0 + +0= +0
-0 + -0= -0

+0 - +0= +0
+0 - -0= +0
-0 - +0= -0
-0 - -0= +0

Lecture 3: Induction: One Step at a Time

Induction is an extremely important technique which you'll continue to use throughout the course. (and which you'll be returning to throughout your career as a CS major). Math Central has some resources on induction. Also read this helpful (and ironically appropriate) analogy which explains induction with a story about Romeo and Juliet.

Lecture 4: On Raising a Number to a Power

Do your addition chains have missing links? Read an explanation of the problem as well as several functions related to it. Also recommended is the survey in The Art of Computer Programming, Volume 2: Seminumerical Algorithms. TAOCP was written by Donald Knuth, also the creator of TeX.

Lecture 5: Is Induction Given by God?

. That funky notation used in lecture is actually common! Check out an explanation of BNF (Backus Naur Form) and some tools that use it (or variants thereof): Lex and Yacc, JavaCC.

Lecture 6: One to One Correspondence and Choice Tree Representation

Texas Hold 'Em -- the game of the world series of poker, and some statistics that every poker player should know by heart. :)

Lecture 7: Counting II: Different Types of Things


Lecture 8: Time Versus Input Size



Lecture 9: Grade School Revisited: How To Multiply Two Numbers

Doubting the improvements of Karatsuba multiplication? Take a look at some performance testing.

Here's another reference to Karatsuba multiplication, in the context of divide and conquer algorithms. You can also read about the growth of functions and the associated notation (O, ). (BTW, if you were wondering why we mix Roman and Greek letters -- the O is really an Omicron!)

Recurrence relations just keep turning up! Read a simple introduction to solving recurrence relations or a more sophisticated version. Also see some common recurrences and their solutions. Recurrences are also used toanalyze the Tower of Hanoi, which you can play here via a Java applet.

Lecture 10: Grade School Again: A Parallel Perspective

Does parallel computation have you beside yourself? The NESL page, part of the CMU SCANDAL project, contains good information on parallel algorithms and how to program them.

Modern computer arithmetic goes far beyond the algorithms you learned in grade school. Check out these simulations of algorithms that processors actually use. Or, if you doubt the importance of the topic, read about some computer arithmetic tragedies.

Boolean circuits are closely linked to the physical hardware of computer arithmetic units as well as to the theoretical analysis of the complexity of parallel algorithms. Read an introduction to logic gates.

IBM's Deep Blue, the computer that beat Garry Kasparov in chess, used massive parallelism to explore possible sequences of moves. IBM's site gives extensive info, but if you'd like to get a little more personal with DB, read this CNN story on his personality, or check out this exclusive interview.

Lecture 11: Pascal's Triangle and Polynomials

Professor Rudich makes reference to Herbert Wilf's book GeneratingFunctionology which is available now for free! A relatively easy read, and provides techniques for solving many common recurrences. (PDF link taken from here).


Lecture 12: Counting in Terms of Proportions

Lecture 13: Counting, Naming and Worst-Case Compression


The Sandbox

MathWorld is back and better than ever! One of the best web resources for math terminology and definitions.'s based on user contributions, so it's sometimes confusing and sometimes wrong. It's supported by Wolfram, so it has a heavy Mathematica influence and copious amounts of sample code. Related sites at ScienceWorld are worth a look too.

Feel like looking at pretty pictures? Check out Robert's Math Figures.

"Set" is a fun mathematical card game published by Set Enterprises. You can play the game online, learn about the mathematics behind it, and check out other interesting links. Other games published by Set Enterprises (and featured on this website) are Quiddler and Five Crowns. (Thanks to Ira Fay for these links.)

If you'd like to experiment with the breaking chocolate bars problem, try this Java applet from Cut the Knot.

Send comments about this page to jsaks@andrew.