CS6015: Linear Algebra and Random Processes

Course information

  • When: Jul-Nov 2019

  • Lectures: Slot D

  • Where: CS36

  • Teaching Assistants: Nirav Bhavsar, Ajay Pandey, Nithia V, Monisha J

  • Office Hours: Wed 2:30pm to 3:30pm

  • Course Content: See Schedule below

Grading

  • Mid-term (Linear Algebra concepts): 30%

  • Final exam (Probability concepts): 30%

  • Quizzes: 20% (Best 4 out of 6)

  • Programming Assignments: 20%

Target Audience

Masters (M.Tech/M.S.) and Ph.D. students

Important Dates

  • Quizzes: Aug 13, Aug 29, Sep 19, Oct 14, Oct 30, Nov 11

  • Mid-term: 10am to 12pm, Sep 28

  • End-sem: 2pm to 5pm, Nov 20

Quizzes/Exams

Textbooks

  • Linear Algebra:

    • Linear algebra and applications by Gilbert Strang

    • Linear Algebra: Pure and Applied by Edgar Goodaire

  • Additional references:

    • Introduction to Probability by Bertsekas and Tsitsiklis

    • Introduction to probability models by Sheldon Ross

Schedule from 2017

Part I: Linear Algebra
Lecture number Topics Covered Section reference
(Strang's book)
Lecture 1 Course Organization
Motivation for studying linear algebra
Lecture 2 Geometry of linear equations - row picture, col picture
Vector space, subspace - definition, examples Linear combinations, linear independence
1.2
Lecture 3 Transpose - properties
Inverse
Gaussian elimination
1.3
Lecture 4 Computational cost of elimination
Matrix multiplication - four view
Gauss-Jordan method
1.4
Lecture 5 Factorization A=LU and A=LDU
Row exchanges, permutation matrices
Uniqueness of LU/LDU factorization for invertible matrices
1.5
Lecture 6 Column and null spaces
Null space computation by solving Ax=0
Pivot and free variables, special solutions
row reduced echelon form
2.1, 2.2
Lecture 7 Dimension = number of vectors in any basis
Rank, row-rank = col-rank
rank + nullity = number of columns
2.3, 2.4
Lecture 8 Orthogonal vectors and subspaces
Row space orthogonal to null space
3.1
Quiz 1
Lecture 9 Projection onto a line
Projection onto a subspace
3.2
Lecture 10 Least squares data fitting
Orthonormal vectors
3.3
Lecture 11 Four fundamental subspaces (again)
Least squares data fitting
2.4, 3.3
Lecture 12 Orthogonal bases
Gram Schmidt algorithm
Factorization A=QR
3.4
Quiz 2
Lecture 13 Linear transformations:
definition, matrix representation
2.6
Lecture 14 Composition of linear transformations
Change of basis
Change of basis: Section 46 of Halmos's text
Lecture 15 Similarity of transformations Section 47 of Halmos's text
Quiz 3
Lecture 16 Determinants: Properties, Formula 4.2, 4.3
Lecture 17 Determinants: Cofactors, Applications in graphs 4.3, 4.4
Graph applications: Section 3.3 of Goodaire's text
Lecture 18 Eigenvalues and Eigenvectors 5.1
Lecture 19 Similarity and diagonalization 5.2
Lecture 20 Spectral theorem for real symmetric matrices:
case when eigenvalues are distinct
5.5
Lecture 21 Complex vector space, Hermitian and unitary matrices 5.5
Quiz 4
Lecture 22 Schur's theorem
Spectral theorem as a corollary
5.5
Lecture 23 Singular value decomposition 6.3
Mid-sem Exam

Part II: Random Processes
Lecture number Topics Covered Section reference
(Grimmett's book)
Lecture 1 Events as sets, probability spaces 1.2
Lecture 2 Cardinality, countability and infinite sums Sections 4 and 5 of Manjunath Krishnapur's notes
Lecture 3 Properties of probability measure 1.3
Lecture 4 Conditional probability 1.4
Quiz 5
Lecture 5 Independence
Gambler's ruin
1.5
Lecture 6 Random variables and distribution function 2.1
Lecture 7 Uncountable probability spaces, distribution functions Section 14 of Manjunath Krishnapur's notes
Lecture 8 Law of averages - Bernstein's inequality 2.2
Lecture 9 Discrete r.v.s - definition and examples
Independence
3.1
Quiz 6
Lecture 10 Discrete r.v.s - expectation, higher moments and examples 3.3, 3.5
Lecture 11 Discrete r.v.s - joint distribution function
Covariance, correlation
3.6
Lecture 12 Discrete r.v.s - conditional distribution and expectation 3.7
Lecture 13 Discrete r.v.s - conditional expectation
Sums of r.v.s
3.7, 3.8
Quiz 7
Lecture 14 Continuous r.v.s - p.d.f., independence, expectation 4.1, 4.2, 4.3
Lecture 15 Continuous r.v.s - examples 4.4
Lecture 16 Continuous r.v.s - dependence 4.5
Quiz 8
Lecture 17 Continuous r.v.s - conditional distributions and expectation 4.6
Lecture 18 Continuous r.v.s - functions of r.v.s 4.7
Lecture 19 Continuous r.v.s - change of variables 4.7
Lecture 20 Continuous r.v.s - multivariate normal distribution 4.9