FRSEMUA.0385001  Computational Thought, fall 2011
Dennis Shasha
Tuesdays/Thursdays, 3:304:45. Room 101, Warren Weaver Hall
Office hours: After class on Thursdays
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 problemsolving
techniques (algorithms), and new frontiers such as artificial intelligence,
swarm intelligence, and DNA computing.
Principal Texts
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/high level intuitive explanation)
whereas a clearer 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, contextfree languages, transformational grammars
The (mysterious) adoption of contextfree 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 47:
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. Flipflops. 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 810:
Programming Languages.
Load
A graduated series of examples to teach you the python language.
Problems will begin as exercises
then work up to gameplaying (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:
PuzzleMad 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 1113:
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 workaround.
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.
Alphabeta 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.