Features
Focuses on mathematical techniques that are most relevant to computer scientists
Assumes as little mathematical background as possible
Covers applications from computer graphics, web search, machine learning, cryptography, and a host of other computer science areas
Includes MATLAB functions, MATLAB programming assignments, and problems in each chapter
Offers MATLAB code at www.cs.nyu.edu/faculty/davise/MathTechniques/index.html
Based on the author’s course at NYU, Linear Algebra and Probability for Computer Science Applications gives an introduction to two mathematical fields that are fundamental in many areas of computer science. The course and the text are addressed to students with a very weak mathematical background. Most of the chapters discuss relevant MATLAB® functions and features and give sample assignments in MATLAB; the author’s website provides the MATLAB code from the book.
After an introductory chapter on MATLAB, the text is divided into two sections. The section on linear algebra gives an introduction to the theory of vectors, matrices, and linear transformations over the reals. It includes an extensive discussion on Gaussian elimination, geometric applications, and change of basis. It also introduces the issues of numerical stability and round-off error, the discrete Fourier transform, and singular value decomposition. The section on probability presents an introduction to the basic theory of probability and numerical random variables; later chapters discuss Markov models, Monte Carlo methods, information theory, and basic statistical techniques. The focus throughout is on topics and examples that are particularly relevant to computer science applications; for example, there is an extensive discussion on the use of hidden Markov models for tagging text and a discussion of the Zipf (inverse power law) distribution.
Examples and Programming Assignments
The examples and programming assignments focus on computer science applications. The applications covered are drawn from a range of computer science areas, 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.
Homework Problems
Comprehensive problem sections include traditional calculation exercises, thought problems such as proofs, and programming assignments that involve creating MATLAB functions.
Download Updates of this Book (More Exercises, Problems & Programmes) from the following Link:
http://www.cs.nyu.edu/faculty/davise/MathTechniques/MoreAssigs/MoreAssigs.html
Author(s): Ernest Davis
Edition: 1
Publisher: CRC Press
Year: 2012
Language: English
Commentary: Fully Bookmarked
Pages: C, xviii, 410, B
Cover
S Title
Linear Algebra and Probability for Computer Science Applications
© 2012 by Taylor & Francis Group, LLC
ISBN 978-1-4665-0159-1 (eBook - PDF)
Dedication
Contents
Preface
Chapter 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
Problem
Programming Assignments
I: Linear Algebra
Chapter 2 Vectors
2.1 Definition of Vectors
2.2 Applications of Vectors
2.2.1 General Comments about Applications
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
Exercises
Problems
Programming Assignments
Chapter 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
Problems
Programming Assignments
Chapter 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 AbstractMathematics (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
Exercises
Programming Assignments
Chapter 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
Exercises
Programming Assignments
Chapter 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
6.4.8 Coordinate Transformation on Image Arrays
Exercises
Problems
Programming Assignments
Chapter 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
Exercises
Problems
Programming Assignments
II: Probability
Chapter 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
Exercises
Problems
Programming Assignments
Chapter 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.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
Exercises
Problems
Programming Assignments
Chapter 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
Exercises
Problems
Programming Assignments
Chapter 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
Exercises
Problems
Chapter 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
Exercises
Programming Assignments
Chapter 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
Exercises
Problem
Chapter 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
14.7.1 Visualization
14.7.2 Data Analysis
14.7.3 Bounding Box
14.7.4 Surface Normals
14.7.5 Latent Semantic Analysis
Exercises
Problems
Programming Assignments
References
Notation
Back Cover
