Algorithms and Ancient Machines:

Pebbles, the Abacus & the Knotted String

• History of Computing
• Modular Arithmetic
• The Abacus
• The Virtual Museum of Computing

The Straight Edge and Compass

• Euclid's Elements
• Euclid of Alexandria
• More Euclid on the Web
• Relative computing power of machines
• The Collapsing Compass
• The Compass without straight edge (Mohr-Mascheroni)
• Heron's Shortest Path via a Line
• More about Heron of Alexandria

Algorithms and Modern Machines:

• Sir Francis Bacon and the origin of the binary code
• More about Sir Francis Bacon
• Error correcting codes
• Boolean logic
• Boolean logic gates
• Boolean algebra
• Searching the Web with Boolean logic
• More about George Boole
• The Turing machine
• A Turing Machine Java applet simulator
• More about Alan Turing

Processing Numbers:

Creating Order

• Real, rational, integer and binary numbers (bits and bytes)
• Sorting numbers (merge sort and heap sort)
• Solving equations
• Computing square roots with Newton's routine
• The Euclidean factorization algorithm
• Prime numbers (FAQ's)
• Historical introduction to primes
• The Prime Number Home Page

Creating Disorder (Randomness)

• Defining randomness
• Visualizing randomness
• Generating random numbers
• Simulating the rolling of dice on a computer
• Randomness and the Netscape browser

Processing Text:

• Data compression
• Huffman coding
• Introduction to probability and information theory (entropy).
• Markov models of natural language (monkeys and typewriters)
• Spelling correction programs.
• Determining unknown authorship of manuscripts.

Processing Images:

• Tiles, pixels and grids.
• Obtaining grey-level images with a digital camera.
• Obtaining binary images from grey-level images (thresholding).
• Finding connected components in binary images (contour tracing with cellular automata).
• Smoothing images (noise removal).
• Sharpening images (spatial differentiation).

Processing Geometric Objects:

• Polygons: crossing, simple and convex.
• Determining if a point is inside a polygon.
• Smoothing polygons and polygonal waveforms.
• Application to point facility location (minimal spanning circle of a set of points in the plane).
• Application to the convex hull (Jarvis' algorithm).

Data Structures:

• Arrays.
• Linked lists.
• Stacks
• Queues
• Trees.
• Efficient queries and binary search.

Computers as Models of Brains & Intelligence:

• The McCullock-Pitts formal neuron.
• Threshold logic.
• Perceptrons & neural networks (parallel machines).
• Learning algorithms.
• Game trees.
• Decision theory.
• Recognizing patterns (how can a robot tell an orange from a banana).

Computers in Statistics and Exploratory Data-Analysis:

• Graphs and networks.
• The minimal spanning tree and its application to cluster analysis.
• Unsupervised learning.
• Robust estimation of location (onion peeling).

Computer Vision:

• The Hough transform.
• Detecting lines in a digital image with the Hough transform.
• Image segmentation in document analysis.
• Text-line orientation inference in document analysis (another application of the minimal spanning tree).

Computer Networks

• Electronic mail, passwords and privacy.
• Coding theory and cryptography.
• Transposition and substitution ciphers.
• Cryptanalysis (breaking secret codes).
• The Knapsack problem.
• Public-key cryptosystems (the Hellman-Merkle-Diffie cryptosystem)

Computer Graphics and Visualization:

• Turtle geometry.
• Fractals.
• Hidden surface removal.
• The painter's algorithm.
• Virtual reality.

Philosophical, Ethical and Social Implications of Computers:

• Can a computer think? Turing's test.
• Computer art (competition with Mondrian?).
• Law.
• Medicine.
• Computer psychotherapy.

---

Teaching Activities           Homepage

---