GOALS

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

• Out of their Minds: the lives and discoveries of 15 great computer scientists by Dennis Shasha and Cathy Lazer, publisher: Springer
• 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

Optional:

• Learning Python by Mark Lutz and David Ascher, publisher: O'Reilly, 366 pages.
• Computer Science: an overview J. Glenn Brookshear, publisher: Pearson/Addison Wesley

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.

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

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

• 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, Frege, Goedel, Turing, undecidability of the halting problem, and implications for general rewriting (Thue systems) and for the logical architecture of computers (stored programs) and viruses.
  • Student presentation: Russell's theory of types
  • Dr. Ecco: Spies and Double Agents, Spacecraft Malfunction
• 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.
  • Readings from Out of their Minds : Backus, Rabin.
  • Student presentation: ambiguity of if-then-else expressions.
  • Student presentation: non-deterministic finite state automaton.
  • Assignment: create your own paradox.
  • Dr. Ecco: Wrong Number.
• Computer Anatomy and Architecture. Electrical properties of resistors and transistors. Construction of inverters, NAND gates out of these components. Boolean logic and algebra. Sheffer stroke Gates. Flip-flops. Clocked logic. Memory, memory hierarchy. Instructions and circuit implementation. Program counter/Branching. Basic operating system.
  • Readings from Out of their Minds : Brooks.
  • Optional background from Computer Science: an overview : Chapter 1 through section 1.2. Chapter 3 through section 3.3.
  • Assignments: XOR, XOR with resisters/transistors etc.
  • Dr. Ecco: Rocket Assembly, Circuits checking Circuits, The Camper's Problem, Puzzle-Mad Kidnapper
• Languages. Load A graduated series of examples to teach you the language.
  • Readings from Out of their Minds : McCarthy, Kay
  • Optional background from Computer Science: an overview : Chapter 6, through end of 6.2 and 6.6.
  • Dr. Ecco: Code Invention
  • Assignment: translation from English to German noun phrases given the basic rules. Presentations on elaborations including plurals, datives, new vocabularies and so on.
  • Assignment: the Eliza program.
• Algorithms. Definition. Algorithm/program/process. Searching. Binary search. Information theoretic "lower bound" arguments. Hashing and the arithmetic work-around. Graph theory (nodes, edges and what they could represent). Shortest path, minimum spanning tree, min cut/max flow. Security for the internet Parallel computing, Amdahl's law.
  • Readings from Out of their Minds : Dijkstra, Smith, Hillis
  • Optional background from Computer Science: an overview : Chapter 5 through section 5.5.
  • Dr. Ecco: Tower of Lego, Flighty Ideas, Subway Layout, The Coach's Dilemma, Maximum Flow, Warehouses and Barrels,
• 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 tetrahedron out of DNA?
  • Presentations: stratpal presentation of some area of your expertise.
  • Assignment: Use of Cyc for a problem in everyday life.
  • Assignment: try to create a tetrahedron with DNA.
  • Readings from Out of their Minds : Feigenbaum, Lenat
  • Dr. Ecco: Architect's Problem, Knowledge Coordination I, Knowledge Coordination II