McGill University
School of Computer Science

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.



Table of Contents
TOC PDF 109K

                 For Grade Scholars and the Young at Heart

Week i Rules and Calculations                                                                     Notes PDF 406K
 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 740K
 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 299K
 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 280K
  Math: functions and their zeros, slopes, square roots,
  slope equations, De Moivre's theorem.
  Computing: Newton's method, summing (convergent) infinite
  series.

Week v Milli-micro-nano-..math II                                                                  Notes PDF 185K
  Math: slopes and antislopes.
  Computing: Newton's method for solving equations.


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.
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 space travel introduces propulsion via momentum conservation
and the rocket equation, orbits via conic sections and further conservation
laws, and some of the issues confronting humans in space, including
extraterrestrial intelligence and preserving "spaceship Earth".
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 397K
 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 175K
 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 195K
 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 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;
        approximate calculation.
 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
        bosons;
 Math: matrices of complex numbers; anticommutativity.
 Computing: a preparation for quantum computing.

Week 7 Bonus lectures

 a) E=mc^2                                                                                         Notes PDF 145K
 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 77K

 c) Coordinates, angles and reality                                                                Notes PDF 341K
 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] AKA Reflection algebra [PDF 119K].
 Computing: practice

Week 8  Higher dimensions: Sketchpad and Web page rank                          MATLABpak          Notes PDF 324K
 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
are needed.
 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 1067K
 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
       space groups.
 Science: waves; measuring CD track spacings and crystal atomic spacings.

     8c Part III Continuous symmetries and the atom                             MATLABpak          Notes PDF 1173K
 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 658K
 Math: commutator algebra; "special unitary" groups SU(2) and SU(3); Noether's
       theorem.
 Science: quarks; Lagrangian and Hamiltonian physics; symmetry and conservation
       laws.
 Computing: cubic and quintic splines.

Book 8d Rocket Science
(This is a discussion of space travel. All the stipulations for Book 8c above
apply here.
 This "week" on rocket science was added in 2021 and is also not intended to be
covered in one week.)

     8d Part I Propulsion                                                                          Notes PDF 175K
 Science: momentum conservation, kinetic energy, Boltzmann and Planck constants,
       force and acceleration, pressure.
 Engineering: rocket equation; specific impulse; chemical, electric and nuclear
       rockets; Z-pinch fusion; multistage rockets; photon sails.

     8d Part II Orbits                                                                             Notes PDF 966K
 Math: equations of circles and ellipses, Pythagoras, algebra, radians, conic
       sections (parabolas and hyperbolas).
 Science: centrifugal force, Newton's constant, solar planets, velocities in
       elliptical orbits (vis viva equation), conservation of momentum and
       energy, potential energy, orbital resonances (Jupiter's moons, Saturn's
       rings), tides, angular momentum, moment of inertia, Lagrange stable
       points, Coriolis force.
 Engineering: transfer orbit; delta-V to change orbits; delta-V to launch;
       interplanetary trip times, delta-V and energies; gravity assisted
       delta-V.

     8d Part III The Space Adventure                                                               Notes PDF 744K
 Handwaving: economic forecast of space exploration timeline.
 Engineering: artificial gravity, radiation shielding, space elevator,
       geosynchronous orbit, artificial ecology, slef-reproducing machine,
       radio antennas.
 Science: centrifugal acceleration, grays and sieverts, cooperating swarms,
       specific tension, population growth, genetics and inbreeding, SETI
       (search for extraterristrial intelligence), photon energy.

     8d Part IV Spaceship Earth                                                                    Notes PDF 1.3M
 Science: motion of solar system, mass extinctios, climate change: ice cores
       and isotope layers, greenhouse gases, blackbody radiation (Wien's and
       Stefan's laws), feedback, albedo, PETM (paleocene-eocene thermal
       maximum).
 Handwaving: "herd science", Clean Air Act, Montreal Protocol.

     8d Appendix Trig and Cal                                                                      Notes PDF 104K
 Math: trigonometry, integral calculus, differential calculus.

Week 9  Many Dimensions: Data Compression and Content                           MATLABpak           Notes PDF 313K
 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 701K
 Math: histograms and combining histograms, distributions and moments, normal
 distributions (needing antislopes), surprise and ignorance, correlations and
 conditional distributions.
 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
 the Excursions.

     9c Part III Linear Thermodynamics                                                           Notes PDF 1965K
 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.
 Computing: everywhere.

     9c Part IV. Melt, Boil, Condense, Freeze                                                     Notes PDF 545K
 Math: random graphs, critical probabilities, and, in the Excursions, power law
 distributions.
 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
bioinformatics.

Week 10 The laws of thought                                                                        Notes PDF 248K
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 208K
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.

Book 11c Geometry and Gravity
(This is an extensive treatment of general relativity. All the stipulations for
Book 8c above apply here.
 This "week" on general relativity was added in 2015 and is also not intended 
to be covered in one week.)

     11c Part I. Fields, Complementary Coordinates, Curved Space                                    Notes PDF 1556K
Science: fields, gradient, divergence, curl, shear, classical gravitation,
	geodesics for the Earth.
Math: slopes of multivariable functions and their representation using index
	coordinates, nonorthogonal and unnormalized coordinate systems, coordinate
	systems which depend on the coordinates themselves, tensors, metric, affine
	connection, geodesics, curved space and curvature tensor, hyperbolic and
	parabolic spaces.
Computing: relational representation of vectors, matrices and protors 
	(proto-tensors); the protor calculator.

     11c Part II. Gravity                                                                          Notes PDF 1335K
Science: classical general relativity (curved timespace, gravity and time,
	metrics for spherically and axially symmetric stars, tides, light orbits,
	stress-energy, cosmology, inflation); gravitational technology (warp drive);
	the entropy of null surfaces and the holographic principle; alternatives
	to geometry.

Book 11d Forces and Invariants
(This is an extensive treatment of quantum physics. All the stipulations for
Book 8c above apply here.
 This "week" on quantum physics was added in 2018 and is also not intended 
to be covered in one week.)

     11d Part I. Electrostatics and Electromagnetism                                               Notes PDF 366K
Math: slopes and vectors in 3D (div, grad, dot products; cross products, curl);
	matrix invariants.
Science: energy and momentum scales; electromagnetism from special relativity;
	light as an electromagnetic wave; back to special relativity.
Computing: visualizing magnetic fields.

     11d Part II. Partial Slope Equations and Quantum Mechanics                                    Notes PDF 1252K
Computing: numerical solution of partial slope equations (Jacobi method,
	Dirichlet boundary conditions, unitary matrices and stability).
Science: waves and wave functions (Laplace, wave and Schroedinger equations);
	wave packets in 1D and 2D; barriers and slits.

     11d Part III. Quantum Electromagnetism                                                        Notes PDF 709K
Science: electromagnetic field as a quantum phase shift which depends on
	position; fields versus action-at-a-distance; phase symmetries and
	other forces (weak and strong nuclear forces).
Math: absolute slopes - affine connection as inside connection.
Computing: more simulation.

     11d Part IV. Quantum Field Theory: Matrix Quantum Mechanics                                   Notes PDF 420K
Science: creation and annihilation of particles; boson operators commute,
	fermion operators anticommute; particles as excitations of fields;
	reflections, shears and spin 1/2, spin 2; commutation and simultaneous
	measurements; Klein-Gordon relativistic wave equation; Yukawa potential;
	Dirac equation factors Klein-Gordon for fermions; charge conservation
	and antimatter.
Math: commuting and anticommuting matrices, infinite and 2-by-2; reflections
	and Clifford algebra; ladders and Grassmann algebra; tensor products;
	reflection, rotation and shear matrices; rotation generators; reflection
	algebra in 4D Minkowski space; (back)slash notation; factoring quadratic
	equations; calculus of complex variables.
Computing: (perturbation methods).

     11d Part V. Functional Integrals                                                              Notes PDF 342K
Science: whole paths can have amplitudes; follow the charge because it is
	conserved, not the particle; Feynman diagrams and quantum
	electrodynamics; chirality and the electroweak synthesis, left-handed
	neutrinos; Green's functions are propagators.
Math: calculus of functionals; Gaussian integrals, normalization; inverting
	slope equations - Green's functions.
Computing: (path integrals).

     11d Part VI. Quantum Computing                                                                Notes PDF 294K
Computing: qubits; 1-, 2- and 3-qubit gates (reversible, Hermitian);
	superposition (Hadamard gate) and entanglement (controlled-not gate);
	Fourier transform (bits, qubits, period-finding); cybersecurity
	(quantum key distribution); searching unstructured databases; error
	correction.
Science: observables and measurement, expected values and density matrices,
	system and environment; no cloning theorem; spooky action at a distance
	(Einstein-Podolsky-Rosen).
Math: representing functions (Walsh-Hadamard transform and entanglement);
	bra-ket notation; rotations and reflections.

Week 12 Memory and programming language: recursion and instantiation            MATLABpak          Notes PDF 280K
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

Keyword-in-context Index                                                                          KWIC PDF 103K



Here is the version of this course posted in 2018 .

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

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

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

Marking
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 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, Luigi Adario-Berry, Cezanne Aguilar-Gagne, Karl Alvarado, Fahd Badran, John Blackman, Mathieu Blanchette, Luis Chaidez, Xiao-Wen Chang, Hossam El-Gindy, Leftraru Gonzalez-Tucas, Frederic Guichard, Arturo Hal, Caden Indigo Hamer, Tristan Rain Hamer, David Harpp, Patrick Hayden, Don Hetherington, Iris Huang, Ravi Jovanovic, Zhanna Klimanova, Alex Kroitor, Dalia Leblay, Solomon Li, Gabriel Marleau, Liam Martins, Fred Mayer, Jake McKinnell, Taowa Munene-Tardif, John Parkinson, Wolf Rasmussen, Adam Shamsa, Amaya Sealy-Lepage, Kaleem Siddiqi, Shea Turner-Matthews, Jessica Thompson, Matthew Williams, Xiaowei Yu 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.

Books
All the pdf Notes linked to above have been written not for direct study by teenagers but are targeted towards myself as instructor (for "Weeks") or myself as learner (for "Books").
I have since rewritten some of them into a series of short (120-page) but self-contained books (Physics for Teenagers, Computing for Teenagers, etc.):

Physics for Superteens: Relativistic Quantum Physics (TBP) PDF 1.4M (Mainly from Book 11d, with help from Book 8c.)

Physics for Superteens: Collective Phenomena (TBP) PDF 1.8M (Based on Book 9c.)

Physics for Superteens: Rocket Science (TBP) PDF 1.9M (Minor rearrangement of Book 8d.)

Computing for Superteens (TBP) PDF 3.0M (Python programs for many of these topics and more.)

Advanced Math for Superpreteens (TBP) PDF 1.2M (A grade 6 course in dialog.)

Even so, these books are probably too concentrated for their audience and will need to be interpreted by a more experienced partner.

Synopses, of about 500 words, can be found for each of these books here .