CS 101: Schedule & Readings
Week 1: Computers and Computation
- Instructors: Prof. Haoqi Zhang and Prof. Jason Hartline
- Monday (9/30/2013): [slides] history, evolution, genetics, societies, the brain, digital computers
- Wednesday (10/2/2013):[slides] theory of computation, universality, duality, Turing machines, halting problem
Consider and answer these questions while you do this week's reading.
- What is a computer? (Is a wristwatch a computer? Is a school of fish a computer? Is your smart (or dumb) phone a computer? Are you a computer?)
- What is computation? (Is keeping time a computation? Is avoiding being eaten by sharks a computation? Is looking up a number in your address book a computation? Is reading and understanding this question a computation?)
- What is not computation? What is not a computer?
- What are other academic fields where computation may play a central role?
- What is "computational thinking"?
- What is the difference between a universal computer and a non-universal computer? Give examples of each. Are you a universal computer? Is your smartphone a universal computer? Is your wristwatch a universal computer?
- If you are a computer and your smartphone is a universal computer, how come your smartphone cannot simulate you?
- Are there limits to what computer can compute?
- What is the relationship between computer programs, computer simulations, and universal computation?
- What is duality and what does it mean to run a computer program with another computer program as its input?
Reading and Media
Articles for the week can be obtained individually from their sources below, by the day, or as a single PDF.
- The Antikythera mechanism: The clockwork computer, Economist, Sep 19th 2002.
- Ian Horswill, What is Computation?, XRDS, March 2012.
- Jeannette Wing, Computational Thinking, CACM, March 2006.
- (skim) Kari and Rozenberg, The Many Facets of Natural Computing, CACM, October 2008.
- (optional) James Grimmelmann, Why Johnny Can't Steam: How video copyright went insane, Ars Technica, October 2012.
- Bernard Chazelle, Could your iPod be holding the greatest mystery in modern science, Math Horizons, April 2006.
- Geoffrey K. Pullum, Scooping the Loop Snooper: a proof that the halting problem is undecidable, Mathematics Magazine, October 2000.