Mathematics 202: Linear Algebra and Probability (Spring 2011)
Instructor:
Allan Cruse
Email: cruse@usfca.edu
Phone: (415) 422-5692
Office: 222A Harney Science Center
Office Hours: (see my homepage)
Synopsis:
This course explores fundamental concepts, from two distinct realms
of mathematics, which are
especially relevant to college students
majoring in computer science (although students in other
disciplines
may also be advantaged by these studies). Computer graphics, web
sciences, artificial
intelligence, and parallel programming are a few
examples of areas within computer science where
ideas from linear algebra
and from probability are illuminating and useful. Although it is more
typical
for these two mathematics subjects to be taught in separate
courses, we will attempt here to tie them
together wherever possible,
and especially to show how they apply to specific kinds of questions that
computer science students encounter.
The planned course-topics include:
- matrix arithmetic
- laws of matrix algebra
- determinants and inverses
- solutions for linear systems
- geometric applications
- matrices as transformations
- vectors in 2- and 3-dimensions
- equations for lines and planes
- discrete probability and counting
- independent and dependent events
- random variables and sampling
- discrete and continuous distributions
- the binomial and normal distributions
- expected value and variance
The pair of textbooks which accompany this course were selected with
clarity, cost, coverage, and
convenience in mind: they offer us
succinctly presented ideas, accompanied by a rich collection of
examples and worked out exercises which facilitate self-study and
review -- and they have a long
record of successful use by college
students at a diversity of institutions. While their 'dry' style
may
not make for exciting reading, it does offer rapid expositions
of key technical details, allowing our
classroom to be the place
where 'life' will get breathed into these topics. :-)
Textbooks:
Seymour Lipschutz and Marc Lipson,
Probability (2nd Edition),
Schaum's Outline Series: McGraw-Hill (2000),
ISBN 987-0-07-135203-1
Seymour Lipschutz and Marc Lipson,
Linear Algebra (4th Edition),
Schaum's Outline Series: McGraw-Hill (2009),
ISBN 978-0-07-154352-1
Learning Outcomes:
- You will know how to gauge the significance of probability measurements.
- You will be able to distinguish randomness from deterministic behaviors.
- You will understand the basis for inferences based upon opinion polling.
- You will know how to represent any linear system with a suitable matrix.
- You will know how to compute the general solution for any linear system.
- You will be able to recognize geometric properties inherent in matrices.
- You will gain familiarity with laws and terminology from modern algebra.
- You will have a fresh appreciation for mathematics' role in computation.
Readings
- For Week 1 (1/24 - 1/28): Probability, Chapters 1 and 2
- For Week 2 (1/31 - 2/04): Probability, Chapter 3
- For Week 3 (2/07 - 2/11): Probability, Chapter 4
- For Week 4 (2/14 - 2/18): Probability, Chapter 5
- For Week 5 (2/22 - 2/25): Probability, Chapter 6
- For Week 6 (2/28 - 3/04): Probability, Chapter 7
- For Week 7 (3/07 - 3/11): Linear Algebra, Chapter 1
- For Week 8 (3/21 - 3/25): Linear Algebra, Chapter 2
- For Week 9 (3/28 - 4/01): Linear Algebra, Chapter 3
- For Week 10 (4/04 - 4/08): Linear Algebra, Chapter 4
- For Week 11 (4/11 - 4/15): Linear Algebra, Chapter 5
- For Week 12 (4/18 - 4/21): Linear Algebra, Chapter 6
- For Week 13 (4/25 - 4/29): Linear Algebra, Chapter 7
- For Week 14 (5/02 - 5/06): Linear Algebra, Chapter 8
- For Week 15 (5/09 - 5/11): Linear Algebra, Chapter 9
Resources
- Online guide to
ANSI terminal escape-sequences
- Audiovisual animation:
How Diffusion Works, for "Human Anatomy", by McKinley O'Loughlin,
McGraw-Hill (2005)
- Research statistics:
Blood Types in the U.S. School of Medicine, Stanford University (2011)
- Online Math Reference:
Generalizing the Volume of a Simplex
- Online Math Refresher:
Euler's Number by Larry Freeman, Fremont, California (2006)
- BetterExplained article:
An Intuitive Guide to Exponential Functions and e by Kalid Azad (May 2007)
- Online video tutorial:
Introduction to Markov Chains - Part 1 by PatrickJMT
- Online video tutorial:
Introduction to Markov Chains - Part 2 by PatrickJMT
- Online article:
How is it made? Google Search Engine, by Joseph Khoury,
University of Ottawa (2010)
- Matrix application:
Color Conversion
by Equasys System Development, Germering, Germany
- Mathfun tutorial:
Pythagorean Triples are sets of three integers (a,b,c)
that satisfy the Pythagoras equation
- Online article:
Homogeneous Coordinates,
by Jules Bloomenthat and Jon Rokne, CS Dept, Univ. of Calgary
- Online article:
The Gram-Schmidt Algorithm
(.pdf format),
Harvey Mudd College Math Tutorial
Handouts
- 0206-202-01: Course syllabus (PDF)
- lesson01.odp (OpenOffice Slides)
- Demo program: tosscoin.py
uses Python's 'randint()' function to simulate the tossing of a 'fair' coin
- Demo program: lawlarge.py
uses a coin-tossing simulation to illustrate the Law of Large Numbers
- Demo program: lincong.cpp
generates 'random' numbers using the "Linear Congruential Method"
- lesson02.odp (OpenOffice Slides)
- Demo program: passwds.py
this will show us how many 7-letter computer passwords are possible
- Demo program: demere.py
computes the chances of getting a 'double-six' in 24 throws of two dice
- Demo program: randwalk.cpp
shows an animation where a molecule randomly moves left or right
- Demo program: 2dimwalk.cpp
shows a "random walk" animation in two dimensions with barriers
- lesson03.odp (OpenOffice Slides)
- Demo program: binomial.py
illustrates use of recursion to display some rows of Pascal's Triangle
- lesson04.odp (OpenOffice Slides)
- Demo program: megawin.py
computes the number of MegaMillions lottery-tickets using recursion
- Demo program: megawin2.py
computes the number of MegaMillions lottery-tickets non-recursively
- lesson05.odp (OpenOffice Slides)
- Demo program: shortadd.cpp
shows the probability of overflow if random 16-bit integers are added
- lesson06.odp (OpenOffice Slides)
- Demo program: hemoxfer.cpp
estimates the probability of random blood transfusion incompatibility
- lesson07.odp (OpenOffice Slides)
- lesson08.odp (OpenOffice Slides)
- Demo program: cancer.py
performs a calculation we needed that pocket-calculators wouldn't show
- lesson09.odp (OpenOffice Slides)
- lesson10.odp (OpenOffice Slides)
- lesson11.odp (OpenOffice Slides)
- Demo program: eulernum.cpp
offers an introduction to Euler's Number using computer simulations
- Demo program: converge.py
shows terms from two sequences that both approach Euler's Number
- Demo program: faster_e.py
displays the successive sums of the reciprocal-factorials up through 9!
- lesson12.odp (OpenOffice Slides)
- Demo program: e_as_mean.cpp
revised 'eulernum' simulation shows probability distribution graph
- lesson13.odp (OpenOffice Slides)
- Demo programs: bindist.cpp
and normdist.cpp
for comparing the Binomial and Normal distributions
- Demo programs: geodist.cpp
depicts a Geometric Distribution (to model trials that seldom succeed)
- Demo programs: stdnorml.cpp
shows numerical areas under the standard normal curve for quizzes
- lesson14
Sample Applications of Binomial and Normal Distributions
- lesson15
Sample Applications of Markov Chains
- Demo program: markov.cpp
shows a transition matrix and state vectors in a Markov Chain example
- lesson16
Sample Application of Transition-Matrix Powers
- Demo program: matpower.cpp
shows powers of the transition matrix for the Markov Chain example
- Demo program: table.py
reviews some Python programming techniques of potential use in Project 1
- lesson17
showing some 'Birthday Problem' probabilities
- Demo program: birthday.py
shows probabilities of randomly chosen people having distinct birthdays
- Midterm Exam
- lesson18
showing essential output from our 'PageRank' calculation-demo
- Demo program: pagerank.cpp
implementing the PageRank calculation from Joseph Khoury's article
- Project soliution: stdnorml.py
showing a possible way to solve the programming problem in Project 1
- Lesson 19
illustrating some uses of linear algebra in computer graphics
- Demo program: redband.cpp
for illustrating the way graphics display memory controls screen colors
- System utility: fileview.cpp
allows us to view the contents of any files (including device special files)
- Demo programs: rgb2mono.cpp
and rgbsplit.cpp
applying matrix-multiplication to color-conversions
- Image files: hawaii.img and
hawaii2.img to use with the two
color-conversion demo-programs above
- Device Driver: gateway.c
required for execution of the color-conversion demo-programs under Linux
- System utility: mmake.cpp
the tool we use for compiling our 'gateway.c' device-driver under Linux 2.3
- Demo program: opaqueit.cpp
for illustrating the role of vectors and dot-products in computer graphics
- Lesson 20
illustrating the Gauss-Jordan Elimination algorithm
- Header file: fraction.h
defines the attributes and methods for an object class in C++ called 'Fraction'
- Header file: qmatrix.h
defines the attributes and methods for an object class called 'FractionMatrix'
- Matrix utility: gaussian.cpp"
implements Gauss-Jordan Elimination, used for solving linear systems
- Lesson 21
on an example of a homogeneous linear system which arises in chemistry
- Demo program: fourdemo.cpp
dynamically approximates a graph using terms from a Fourier Series
- Lesson 22-1 and
Lesson 22-2
on a simple 'change-of-basis' example in graphics programming
- Lesson 23
showing sample output from our 'orthog.cpp' demo-program
- Demo program: orthog.cpp
implements Gram-Schmidt orthogonalization of row-vectors in a matrix
- Header-files: fraction.h
and vmatrix.h
(these are needed when compiling our 'ortho.cpp' application)
- Demo program: permlist.cpp
displays a list of all the permutations on the first n uppercase letters
- Demo program: minassn.cpp
shows steps in obtaining the minimum-cost personnel assignment
- Demo program: perms.cpp
lists all of the permutations for {1,2,...,N} in a 'cycle' of transpositions
Announcements
- No class meeting: Monday, February 21 (Presidents' Day)
- project1: Due 1pm Wednesday, March 9.
- MIDTERM EXAM: Friday, March 11, 1:00pm
- No class meetings: Mon-Fri, March 14-18 (Spring Break)
- No class meeting: Friday, April 22 (Good Friday)
- FINAL EXAMINATION: Monday, May 16, 12:30pm
Last updated on 07/10/2011
