Computer Science COMP 199 (Winter term)
Excursions in Computing Science
(or
We Know a Lot More than *Bleep*)

Instructor: T. H. Merrett

"Excursions in Computing Science" explores the role of computing in understanding the universe. So we link up theoretical science, mathematics and computing. Specifically, we look at some of the big ideas in science, such as quantum theory, special relativity, and gene expression; at the supporting mathematical concepts in linear algebra, mathematical logic, and nonlinear attractors; and at computing techniques including data structures, procedural abstraction, and object-orientation.

This course is a dance of science, mathematics and computing, with each of these subjects treated in novel ways, without prerequisites beyond high school.
(A CEGEP graduate may have seen some of the material before, but from a quite different approach.)

The science motivates the mathematics and the computing. The mathematics provides the concepts for the science and the formalisms for the computing. The computing gives experience with the mathematics and predictions for the science; later in the course, advanced computing applications are based on the mathematics. We can understand the science through mathematical analogies, which are better for abstract science than conventional analogies such as waves and particles. The mathematics captures the subtleties; the computing captures the complexities. The mathematics explains the science; the computing explains the mathematics.

The intention of the course is to to be a head start, by experiencing the abstractions by which we do science. We do this by progressing from the science from which the abstractions emerge, to the mathematics which explores the abstractions, to the computing which extracts the predictions and brings the abstractions back to science. Playing the three against each other gives a better grasp than looking at any one of them on its own. We do real science, real math and real computing. The novel way of looking at them will complement the detailed coverage of later, more advanced courses. You will encounter again the abstractions experienced here, and you will be ahead of the game by having experienced them.

COMP 199                                         Excursions in Computing Science

                            COURSE SUMMARY

Part I Time and Spaces
The science discussed is quantum physics and special relativity, with
motivation from and applications to polarized light, quantum electrodynamics
and nuclear physics.
The mathematics covered is the linear algebra of (mainly) two-dimensional
vectors, matrices and tensors, and excursions into higher dimensions, especially
three-dimensional Clifford algebra.
The computing aspect introduces array data structures and operations, functions
as procedural abstraction, some numerical linear algebra in the form of equation
solution, discussion of algorithm complexity and divide-and-conquer, and
applications to graphics, multimedia and Internet search engines. A guest
lecture introduces quantum computing.

Week 1 Polarized Light                                                                             Notes PDF 153K
 Science: building a scientific theory to predict by calculating;
        light through one, two and three polarizing filters.
 Math: trigonometry in a nutshell.
 Computing: programming with MATLAB.

Week 2 Operators                                                                MATLABpak          Notes PDF 160K
 Science: physical measurements and observations as operators;
        polarizing filter as projection.
 Math: vector and matrix products; projection and rotation operators;
       Pythagoras; linear operators.
 Computing: experiencing abstractions through programming; cost and
        complexity of algorithms.

Week 3 Speed of Light                                                           MATLABpak          Notes PDF 120K
 Science: there is a maximum speed for anything; laws of nature are not
        affected by uniform speed; lightspeed is a law of nature;
        the twin paradox.
 Math: fixed-point vectors of transformations; shear transformations;
        determinants; anti-Pythagoras.
 Computing: visualizing transformations by calculating them; procedural
        abstraction.

Week 4 Two-dimensional Numbers and Turtles                                                         Notes PDF 144K
 Science: adding and multiplying arrows; is an imaginary dimension science?
 Math: rotations off the real line - right angle, any angle; the field axioms;
        multiplying rotations is adding angles - exponentials.
 Computing: turtle graphics.

Week 5 Particles with Periods                                                                      Notes PDF 126K
 Science: QED, the strange theory of light and matter; amplitudes and
        probabilities; amplitudes under particle exchange - fermions and bosons.
 Math: 2-numbers give particles frequencies, wavelengths and periods;
        approximate calculation.
 Computing: playing with consequences through programming; errors and artefacts
        of the computation itself.

Week 6 Spin                                                                                        Notes PDF 117K
 Science: polarization states of electrons; half-angles and walking dogs; two
        spin-1/2s make two qbits; two spin-1/2s make one spin-1; fermions and
        bosons;
 Math: matrices of complex numbers; anticommutativity.
 Computing: a preparation for quantum computing.

Week 7 Bonus lectures

 a) E=mc^2                                                                                         Notes PDF 132K
 Science: frequency and wavenumber transform like time and space; energy and
        momentum are frequency and wavenumber; units and dimensional analysis;
        classical limits - E = mc^2; conservation, anti-Pythagoras and nuclear
        fusion and fission; scattering light from electrons - the Compton
        effect; Doppler effect; equations of quantum mechanics.
 Math: practice
 Computing: (small) databases.

 b) invited lecture on quantum computing: Patrick Hayden                                           Notes PDF 209K

 c) Coordinates, angles and reality                                                                Notes PDF 114K
 Science: vectors are real - something is invariant as coordinate systems
        transform; some arrays do not transform like vectors; some real things
        do not transform like vectors; angles, reflections and rotations in 2D
        and 3D.
 Math: tensor products; Clifford algebra [PDF 103K]. 
 Computing: practice

Week 8  Higher dimensions: Sketchpad and Web page rank                          MATLABpak          Notes PDF 198K
 Science: constraint-based graphics for drawing and design; how important is a
        web page? Measuring personality. Surveying and GPS.
 Math: underdetermined and overdetermined linear equations - Lagrange
        multipliers and least-squares; linear approximations to nonlinear
        functions; optimization; eigenvectors and eigenvalues.
 Computing: iterative methods to find an eigenvector, gaussian elimination for
        solving linear systems; parallelization; Sketchpad [Postscript file on constraints in Sketchpad, 110K].

Week 9  Many Dimensions: Data Compression and Content                           MATLABpak          Notes PDF 125K
 Science: image compression and content analysis
 Math: orthogonal vectors in higher dimensions, complex roots of unity, 
	polynomial long division and remainders
 Computing: fast Fourier transform, divide-and-conquer


Part II Logic, Memory and Languages
The scientific aspect is the biology of gene expression. This is related to the
engineering of memory circuits in computers, which motivates this Part.
The mathematics is boolean algebra of logic and combinational circuits and the
nonlinear math of feedback loops and sequential circuits.
The computing covered is iterative techniques to find attractors and cycles in
feedback systems, automata for grammar recognition, expression evaluation, and
memory and state in high-level programming languages. A guest lecture introduces
bioinformatics.

Week 10 The laws of thought                                                                        Notes PDF 126K
Engineering: logic gates, combinational circuits such as adders for a computer,
        and circuit simplification using Karnaugh maps.
Math: axioms of boolean algebra, all possible unary and binary operators on two values,
        universal operators and reversible operators; proof by contradiction.

Week 11 Memory, feedback and automata                                           MATLABpak          Notes PDF 146K
Engineering and science: sequential circuits such as flipflops, control systems,
        gene expression and cell differentiation.
Math: (nonlinear) feedback loops of boolean circuits.
Computing: iteration, simple automata for language recognition, stacks and queues 
        for expression evaluation.

Week 12 Memory and programming language: recursion and instantiation            MATLABpak          Notes PDF 146K
Science: the algorithmic beauty of plants.                                                         Notes PS  498K
Computing: grammars for operator precedence, fractal drawing, encapsulation and
        instantiation of state. (Notes on LISP HTML 3K)
Math: Mathematical induction and proving programs correct.

Week 13 invited lecture on bioinformatics: Mathieu Blanchette