Goal

Computational technology and methods lie at the core of modern science, commerce, entertainment, and regrettably war. There are very powerful ideas underlying the field that have roots in mathematics, linguistics, engineering, and even philosophy. Some of its greatest inventions were born in cafes or as responses to a puzzle. Some recent algorithmic methods come from studying ants and evolution.

My goal is to teach you to understand computation from the point of view of its history in logic and mathematics, how computers are built from transistors up, the ideas underlying programming languages, computational problem-solving techniques (algorithms), and new frontiers such as artificial intelligence, swarm intelligence, and DNA computing.

Principal Texts

• Natural Computing: DNA, Quantum Bits, and the Future of Smart Machines by Dennis Shasha and Cathy Lazere, publisher: Norton
• The Puzzling Adventures of Dr. Ecco by Dennis Shasha, publisher: Dover
• Professor Scarlet's Notebook by Edward Leonard, Ted Lewis, and Andy Liu with this nice cover
• A web short course on python
• You want to download the python environment from enthought (www.enthought.com). Note that you have to use your academic address to get it. Also anaconda

Optional:

• Computer Science: an overview J. Glenn Brookshear, publisher: Pearson/Addison Wesley
• Learning Python by Mark Lutz and David Ascher, publisher: O'Reilly, 366 pages. You can order this online.
• Mining the Social Web: Analyzing Data from Facebook, Twitter, LinkedIn, and Other Social Media Sites by Matthew Russell. This book uses data mining programs in python to analyze social media. (I haven't ordered this, but hear the book is good.)

Workload/Requirements

You will have weekly assignments of reading, puzzles, and/or programs.

In addition, you will be a scribe (take notes for all members of the course) for two classes during the semester. To see what the product of a scribe is, check out the excellent web site on quantum computing (a subject we will discuss a bit towards the end) where graduate students at MIT were scribes. I'm sure you can do better. (Please take the scribe duty very seriously. If you can't make it, then please get your alternate to take it for you.)

You will make oral presentations two or three times during the semester.

For homeworks, you may work alone or with at most one partner.

There will be quizzes (one or two questions per quiz) but no exams.

Your grade will depend in equal measure on class engagement, quizzes, presentations, and homeworks.

Lateness policy: Late homeworks or project will not be accepted . If you have a medical excuse, then I will simply not count that homework and your grade will be the average over your other work. I will spend some time reviewing the homeworks either the day they are due or the following class. So this is just a question of fairness.

Syllabus in Order

• Week 1: Mathematical sources of computation: how did a paradox spur the invention of modern computation? This is the story of a failure leading to the birth of an entirely new technology. Topics: Russell paradox (read for history/intuitive explanation) whereas a personal but possibly imagined presentation is found here: Russell paradox (math/logic), Frege, Goedel, Turing, undecidability of the halting problem, relationship to the Entscheidungsproblem and implications for general rewriting (Thue systems) and for the logical architecture of computers (stored programs) and viruses. We may also look briefly at Russell's theory of types
  • Dr. Ecco: Spies and Double Agents, Spacecraft Malfunction
• Weeks 2 and 3: Linguistics and computation. Syntax vs. semantics. Chomsky's hierarchy of language descriptions. Finite state automata, context-free languages, transformational grammars The (mysterious) adoption of context-free grammars for computer languages. Fortran and Lisp.
  • Story of John Backus
  • Student presentation: a chapter from Natural Computing
  • Assignment: create your own paradox.
  • Dr. Ecco: Wrong Number.
• Weeks 4-7: Computer Anatomy and Architecture. Electrical properties of resistors and transistors. Construction of inverters, NAND gates out of these components. Boolean logic and algebra. Here is an article about the Sheffer stroke Gates. Flip-flops. Clocked logic. Memory, memory hierarchy. Instructions and circuit implementation. Program counter/Branching. Basic operating system.
  • Reserve book reading (Warren Weaver Hall/Courant Library) Computer Science Illuminated relevant chapter on circuits. Assignments: XOR, XOR with resisters/transistors etc.
  • Dr. Ecco: Tower problem, Rocket Assembly, Circuits checking Circuits, The Camper's Problem, Code Invention
• Weeks 8-10: Programming Languages. Load A graduated series of examples to teach you the python language. Problems will begin as exercises then work up to game-playing (e.g. mastermind, connect4, sudoku, sudokill), a simple operating system that fetches and displays files from the web, and some simple natural language processing.
  • Reserve book reading (Warren Weaver Hall/Courant Library) Computer Science Illuminated relevant chapter on programming languages.
  • Dr. Ecco: Puzzle-Mad Kidnapper
  • Assignment: translation from English to German noun phrases given the basic rules. Presentations on elaborations including plurals, datives, new words and so on.
  • Project: the Eliza program in python/elementary operating system/something else
• Weeks 11-13: Algorithms. Definition. Algorithm/program/process. Graph theory (nodes, edges and what they could represent). Shortest path, minimum spanning tree, min cut/max flow. Methods of solution involving decision trees. Searching. Binary search. Information theoretic "lower bound" arguments. Hashing and the arithmetic work-around. Security for the internet Parallel computing, Amdahl's law.
  • Reserve book reading (Warren Weaver Hall/Courant Library) Computer Science Illuminated relevant chapter on algorithms.
  • Dr. Ecco: Tower of Lego, Flighty Ideas, Subway Layout, The Coach's Dilemma, Maximum Flow, Warehouses and Barrels,
• Week 14: Artificial Intelligence. Knowledge logic, Elementary game theory and social analysis. Decision trees. Alpha-beta pruning. Expert systems. Machine intelligence: try to infer rules. Use of information theory for learning decision trees. The use of simple intelligence for swarms. DNA computing -- what can we do with the principle of complementarity? Computing with viruses.
  • Presentation: Can you make a triangle out of DNA? Walking DNA.
  • Assignment: Use of Cyc for a problem in everyday life.
  • Assignment: try to create a tetrahedron with DNA.
  • Dr. Ecco: Architect's Problem, Knowledge Coordination I, Knowledge Coordination II
• Other topics as time permits.