G22.2631-001
Computational Thought, fall 2008
Dennis Shasha
Tuesdays/Thursdays, 3-4:45. Room 1013, Warren Weaver Hall
Office hours: After class on Thursdays
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