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

Handouts for the course can be found in

You are taking this course because you have

- a passion to know how the universe works and how to change it;

- a need to know this right now, not after the next course or after graduation or when you are as old as I am;

- aptitude, demonstrated by high marks in high school mathematics and science.

The course will try to

- answer all the questions you now have about science, math and computing;

(Of course it won't succeed, but ask anyway and the course will get better.)

- leave you with more questions than it answered, so you know you will have lots more to learn during university and beyond;

- most important, allow you to experience the abstractions we use to understand the universe, just as you have, by touch and sight and sound,

been experiencing the surface aspects of nature and artefacts, and came to university to learn more.

We will meet Mondays, Wednesdays and Fridays at 15:30--16:30.

Monday: lecture day. Wednesday: interaction day. Friday: presentation day.

There will be no examinations.

5% of the marks will be for your anticipating the lectures each week with a list, delivered by Sunday night,

of questions and of excursions you would be interested to present.

80 % of the marks will be for work done in the Friday classes:

35% for excursions which you will present;

10% for handouts for your presentations;

30% for your participation in presentations by others

20 % of the marks will be for a journal which you will keep and submit each Sunday.

Note on "experiencing abstractions".

As youngsters, we can experience electricity by trying to build electromagnets, radio by making a crystal set or becoming a ham operator, plants by growing them, animals by training pets, programs by writing them, etc. It is harder to experience the ideas of relativity, which characterize things that move incredibly fast; or of quantum physics, which looks at things incredibly small; or of the processes by which living cells reproduce, manufacture their proteins, make up various organs, play different roles in the body, and evolve, all of which is incredibly complicated.

These ideas are based on abstractions which themselves cannot be handled or experienced with the senses: trigonometry, complex numbers, linear algebra, mathematical logic, feedback systems and nonlinear attractors, even the secrets of processing and memory circuits hidden in integrated circuit chips. We can experience machines by sight and sound and touch, but can we comprehend the full potential of programs ("machines with no physical parts"), unrestricted by gravity, friction, corrosion, weather or wear and tear?

I am grateful for enthusiasm, support and detailed comments variously from Omar Abdulhadi, Fahd Badran, Mathieu Blanchette, Luis Chaidez, Xiao-Wen Chang, Hossam El-Gindy, Frederic Guichard, David Harpp, Patrick Hayden, Don Hetherington, Solomon Li, Fred Mayer, Wolf Rasmussen, Kaleem Siddiqi and Jessica Thompson. Remaining errors and stubbornness are my own.

This course is dedicated to Albert John Coleman, who taught me first-year mathematics and much besides.