**Excursions
in Computer Science**

*"I cannot do it without computers"* - William Shakespeare

**Detailed
Course Contents
**

- Modular addition with ashtrays and pebbles.
- Arithmetic with the abacus.
- Erecting perpendiculars with knotted strings in ancient architecture.
- The converse of Pythagoras' theorem and its application to knotted string algorithms.
- Constructions (algorithms) and their proofs of correctness (Euclid).
- Relative computing power of machines (the rigid compass versus the collapsing compass).
- Ancient measures of complexity (number of geometric steps in a construction)
- Erecting perpendiculars with straight edge and compass.
- Application to the highway facility location problem (Heron of Alexandria)

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

- Real, rational, integer and binary numbers (bits and bytes).
- Storing numbers in an electronic digital computer.
- Sorting numbers (merge sort and heap sort).
- Solving equations.
- Computing square roots with Newton's routine.
- The Euclidean factorization algorithm.
- Prime numbers and their generation.
- Defining randomness.
- Generating random numbers.
- Simulating the rolling of dice on a computer.

- Text compression and 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.

- 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).

- 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).

- 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).

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

- 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).

- 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)

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

- A. K. Dewdney,
*The Tinkertoy Computer and Other Machinations*, W. H. Freeman & Co., New York, 1993. - G. T. Toussaint, "A
new
look at
Euclid's second proposition,"
*The Mathematical Intelligencer*, vol. 15, No. 3, 1993, pp. 12-23. - J. Weizenbaum,
*Computer Power and Human Reason*, W. H. Freeman & Co., San Francisco, 1976. - R. M. Baer,
*The Digital Villain*, Addison-Wesley, Reading, Mass., 1972. ().`Good for history of computing, Turing machines, numerical analysis and artificial intelligence` - A. K. Dewdney,
*The Turing Omnibus: 61 Excursions in Computer Science*, Computer Science Press, Rockville, U.S.A., 1989. - R. Rucker,
*Mind Tools*, Houghton Mifflin Co., Boston, 1987. ().`Good for elementary introduction to Turing machines` - 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` - J. G. Brookshear,
*Computer Science: An Overview*, The Benjamin/Cummings Publishing Company, Inc., 1994.