School of Computer Science
Computer Science COMP 199 (Winter term)
Excursions in Computing Science
We Know a Lot More than *Bleep*)
Instructor: T. H.
"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
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 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
For Grade Scholars and the Young at Heart
Week i Rules and Calculations Notes PDF 308K
Math: some neat numbers and rules for finding them; calculating with letters.
Computing: programming your calculator or MATLAB makes it faster; graphics
turns it into pictures.
Week ii Powers and Trees MATLABpak Notes PDF 737K
Math: numbers can get very big very fast or very small very fast.
Science: from us to the universe in 9 steps; from us to smaller than the atom
in 5 steps.
Computing: searching by using trees upside-down.
Week iii Bases and Polynomials MATLABpak Notes PDF 918K
Math: counting on our fingers; decimals that go on forever; arithmetic on
polynomials and why multiplication etc. work the way they do.
Computing: counting on the computer's "fingers"
Science: the genetic code.
Week iv Space Math Notes PDF 298K
Math: arithmetic on matrices.
Science: rotating and transforming space.
Computing: matrices on the calculator and in MATLAB.
Week v Milli-micro-nano-..math I Notes PDF 260K
Math: functions and their zeros, slopes, square roots,
slope equations, De Moivre's theorem.
Computing: Newton's method, summing (convergent) infinite
Week v Milli-micro-nano-..math II Notes PDF 140K
Math: slopes and antislopes.
Computing: Newton's method for solving equations.
COMP 199 Excursions in Computing Science
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.
A discussion of symmetry introduces the mathematics, and many applications from
molecular vibrations, crystals and wallpaper to the electron structure of the
atom, quarks and the conservation laws of physics.
A discussion of heat introduces the mathematics of distributions and timeseries
and a computer simulation of gas dynamics, leading to the thermostatic
abstractions of entropy, temperature and pressure and to many ramifications
of transport thermodynamics, including Brownian motion, electricity and
thermoelectricity, rheology and chemical reactions. Phase transitions are
introduced with computer simulations rather than mathematically, leading to the
many-scale (fractal) nature of criticality.
Week 1 Polarized Light Notes PDF 365K
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 174K
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 173K
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;
Computing: visualizing transformations by calculating them; procedural
Week 4 Two-dimensional Numbers and Turtles Notes PDF 186K
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;
Computing: playing with consequences through programming; errors and artefacts
of the computation itself.
Week 6 Spin Notes PDF 126K
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
Math: matrices of complex numbers; anticommutativity.
Computing: a preparation for quantum computing.
Week 7 Bonus lectures
a) E=mc^2 Notes PDF 137K
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.
Computing: (small) databases.
b) invited lecture on quantum computing: Patrick Hayden Notes PDF 77K
c) Coordinates, angles and reality Notes PDF 200K
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
Math: tensor products; Clifford algebra [PDF 103K].
Week 8 Higher dimensions: Sketchpad and Web page rank MATLABpak Notes PDF 321K
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].
Book 8c Symmetry: Simplifying Matrices
(This is an extensive treatment of symmetry, a study rich in implications for
science and requiring challenging computations. It will require a couple of
months of dedicated effort, if you are starting from scratch, but this
treatment is self-contained and accessible to anyone prepared to do the work.
Prerequisites from other Weeks in this course are given explicitly when they
This "week" on symmetry was added in 2009 and is not intended, which earlier
Weeks are, to be covered in one week.)
8c Part I Discrete symmetries and molecules MATLABpak Notes PDF 1025K
Math: the mathematics of symmetry - group theory; abstracting groups from
matrices and then representing them back as matrices again.
Science: vibrations of molecules.
8c Part II Infinite symmetries and crystals MATLABpak Notes PDF 1511K
Math: infinite commutative groups in 1D and 2D; wallpaper - point groups and
Science: waves; measuring CD track spacings and crystal atomic spacings.
8c Part III Continuous symmetries and the atom MATLABpak Notes PDF 1172K
Math: rotational symmetry in 2D and 3D; commutators; spherical harmonics.
Science: the electronic structure and fine structure of atoms.
8c Part IV Abstract symmetries and lots of physics MATLABpak Notes PDF 634K
Math: commutator algebra; "special unitary" groups SU(2) and SU(3); Noether's
Science: quarks; Lagrangian and Hamiltonian physics; symmetry and conservation
Computing: cubic and quintic splines.
Week 9 Many Dimensions: Data Compression and Content MATLABpak Notes PDF 280K
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
Book 9c Heat: Histograms and Gases
(This is an extensive treatment of thermodynamics. All the stipulations for
Book 8c above apply here.
This "week" on thermodynamics was added in 2012 and is also not intended to be
covered in one week.)
9c Part I Histograms, etc. Notes PDF 683K
Math: histograms and combining histograms, distributions and moments, normal
distributions (needing antislopes), surprise and ignorance, correlations and
Science: ecology (mutual information in trophic networks) - in the Excursions.
Computing: Bayesian learning.
9c Part II Heat Notes PDF 981K
Computing: kinetic gas and other simulations.
Science: Boltzmann and Maxwell distributions; entropy, temperature and pressure;
thermostatic equations of state; work and heat. A kinetic theory of conflict
(in the Excursions).
Math: slopes of functions of more than one variable. Topology of graphs - in
9c Part III Linear Thermodynamics Notes PDF 1953K
Math: correlations of timeseries and a distribution whose autocorrelation sums
to the mean interval length, convolutions and filters
Science: transport phenomena - intercollision times and distances, and how the
equilibrium autocorrelation filters forces: Green, Kubo and Nyquist, and hence
mobility and diffusion; Brownian motion and Ohm's law; potentials and
dissipation; active transport and membrane biochemistry; Onsager relations and
combined transport (e.g., heat and electric: Seebeck and Peltier effects). In
the Excursions: Kirchhoff circuits, heat conduction, viscosity, elasticity of
solids and crystals, chemical kinetics and affinity of reactions.
9c Part IV. Melt, Boil, Condense, Freeze Notes PDF 518K
Math: random graphs, critical probabilities, and, in the Excursions, power law
Science: critical temperatures, resistance networks, van der Waals gas-liquids,
the Ising model of ferromagnetism, Bose-Einstein condensation, and, in the
Excursions, percolation and renormalization groups.
Computing: simulations everywhere (the systems are not hard to describe
mathematically but solving the math is labourious where not intractable),
double-Newton's method, Z-order for multiple dimensions, and, in the
Excursions, standing ovations as a phase transition.
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
Week 10 The laws of thought Notes PDF 172K
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 207K
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 279K
Science: the algorithmic beauty of plants.
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
Here is the version of this course posted in 2009 .
Handouts for the course can be found in directory ~cs199/handouts (not
on the Web) by readers with accounts on the SOCS (McGill's School of Computer
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;
- enthusiasm for 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
20 % of the marks will be for a journal which you will keep and submit each
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 believe that we can
experience these abstractions by exercising with the experiences we already
have, that they are abstracted from. This course aims to build up chains of
ideas of increasing abstraction and power by alternatively abstracting from
experience then experiencing the abstraction.
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, Gabriel Marleau, Fred Mayer, Jake McKinnell, Wolf Rasmussen, Kaleem
Siddiqi, Jessica Thompson and Rigel Zifkin. Remaining errors and stubbornness
are my own.
This course is dedicated to the memory of Albert John Coleman, who taught me
first-year mathematics and much besides.