 ## Course materials: Linear Algebra and Probability for Computer Science Applications

### Summary

Taking a computer scientist's point of view, this classroom-tested text gives an introduction to linear algebra and probability theory, including some basic aspects of statistics. It discusses examples of applications from a wide range of areas of computer science, including computer graphics, computer vision, robotics, natural language processing, web search, machine learning, statistical analysis, game playing, graph theory, scientific computing, decision theory, coding, cryptography, network analysis, data compression, and signal processing. It includes an extensive discussion of MATLAB, and includes numerous MATLAB exercises and programming assignments. xviii + 410 pages.

### Book web site: CRC Press Errata Addenda Matlab Code Additional Assignments

Solutions to some assignments are available for course instructors. For information please email Susie Carlisle susie.carlisle@taylorandfrancis.com.

• 1 Matlab
• 1.1 Desk Calculator Operations
• 1.2 Booleans
• 1.3 Nonstandard Numbers
• 1.4 Loops and Conditionals
• 1.5 Script File
• 1.6 Functions
• 1.7 Variable Scope and Parameter Passing

#### Part I: Linear Algebra

• 2 Vectors
• 2.1 Definition of Vectors
• 2.2 Application of Vectors
• 2.3 Basic Operations on Vectors
• 2.3.1 Algebraic Properties of the Operations
• 2.3.2 Applications of Basic Operations
• 2.4 Dot Product
• 2.4.1 Algebraic Properties of the Dot Product
• 2.4.2 Application of the Dot Product: Weighted Sum
• 2.4.3 Geometric Properties of the Dot Product
• 2.4.4 Metacomment: How to Read Formula Manipulations
• 2.4.5 Application of the Dot Product: Similarity of Two Vectors
• 2.4.6 Dot Product and Linear Transformations
• 2.5 Vectors in MATLAB: Basic Operations
• 2.5.1 Creating a Vector and Indexing
• 2.5.2 Creating a Vector with Elements in Arithmetic Sequence
• 2.5.3 Basic Operations
• 2.5.4 Element-by-Element Operations
• 2.5.5 Useful Vector Functions
• 2.5.6 Random Vectors
• 2.5.7 Strings: Arrays of Characters
• 2.5.8 Sparse Vectors
• 2.6 Plotting Vectors in MATLAB
• 2.7 Vectors in Other Programming Languages
• 3 Matrices
• 3.1 Definition of Matrices
• 3.2 Applications of Matrices
• 3.3 Simple Operations on Matrices
• 3.4 Multiplying a Matrix Times a Vector
• 3.4.1 Applications of Multiplying a Matrix Times a Vector
• 3.5 Linear Transformation
• 3.6 Systems of Linear Equations
• 3.6.1 Applications of Systems of Linear Equations
• 3.7 Matrix Multiplication
• 3.8 Vectors as Matrices
• 3.9 Algebraic Properties of Matrix Multiplication
• 3.9.1 Matrix Exponentiation
• 3.10 Matrices in MATLAB
• 3.10.1 Inputting Matrices
• 3.10.2 Extracting Submatrices
• 3.10.3 Operations on Matrices
• 3.10.4 Sparse Matrices
• 3.10.5 Cell Arrays
• 4 Vector Spaces
• 4.1 Fundamentals of Vector Spaces
• 4.1.1 Subspaces
• 4.1.2 Coordinates, Bases, Linear Independence
• 4.1.3 Orthogonal and Orthonormal Basis
• 4.1.4 Operations on Vector Spaces
• 4.1.5 Null Space, Image Space, and Rank
• 4.1.6 Systems of Linear Equations
• 4.1.7 Inverses
• 4.1.8 Null Space and Rank in MATLAB
• 4.2 Proofs and Other Abstract Mathematics (Optional)
• 4.2.1 Vector Spaces
• 4.2.2 Linear Independence and Bases
• 4.2.3 Sum of Vector Spaces
• 4.2.4 Orthogonality
• 4.2.5 Functions
• 4.2.6 Linear Transformations
• 4.2.7 Inverses
• 4.2.8 Systems of Linear Equations
• 4.3 Vector Spaces in General (Very Optional)
• 4.3.1 The General Definition of Vector Spaces
• 5 Algorithms
• 5.1 Gaussian Elimination: Examples
• 5.2 Gaussian Elimination: Discussion
• 5.2.1 Gaussian Elimination on Matrices
• 5.2.2 Maximum Element Row Interchange
• 5.2.3 Testing on Zero
• 5.3 Computing a Matrix Inverse
• 5.4 Inverse and Systems of Equations in MATLAB
• 5.5 Ill-Conditioned Matrices
• 5.6 Computational Complexity
• 5.6.1 Viewpoints on Numerical Computation
• 5.6.2 Running Times
• 6 Geometry
• 6.1 Arrows
• 6.2 Coordinate Systems
• 6.3 Simple Geometric Calculations
• 6.3.1 Distance and Angle
• 6.3.2 Direction
• 6.3.3 Lines in Two-Dimensional Space
• 6.3.4 Lines and Planes in Three-Dimensional Space
• 6.3.5 Identity, Incidence, Parallelism, and Intersection
• 6.3.6 Projections
• 6.4 Geometric Transformations
• 6.4.1 Translations
• 6.4.2 Rotation around the Origin
• 6.4.3 Rigid Motions and the Homogeneous Representation
• 6.4.4 Similarity Transformations
• 6.4.5 Affine Transformations
• 6.4.6 Image of a Distant Object
• 6.4.7 Determinants
• 6.4.8 Coordinate Transformation on Image Arrays
• 7 Change of Basis, DFT, and SVD
• 7.1 Change of Coordinate System
• 7.1.1 Affine Coordinate Systems
• 7.1.2 Duality of Transformation and Coordinate Change; Handedness
• 7.1.3 Application: Robotic Arm
• 7.2 The Formula for Basis Change
• 7.3 Confusion and How to Avoid It
• 7.4 Nongeometric Change of Basis
• 7.5 Color Graphics
• 7.6 Discrete Fourier Transform (Optional)
• 7.6.1 Other Applications of the Fourier Transform
• 7.6.2 The Complex Fourier Transform
• 7.7 Singular Value Decomposition
• 7.7.1 Matrix Decomposition
• 7.7.2 Proof of Theorem 7.4 (Optional)
• 7.8 Further Properties of the SVD
• 7.8.1 Eigenvalues of a Symmetric Matrix
• 7.9 Applications of the SVD
• 7.9.1 Condition Number
• 7.9.2 Computing Rank in the Presence of Roundoff
• 7.9.3 Lossy Compression
• 7.10 MATLAB
• 7.10.1 The SVD in MATLAB
• 7.10.2 The DFT in MATLAB

#### Part II: Probability

• 8 Probability
• 8.1 The Interpretations of Probability Theory
• 8.2 Finite Sample Spaces
• 8.3 Basic Combinatorial Formulas
• 8.3.1 Exponential
• 8.3.2 Permutations of n Items
• 8.3.3 Permutations of k Items out of n
• 8.3.4 Combinations of k Items out of n
• 8.3.5 Partition into Sets
• 8.3.6 Approximation of Central Binomial
• 8.3.7 Examples of Combinatorics
• 8.4 The Axioms of Probability Theory
• 8.5 Conditional Probability
• 8.6 The Likelihood Interpretation
• 8.7 Relation between Likelihood and Sample Space Probability
• 8.8 Bayes' Law
• 8.9 Independence
• 8.9.1 Independent Evidence
• 8.9.2 Application: Secret Sharing in Cryptography
• 8.10 Random Variables
• 8.11 Application: Naive Bayes Classification
• 9 Numerical Random Variables
• 9.1 Marginal Distribution
• 9.2 Expected Value
• 9.3 Decision Theory
• 9.3.1 Sequence of Actions: Decision Trees
• 9.3.2 Decision Theory and the Value of Information
• 9.4 Variance and Standard Deviation
• 9.5 Random Variables over Infinite Sets of Integers
• 9.6 Three Important Discrete Distributions
• 9.6.1 The Bernoulli Distribution
• 9.6.2 The Binomial Distribution
• 9.6.3 The Zipf Distribution
• 9.7 Continuous Random Variables
• 9.8 Two Important Continuous Distributions
• 9.8.1 The Continuous Uniform Distribution
• 9.8.2 The Gaussian Distribution
• 9.9 MATLAB
• 10 Markov Models
• 10.1 Stationary Probability Distribution
• 10.1.1 Computing the Stationary Distribution
• 10.2 PageRank and Link Analysis
• 10.2.1 The Markov Model
• 10.2.2 Pages with No Outlinks
• 10.2.3 Nonuniform Variants
• 10.3 Hidden Markov Models and the K-Gram Model
• 10.3.1 The Probabilistic Model
• 10.3.2 Hidden Markov Models
• 10.3.3 The Viterbi Algorithm
• 10.3.4 Part of Speech Tagging
• 10.3.5 The Sparse Data Problem and Smoothing
• 11 Confidence Intervals
• 11.1 The Basic Formula for Confidence Intervals
• 11.2 Application: Evaluating a Classifier
• 11.3 Bayesian Statistical Inference (Optional)
• 11.4 Confidence Intervals in the Frequentist Viewpoint (Optional)
• 11.5 Hypothesis Testing and Statistical Significance
• 11.6 Statistical Inference and ESP
• 12 Monte Carlo Methods
• 12.1 Finding Area
• 12.2 Generating Distributions
• 12.3 Counting
• 12.4 Counting Solutions to a DNF Formula(Optional)
• 12.5 Sums, Expected Values, and Integrals
• 12.6 Probabilistic Problems
• 12.7 Resampling
• 12.8 Pseudorandom Numbers
• 12.9 Other Probabilistic Algorithms
• 12.10 MATLAB
• 13 Information and Entropy
• 13.1 Information
• 13.2 Entropy
• 13.3 Conditional Entropy and Mutual Information
• 13.4 Coding
• 13.4.1 Huffman Coding
• 13.5 Entropy of Numeric and Continuous Random Variables
• 13.6 The Principle of Maximum Entropy
• 13.6.1 The Principle of Maximum Entropy
• 13.6.2 Consequences of the Maximum Entropy Principle
• 13.7 Statistical Inference
• 14 Maximum Likelihood Estimation
• 14.1 Sampling
• 14.2 Uniform Distribution
• 14.3 Gaussian Distribution: Known Variance
• 14.4 Gaussian Distribution: Unknown Variance
• 14.5 Least Squares Estimates
• 14.5.1 Least Squares in MATLAB
• 14.6 Principal Component Analysis
• 14.7 Applications of Principal Component Analysis