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!
Lecture 1: Abstract Representation: Your Ancient
||Curious about many of the mathematical discoveries
of the ancient world? Take some time to learn more about Ancient Egyptian
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)
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.
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,
Lecture 6: One to One Correspondence
and Choice Tree Representation
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
Lecture 9: Grade School Revisited: How To Multiply
||Doubting the improvements of Karatsuba multiplication?
Take a look at some performance
|Here's another reference to Karatsuba multiplication,
in the context of
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!)
Lecture 10: Grade School Again: A Parallel Perspective
||Does parallel computation have you beside yourself?
page, part of the CMU SCANDAL project, contains good information on parallel
algorithms and how to program
|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.|
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
story on his personality, or check out this exclusive interview.
Lecture 11: Pascal's Triangle
Professor Rudich makes reference to
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
back and better than ever! One of the best web resources for math terminology
and definitions. Beware...it'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.
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
(Thanks to Ira Fay for these links.)
||If you'd like to experiment with the breaking
chocolate bars problem, try this
applet from Cut the Knot.
Send comments about this page to jsaks@andrew.