Excursions in Computer Science

"I cannot do it without computers" - William Shakespeare

Detailed Course Contents

Algorithms and Ancient Machines:

  1. Modular addition with ashtrays and pebbles.
  2. Arithmetic with the abacus.
  3. Erecting perpendiculars with knotted strings in ancient architecture.
  4. The converse of Pythagoras' theorem and its application to knotted string algorithms.
  5. The Straight Edge and Compass

  6. Constructions (algorithms) and their proofs of correctness (Euclid).
  7. Relative computing power of machines (the rigid compass versus the collapsing compass).
  8. Ancient measures of complexity (number of geometric steps in a construction)
  9. Erecting perpendiculars with straight edge and compass.
  10. Application to the highway facility location problem (Heron of Alexandria)

Algorithms and Modern Machines:

  1. Sir Francis Bacon and the origin of the binary code.
  2. Decimal to Binary Conversion
  3. Error correcting codes.
  4. The digital computer, logic and truth tables.
  5. Flip-flops and Boolean logic.
  6. Minimal complete Boolean bases.
  7. The Turing machine.
  8. The random access machine (RAM).
  9. Modern measures of complexity (number of arithmetic steps in an algorithm).

Processing Numbers:

  1. Real, rational, integer and binary numbers (bits and bytes).
  2. Storing numbers in an electronic digital computer.
  3. Sorting numbers (merge sort and heap sort).
  4. Solving equations.
  5. Computing square roots with Newton's routine.
  6. The Euclidean factorization algorithm.
  7. Prime numbers and their generation.
  8. Creating Disorder (Randomness)

  9. Defining randomness.
  10. Generating random numbers.
  11. Simulating the rolling of dice on a computer.

Processing Text:

  1. Text compression and Huffman coding.
  2. Introduction to probability and information theory (entropy).
  3. Markov models of natural language (monkeys and typewriters)
  4. Spelling correction programs.
  5. Determining unknown authorship of manuscripts.

Processing Images:

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

Processing Geometric Objects:

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

Data Structures:

  1. Arrays.
  2. Linked lists.
  3. Stacks
  4. Queues
  5. Trees.
  6. Efficient queries and binary search.

Computers as Models of Brains & Intelligence:

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

Computers in Statistics and Exploratory Data-Analysis:

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

Computer Vision:

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

Computer Networks

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

Computer Graphics and Visualization:

  1. Turtle geometry.
  2. Fractals.
  3. Hidden surface removal.
  4. The painter's algorithm.
  5. Virtual reality.

Philosophical, Ethical and Social Implications of Computers:

  1. Can a computer think? Turing's test.
  2. Computer art (competition with Mondrian?).
  3. Law.
  4. Medicine.
  5. Computer psychotherapy.

References

Course Level Material

  1. A. K. Dewdney, The Tinkertoy Computer and Other Machinations, W. H. Freeman & Co., New York, 1993.
  2. G. T. Toussaint, "A new look at Euclid's second proposition," The Mathematical Intelligencer, vol. 15, No. 3, 1993, pp. 12-23.
  3. J. Weizenbaum, Computer Power and Human Reason, W. H. Freeman & Co., San Francisco, 1976.
  4. R. M. Baer, The Digital Villain, Addison-Wesley, Reading, Mass., 1972. (Good for history of computing, Turing machines, numerical analysis and artificial intelligence).
  5. A. K. Dewdney, The Turing Omnibus: 61 Excursions in Computer Science, Computer Science Press, Rockville, U.S.A., 1989.
  6. R. Rucker, Mind Tools, Houghton Mifflin Co., Boston, 1987. (Good for elementary introduction to Turing machines).
  7. D. M. Davis, The Nature and Power of Mathematics, Princeton University Press, Princeton, N.J., 1993. (Good for basic number theory related to cryptography and fractals).
  8. J. G. Brookshear, Computer Science: An Overview, The Benjamin/Cummings Publishing Company, Inc., 1994.
    1. Introduction
    2. Chapter 1: Data Storage
    3. Chapter 4: Algorithms
    4. Chapter 7: Data Structures
    5. Chapter 10: Artificial Intelligence
    6. Chapter 11: Theory of Computation