CS6030 - Mathematical Concepts for Computer Science

Meetings  

• Theme 1 : Describing Sets : Logic & Proofs - 16 meetings

  • Meeting 01 : Mon, Jul 29, 11:00 am-11:50 am -

  Administrative announcements: course structure and evaluation schemes. <br> The language of mathematics. Propositions. Operators.

  References	Chapter 1 of [KR].
  Exercises
  Reading

  Administrative announcements: course structure and evaluation schemes.
  The language of mathematics. Propositions. Operators.
  

  References:

  Chapter 1 of [KR].

  • Meeting 02 : Tue, Jul 30, 10:00 am-10:50 am - Raghavendra Rao

  Admin : TA introduction, Grouping. <br> Implication, Double Implication, Logical Equivalences.

  References	[KR] sections 1.1 and 1.2.
  Exercises
  Reading	<a href="http://www.vordenker.de/ggphilosophy/mcgill_contradiction-excl-middle.pdf"> On the laws of excluded middle </a>

  Admin : TA introduction, Grouping.
  Implication, Double Implication, Logical Equivalences.
  

  References:	[KR] sections 1.1 and 1.2.
  Reading:	On the laws of excluded middle

  • Meeting 03 : Wed, Jul 31, 09:00 am-09:50 am - Raghavendra Rao

  Arguments and Argument forms. Validity of Arguments. Rules of inference. Examples of deductions.

  References	[KR] section 1.5.
  Exercises
  Reading

  Arguments and Argument forms. Validity of Arguments. Rules of inference. Examples of deductions.
  

  References:

  [KR] section 1.5.

  • Meeting 04 : Thu, Aug 01, 12:00 pm-12:50 pm - Raghavendra Rao

  More examples of deductions. Quantifiers, quantified predicates.

  References	Section 1.3 of [KR]. Some of the examples for deductions are taken from [GT].
  Exercises
  Reading

  More examples of deductions. Quantifiers, quantified predicates.
  

  References:

  Section 1.3 of [KR]. Some of the examples for deductions are taken from [GT].

  • Meeting 05 : Mon, Aug 05, 11:00 am-11:50 am - Raghavendra Rao

  Deduction. Quantifiers and Predicate Logic, Examples, Negations. Notion of a proof. Various proof techniques: direct proof with two examples.

  References	[KR].
  Exercises
  Reading

  Deduction. Quantifiers and Predicate Logic, Examples, Negations. Notion of a proof. Various proof techniques: direct proof with two examples.
  

  References:

  [KR].

  • Meeting 06 : Tue, Aug 06, 10:00 am-10:50 am - Raghavendra Rao

  Proof by picture and proof by examples:pitfalls. Indirect proof with examples. Proof by contradiction. How to identify the contradiction? Examples

  References	The material is from [KR], and examples are taken from various sources.
  Exercises
  Reading	<a href="http://school.maths.uwa.edu.au/~berwin/humour/invalid.proofs.html"> Invalid Proof Techniques </a>

  Proof by picture and proof by examples:pitfalls. Indirect proof with examples. Proof by contradiction. How to identify the contradiction? Examples
  

  References:	The material is from [KR], and examples are taken from various sources.
  Reading:	Invalid Proof Techniques

  • Meeting 07 : Wed, Aug 07, 09:00 am-09:50 am - Raghavendra Rao

  More examples for proof by contradiction, Mathematical Fallacies: examples, Existence proofs: Constructive vs non-constructive proofs.

  References	Concepts are from the book [KR]. Examples from various sources.
  Exercises
  Reading

  More examples for proof by contradiction, Mathematical Fallacies: examples, Existence proofs: Constructive vs non-constructive proofs.
  

  References:

  Concepts are from the book [KR]. Examples from various sources.

  • Meeting 08 : Thu, Aug 08, 12:00 pm-12:50 pm - Raghavendra Rao

  Introduction to set theory. Axioms of set theory, Russel's paradox. Notion of cardinality. Countable, countably infinite sets.

  References	<a href="http://www.math.ucla.edu/~mwilliams/cardinality.pdf"> Cardinality of a set </b> By Michael Williams. <br>
  Exercises
  Reading	<a href="http://www.scs.ryerson.ca/~mth110/Handouts/PD/russell.pdf"> Russell's paradox and computability </a> If you like computability. <br> <a href="http://people.umass.edu/klement/OriginsPFParadox.pdf"> On the origins of Russell's paradox </a>

  Introduction to set theory. Axioms of set theory, Russel's paradox. Notion of cardinality. Countable, countably infinite sets.
  

  References:	Cardinality of a set By Michael Williams.
  Reading:	Russell's paradox and computability If you like computability. On the origins of Russell's paradox

  • Meeting 09 : Mon, Aug 12, 11:00 am-11:50 am - Raghavendra Rao

  Union of countably infinite sets. Set of rational numbers is a countably infinite set

  References	[KR] pages 169-173. <br> <a href="http://www.math.ucla.edu/~mwilliams/cardinality.pdf"> Cardinality </a> Notes by M Williams
  Exercises
  Reading

  Union of countably infinite sets. Set of rational numbers is a countably infinite set
  

  References:

  [KR] pages 169-173. Cardinality Notes by M Williams

  • Meeting 10 : Mon, Aug 12, 02:00 pm-03:00 pm - Raghavendra Rao

  Compensatory for Aug 15th - <br> Set of Rationals is countable, Union of countable sets. Uncountability of the set of real numbers: Cantor's diagonalization argument.

  References	[KR] pages 169-173, <br> <a href="http://www.math.ucla.edu/~mwilliams/cardinality.pdf"> Cardinality </a> Notes by M Williams
  Exercises
  Reading

  Compensatory for Aug 15th -
  Set of Rationals is countable, Union of countable sets. Uncountability of the set of real numbers: Cantor's diagonalization argument.
  

  References:

  [KR] pages 169-173, Cardinality Notes by M Williams

  • Meeting 11 : Tue, Aug 13, 10:00 am-10:50 am - Raghavendra Rao

  Uncountability of the set of real numbers: Cantor's diagonalization argument. Can the cardinality Natural number be equal to that of its power set?

  References	[KR] pages 169-173 <br> <a href="http://www.math.ucla.edu/~mwilliams/cardinality.pdf"> Cardinality of Sets</a> Notes by M Williams
  Exercises
  Reading

  Uncountability of the set of real numbers: Cantor's diagonalization argument. Can the cardinality Natural number be equal to that of its power set?
  

  References:

  [KR] pages 169-173 Cardinality of Sets Notes by M Williams

  • Meeting 12 : Wed, Aug 14, 09:00 am-09:50 am - Raghavendra Rao

  Further applications of Cantor diagonalization: A set and its power set are not equipotent. Induction principle: an axiomatic view. Peano's axioms. Examples of proofs by induction.

  References	[KR] Chapter 4. <br> <a href="http://inst.eecs.berkeley.edu/~cs70/sp07/lec/lecture03.pdf"> Lecture notes </a> by Luca Trevisan.
  Exercises
  Reading

  Further applications of Cantor diagonalization: A set and its power set are not equipotent. Induction principle: an axiomatic view. Peano's axioms. Examples of proofs by induction.
  

  References:

  [KR] Chapter 4. Lecture notes by Luca Trevisan.

  • Meeting 13 : Mon, Aug 19, 11:00 am-11:50 am - Raghavendra Rao

  Strong Induction. Examples. Structure of Proof by Induction. Well ordering Axiom. An example application of well ordering axiom: cycles in tournaments.

  References	[KR] Chapter 4. <a href="http://inst.eecs.berkeley.edu/~cs70/sp07/lec/lecture04.pdf"> Lecture Notes </a> byLuca Trevisan.
  Exercises
  Reading

  Strong Induction. Examples. Structure of Proof by Induction. Well ordering Axiom. An example application of well ordering axiom: cycles in tournaments.
  

  References:

  [KR] Chapter 4. Lecture Notes byLuca Trevisan.

  • Meeting 14 : Tue, Aug 20, 10:00 am-10:50 am - Raghavendra Rao

  Well-Ordering axiom is equivalent to strong induction. Fallacies in mathematical induction-- pitfalls in inductions proofs.

  References	Section 4.2 in <a href="http://math.berkeley.edu/~hutching/teach/proofs.pdf‎">Mathematical Proofs: </a> Notes by M Hutchings. <br> <a href="http://www.math.uiuc.edu/~hildebr/347/induction3.pdf"> Fallacies in Induction </a> by AJ Hildebrand.
  Exercises
  Reading

  Well-Ordering axiom is equivalent to strong induction. Fallacies in mathematical induction-- pitfalls in inductions proofs.
  

  References:

  Section 4.2 in Mathematical Proofs: Notes by M Hutchings. Fallacies in Induction by AJ Hildebrand.

  • Meeting 15 : Wed, Aug 21, 09:00 am-09:50 am - Raghavendra Rao

  Creativity in induction. Survivor in a knife fight game. Examples from graph theory.

  References	Example 12 in page 286 of [KR].<br> For the proof on number of edges in a tree see: <a href="http://classes.soe.ucsc.edu/cmps101/Winter13/handouts/InductionProofs.pdf"> Notes </a> on Mathematical induction
  Exercises
  Reading

  Creativity in induction. Survivor in a knife fight game. Examples from graph theory.
  

  References:

  Example 12 in page 286 of [KR]. For the proof on number of edges in a tree see: Notes on Mathematical induction

  • Meeting 16 : Thu, Aug 22, 12:00 pm-12:50 pm - Raghavendra Rao

  Further application of diagonalization: Computability. Halting problem is not computable.

  References	<a href="http://inst.eecs.berkeley.edu/~cs70/sp07/lec/lecture27.pdf"> Lecture Notes </a> by Luca Trevisan.
  Exercises
  Reading

  Further application of diagonalization: Computability. Halting problem is not computable.
  

  References:

  Lecture Notes by Luca Trevisan.

• Theme 2 : Size of Sets : Counting & Combinatorics - 11 meetings

  • Meeting 17 : Mon, Aug 26, 02:00 pm-03:00 pm - Raghavendra Rao

  Compensatory Lecture for Short Exam 1 <br> Basic counting: sum rule, product rule, inclusion-exclusion, pigeonhole principle (PHP)

  References	Section 5.1 of [KR].
  Exercises
  Reading

  Compensatory Lecture for Short Exam 1
  Basic counting: sum rule, product rule, inclusion-exclusion, pigeonhole principle (PHP)
  

  References:

  Section 5.1 of [KR].

  • Meeting 18 : Wed, Aug 28, 09:00 am-09:50 am - Raghavendra Rao

  The pigeonhole principle(PHP). Applications of PHP: non-existence of lossless data compression algorithms.

  References	CHapter 5.2 of [KR]
  Exercises
  Reading

  The pigeonhole principle(PHP). Applications of PHP: non-existence of lossless data compression algorithms.
  

  References:

  CHapter 5.2 of [KR]

  • Meeting 19 : Mon, Sep 02, 11:00 am-11:50 am - Raghavendra Rao

  More applications of PHP. Some proofs from the THE Book. Ramsey type theorems. Counting arguments.

  References	Ramsey numbers example is from Page 352 of [KR]. <br> The example of sequences if from the book <b>Proofs from THE BOOK</b> by Martin Aigner and Gunter Ziegler.
  Exercises
  Reading	Please read more profs from Chapter 22 of <b>Proofs from THE BOOK</b> by Martin Aigner and Gunter Ziegler.

  More applications of PHP. Some proofs from the THE Book. Ramsey type theorems. Counting arguments.
  

  References:	Ramsey numbers example is from Page 352 of [KR]. The example of sequences if from the book Proofs from THE BOOK by Martin Aigner and Gunter Ziegler.
  Reading:	Please read more profs from Chapter 22 of Proofs from THE BOOK by Martin Aigner and Gunter Ziegler.

  • Meeting 20 : Wed, Sep 04, 09:00 am-09:50 am - Raghavendra Rao

  Combinatorial Identities. Double counting: a proof technique of combinatorial identities.

  References	Section 5.3 of [KR]
  Exercises
  Reading

  Combinatorial Identities. Double counting: a proof technique of combinatorial identities.
  

  References:

  Section 5.3 of [KR]

  • Meeting 21 : Thu, Sep 12, 12:00 pm-12:50 pm - Raghavendra Rao

  Recurrence relations. Example applications: Derangements. Linear Homogeneous Recurrence Relations

  References	Sections 6.1 and 6.2 of [KR]
  Exercises
  Reading

  Recurrence relations. Example applications: Derangements. Linear Homogeneous Recurrence Relations
  

  References:

  Sections 6.1 and 6.2 of [KR]

  • Meeting 22 : Mon, Sep 16, 11:00 am-11:50 am - Raghavendra Rao

  Linear Homogeneous Recurrence Relations - Distinct roots case, examples.

  References	Sections 6.1 and 6.2 of [KR]
  Exercises
  Reading

  Linear Homogeneous Recurrence Relations - Distinct roots case, examples.
  

  References:

  Sections 6.1 and 6.2 of [KR]

  • Meeting 23 : Tue, Sep 17, 10:00 am-10:50 am - Raghavendra Rao

  Linear Homogeneous Recurrence Relations - higher multiplicity. General form with multiple roots with higher multiplicities.

  References	Section 6.2 of [KR]
  Exercises
  Reading

  Linear Homogeneous Recurrence Relations - higher multiplicity. General form with multiple roots with higher multiplicities.
  

  References:

  Section 6.2 of [KR]

  • Meeting 24 : Wed, Sep 18, 09:00 am-09:50 am - Raghavendra Rao

  Linear Non-homogeneous Recurrence Relations, Examples.

  References	Section 6.2 of [KR]
  Exercises
  Reading

  Linear Non-homogeneous Recurrence Relations, Examples.
  

  References:

  Section 6.2 of [KR]

  • Meeting 25 : Thu, Sep 19, 12:00 pm-12:50 pm - Raghavendra Rao

  Generating Functions Method I. Generating functions as power series. Operations + and * on power series. Extended binomial theorem. Example applications of generating functions for proving combinatorial identities and solving recurrences.

  References	Section 6.3 of [KR]
  Exercises
  Reading

  Generating Functions Method I. Generating functions as power series. Operations + and * on power series. Extended binomial theorem. Example applications of generating functions for proving combinatorial identities and solving recurrences.
  

  References:

  Section 6.3 of [KR]

  • Meeting 26 : Mon, Sep 23, 11:00 am-11:50 am - Raghavendra Rao

  Generating Functions Method II. Counting the number of spanning trees in a Fan-graph of order n.

  References	Class notes
  Exercises
  Reading

  Generating Functions Method II. Counting the number of spanning trees in a Fan-graph of order n.
  

  References:

  Class notes

  • Meeting 27 : Mon, Sep 23, 02:00 pm-03:00 pm - Raghavendra Rao

  Compensatory for Sept 9<br> Further applications of Generating functions. Catalan Numbers using generating functions.

  References	Class notes
  Exercises
  Reading

  Compensatory for Sept 9
  Further applications of Generating functions. Catalan Numbers using generating functions.
  

  References:

  Class notes

• Theme 3 : Structured Sets : Algebraic Structures - 25 meetings

  • Meeting 28 : Tue, Aug 27, 10:00 am-10:50 am - Jayalal Sarma

  Structured sets. Groups, Groupoid, Monoids, Semi-groups.

  References	The material does not appear as it is in the textbook. <ul> <li>Chapter 11 in [KR], Section 2 & 3</li> </ul>
  Exercises
  Reading

  Structured sets. Groups, Groupoid, Monoids, Semi-groups.
  

  References:

  The material does not appear as it is in the textbook. Chapter 11 in [KR], Section 2 & 3

  • Meeting 29 : Thu, Aug 29, 12:00 pm-12:50 pm - Jayalal Sarma

  Isomorphism. Permutation Group. Subgroups.

  References	The material does not appear as it is in the textbook. <ul> <li>Chapter 11 in [KR], Section 4</li> </ul>
  Exercises
  Reading

  Isomorphism. Permutation Group. Subgroups.
  

  References:

  The material does not appear as it is in the textbook. Chapter 11 in [KR], Section 4

  • Meeting 30 : Tue, Sep 03, 10:00 am-10:50 am - Jayalal Sarma

  Impact of the structure on the cardinality. Lagrange's theorem. Corollaries. <br> Normal Subgroups, Quotient Group Structure.

  References	<ul> <li><a href="http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/coset.pdf">Cosets and Lagrange's Theorem</a></li> </ul>
  Exercises
  Reading

  Impact of the structure on the cardinality. Lagrange's theorem. Corollaries.
  Normal Subgroups, Quotient Group Structure.
  

  References:

  Cosets and Lagrange's Theorem

  • Meeting 31 : Thu, Sep 05, 12:00 pm-12:50 pm - Jayalal Sarma

  Cyclic groups. Generator. Order of an element. Abelian groups. All groups whose size is a prime number are abelian. All cyclic groups are abelian.

  References	Material was (mostly) adapted from : <ul> <li><a href="http://science.kennesaw.edu/~plaval/math4361/groups_cyclic.pdf">Notes - 1 (section 4.2 and part of 4.2)</li> <li>From Chapter 11 in [KR], Section 2 & 3 </ul>
  Exercises
  Reading

  Cyclic groups. Generator. Order of an element. Abelian groups. All groups whose size is a prime number are abelian. All cyclic groups are abelian.
  

  References:

  Material was (mostly) adapted from : Notes - 1 (section 4.2 and part of 4.2) From Chapter 11 in [KR], Section 2 & 3

  • Meeting 32 : Tue, Sep 10, 10:00 am-10:50 am - Jayalal Sarma

  Richer Algebraic Structures. Rings, Integral Domains and Fields. Examples and non-examples. Z_n is an integral domain if and only if n is a prime number. Z_n is a field if and only if n is prime number.

  References	<ul> <li>Chapter 11 of [KR], Section 5.</li> </ul>
  Exercises	In the proof that Z_n is a field if and only if n is a prime number, we did not use the fact that n is a prime, other than using it implicitly while utilizing the fact Z_n is an integral domain. Can you generalize the proof then, to prove that "Any finite integral domain is a field".
  Reading

  Richer Algebraic Structures. Rings, Integral Domains and Fields. Examples and non-examples. Z_n is an integral domain if and only if n is a prime number. Z_n is a field if and only if n is prime number.
  

  References:	Chapter 11 of [KR], Section 5.
  Exercises:	In the proof that Z_n is a field if and only if n is a prime number, we did not use the fact that n is a prime, other than using it implicitly while utilizing the fact Z_n is an integral domain. Can you generalize the proof then, to prove that "Any finite integral domain is a field".

  • Meeting 33 : Tue, Sep 24, 10:00 am-10:50 am - Jayalal Sarma

  Review (after the gap). Application, Check bit idea. A generalization to the case of ISBN numbers. Correcting single digit errors and adjacent swap errors.

  References
  Exercises
  Reading

  Review (after the gap). Application, Check bit idea. A generalization to the case of ISBN numbers. Correcting single digit errors and adjacent swap errors.
  

  References:

  None

  • Meeting 34 : Wed, Sep 25, 09:00 am-09:50 am - Jayalal Sarma

  Netflix challenge - as a running example.<br> The high school notion of a vector - Arrows in plane starting from origin. Deriving properties - Definition of a vector space. Three example sets which are vector spaces :Cartesian Product of R, Space of Matrices, Set of polynomials of degree at most n.

  References	<ul> <li></li> <li>Chapter 2 of [Strang]</li> <li><a href="http://www.maths.lse.ac.uk/Personal/martin/fme2a.pdf">Web source 1</a></li> </ul>
  Exercises
  Reading

  Netflix challenge - as a running example.
  The high school notion of a vector - Arrows in plane starting from origin. Deriving properties - Definition of a vector space. Three example sets which are vector spaces :Cartesian Product of R, Space of Matrices, Set of polynomials of degree at most n.
  

  References:

  Chapter 2 of [Strang] Web source 1

  • Meeting 35 : Thu, Sep 26, 12:00 pm-12:50 pm - Jayalal Sarma

  Vector spaces of matrices. Notion of linear combination. Checking if u is a linear combination of v1, v2, ... v_k. Vector Equations in R^n, and their Equivalence to solving linear equations. Equivalent representations in terms of matrix equation.

  References
  Exercises
  Reading

  Vector spaces of matrices. Notion of linear combination. Checking if u is a linear combination of v1, v2, ... v_k. Vector Equations in R^n, and their Equivalence to solving linear equations. Equivalent representations in terms of matrix equation.
  

  References:

  None

  • Meeting 36 : Mon, Sep 30, 02:00 pm-03:00 pm - Jayalal Sarma

  Compensatory for Short Exam-2. <br> Interpreting Matrix Equation Ax as linear combination of columns and xA as linear combination of rows of A. Interpreting matrix multiplication in two different ways. Gaussian Elimination procedure to solve equations. Interpretation in terms of matrices. LU decomposition of matrices.

  References	<ul> <li>Chapter 1 of Gilbert Strang's Book.</li> </ul>
  Exercises
  Reading

  Compensatory for Short Exam-2.
  Interpreting Matrix Equation Ax as linear combination of columns and xA as linear combination of rows of A. Interpreting matrix multiplication in two different ways. Gaussian Elimination procedure to solve equations. Interpretation in terms of matrices. LU decomposition of matrices.
  

  References:

  Chapter 1 of Gilbert Strang's Book.

  • Meeting 37 : Tue, Oct 01, 09:00 am-09:50 am - Jayalal Sarma

  (Wednesday's Time Table) <br> Under permutations. PA = LU. Example.

  References
  Exercises
  Reading

  (Wednesday's Time Table)
  Under permutations. PA = LU. Example.
  

  References:

  None

  • Meeting 38 : Thu, Oct 03, 12:00 pm-12:50 pm - Jayalal Sarma

  Complexity of Gaussian Elimination procedure. Notion of matrix inverse. Condition for existence of matrix inverse. Gauss-Jordan algorithm to find matrix inverse. Examples.

  References
  Exercises
  Reading

  Complexity of Gaussian Elimination procedure. Notion of matrix inverse. Condition for existence of matrix inverse. Gauss-Jordan algorithm to find matrix inverse. Examples.
  

  References:

  None

  • Meeting 39 : Mon, Oct 07, 11:00 am-11:50 am - Jayalal Sarma

  Span of a set S. Properties of the Span. Span(S) forms a vector subspace. Linear dependence and independence. Examples.

  References
  Exercises
  Reading

  Span of a set S. Properties of the Span. Span(S) forms a vector subspace. Linear dependence and independence. Examples.
  

  References:

  None

  • Meeting 40 : Mon, Oct 07, 02:00 pm-03:00 pm - Jayalal Sarma

  Compensatory lecture for Oct 2nd.<br> Definition of basis. Examples and non-examples.

  References
  Exercises
  Reading

  Compensatory lecture for Oct 2nd.
  Definition of basis. Examples and non-examples.
  

  References:

  None

  • Meeting 41 : Tue, Oct 08, 10:00 am-10:50 am - Jayalal Sarma

  Uniqueness of Size of a basis. Notion of Dimension of a vector space. Co-ordinate system. Standard basis for R^n.

  References
  Exercises
  Reading

  Uniqueness of Size of a basis. Notion of Dimension of a vector space. Co-ordinate system. Standard basis for R^n.
  

  References:

  None

  • Meeting 42 : Wed, Oct 09, 09:00 am-09:50 am - Jayalal Sarma

  How do we find the basis for a the span of a given set of vectors? Row space and Columns space of matrices. Effect of Gaussian Elimination on the row space. Column space of matrices.

  References
  Exercises
  Reading

  How do we find the basis for a the span of a given set of vectors? Row space and Columns space of matrices. Effect of Gaussian Elimination on the row space. Column space of matrices.
  

  References:

  None

  • Meeting 43 : Thu, Oct 10, 12:00 pm-12:50 pm - Jayalal Sarma

  Inner Product, Orthogonality and Norm.

  References	<ul> <li><a href="http://linear.axler.net/Chapter6.pdf">Online resource</a></li> <li>Chapter 3, Page 141-144, of [Strang]</li> </ul>
  Exercises
  Reading

  Inner Product, Orthogonality and Norm.
  

  References:

  Online resource Chapter 3, Page 141-144, of [Strang]

  • Meeting 44 : Mon, Oct 14, 11:00 am-11:50 am - Jayalal Sarma

  Gram-Schmidt Orthogonalization process.

  References	<ul> <li><a href="http://linear.axler.net/Chapter6.pdf">Online resource</a></li> <li>Chapter 3, Page 179-180, of [Strang]</li> </ul>
  Exercises
  Reading

  Gram-Schmidt Orthogonalization process.
  

  References:

  Online resource Chapter 3, Page 179-180, of [Strang]

  • Meeting 45 : Tue, Oct 15, 10:00 am-10:50 am - Jayalal Sarma

  Orthogonal Complements. Three fundamental vector spaces associated with a matrix. Rowspace is orthogonal to Nullspace. Dimension of orthogonal complements add up to the full dimension. Rank-Nullity Theorem.

  References	<ul> What we followed in class was a shorter version of this : <li><a href="http://www.math.ucla.edu/~pskoufra/M115A-DirectSumOfVectorSpaces.pdf">Direct Sum of Vector Spaces</a> (we proved Theorem in Page 6 as our main claim in class)</li> </ul>
  Exercises
  Reading

  Orthogonal Complements. Three fundamental vector spaces associated with a matrix. Rowspace is orthogonal to Nullspace. Dimension of orthogonal complements add up to the full dimension. Rank-Nullity Theorem.
  

  References:

  What we followed in class was a shorter version of this : Direct Sum of Vector Spaces (we proved Theorem in Page 6 as our main claim in class)

  • Meeting 46 : Mon, Oct 21, 11:00 am-11:50 am - Jayalal Sarma

  Rowspace, Columns Space, Nullspace, and Range space of a matrix. Rank of a matrix. Column Rank and Row Rank. Row Rank = Column Rank. Computing the matrix rank.

  References	<ul> <li><a href="http://science.kennesaw.edu/~plaval/math3260/rowcolspaces.pdf">Rowspace, Column space, Nullspace</a></li> <li><a href="www.mtts.org.in/userapps/download-expo.php?fileid=64">Row Rank = Column Rank</a></li> </ul>
  Exercises
  Reading

  Rowspace, Columns Space, Nullspace, and Range space of a matrix. Rank of a matrix. Column Rank and Row Rank. Row Rank = Column Rank. Computing the matrix rank.
  

  References:

  Rowspace, Column space, Nullspace Row Rank = Column Rank

  • Meeting 47 : Mon, Oct 21, 02:00 pm-03:00 pm - Jayalal Sarma

  (Compensatory Lecture for Oct 16th) <br> Computing the basis of the nullspace. Viewing matrices as transformations. Interpretations of the spaces in this context.

  References
  Exercises
  Reading

  (Compensatory Lecture for Oct 16th)
  Computing the basis of the nullspace. Viewing matrices as transformations. Interpretations of the spaces in this context.
  

  References:

  None

  • Meeting 48 : Tue, Oct 22, 10:00 am-10:50 am - Jayalal Sarma

  Invertibility of the transformation. Determinants. Geometric and Algebraic Interpretation of the determinant. Properties (statement). Computing the determinant using the Gaussian elimination.

  References	<ul> There is no exact source for the lectures - however following forms references : <li>Determinants - Properties <a href="http://www.math.brown.edu/~mangahas/det.pdf">Notes 1</a> and <a href="http://science.kennesaw.edu/~plaval/math3260/det2.pdf">Notes 2</a></li> <li><a href="http://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/FINALAPP/Peng.pdf">Determinant - a means to calculate volume</a></li> </ul>
  Exercises	Prove the properties of determinants we used in the class. Write down an O(n^3) time algorithm for computing the determinant of an n x n matrix using the ideas in the class.
  Reading

  Invertibility of the transformation. Determinants. Geometric and Algebraic Interpretation of the determinant. Properties (statement). Computing the determinant using the Gaussian elimination.
  

  References:	There is no exact source for the lectures - however following forms references : Determinants - Properties Notes 1 and Notes 2 Determinant - a means to calculate volume
  Exercises:	Prove the properties of determinants we used in the class. Write down an O(n^3) time algorithm for computing the determinant of an n x n matrix using the ideas in the class.

  • Meeting 49 : Wed, Oct 23, 09:00 am-09:50 am - Jayalal Sarma

  Properties of Matrix Transformation. Notion of Linear Transformation. Properties and Examples. Notion of Kernel and Image of the linear transformation. Rank Nullity Theorem.

  References	<ul> <li><a href="http://math.rice.edu/~hassett/teaching/221fall05/linalg2r.pdf">Linear Transformations and Matrices</a></li> </ul>
  Exercises	<ul> <li>Show that Kernel and Image (or Range) of the linear transformations are subspaces of V and W respectively</li> <li>Show that the polynomial differentiation is indeed a linear transformation</li> </ul>
  Reading

  Properties of Matrix Transformation. Notion of Linear Transformation. Properties and Examples. Notion of Kernel and Image of the linear transformation. Rank Nullity Theorem.
  

  References:	Linear Transformations and Matrices
  Exercises:	Show that Kernel and Image (or Range) of the linear transformations are subspaces of V and W respectively Show that the polynomial differentiation is indeed a linear transformation

  • Meeting 50 : Thu, Oct 24, 12:00 pm-12:50 pm - Jayalal Sarma

  Expressing Linear Transformations as matrices. Examples. Observations on linear transformations. Rotation and Reflection. Linear transformations which behave nicely on certain vectors (as scalar multiplications). Eigen values of a matrix. Eigen spaces, Examples.

  References	<ul> <li>For Eigen values and eigen vectors : <a href="http://math.mit.edu/linearalgebra/ila0601.pdf"></a></li> </ul>
  Exercises
  Reading

  Expressing Linear Transformations as matrices. Examples. Observations on linear transformations. Rotation and Reflection. Linear transformations which behave nicely on certain vectors (as scalar multiplications). Eigen values of a matrix. Eigen spaces, Examples.
  

  References:

  For Eigen values and eigen vectors :

  • Meeting 51 : Mon, Oct 28, 11:00 am-11:50 am - Jayalal Sarma

  Application : Image compression (when the image is nice). Symmetric matrices have real eigen values. Diagonalization of Symmetric matrices. Computing Eigen values. Singular Value Decomposition.

  References
  Exercises
  Reading

  Application : Image compression (when the image is nice). Symmetric matrices have real eigen values. Diagonalization of Symmetric matrices. Computing Eigen values. Singular Value Decomposition.
  

  References:

  None

  • Meeting 52 : Mon, Oct 28, 02:00 pm-03:00 pm - Jayalal Sarma

  Properties of Eigenspaces. Dimensions of the eigen spaces. Eigen decomposition of R^n space. Diagonalizability.

  References
  Exercises
  Reading

  Properties of Eigenspaces. Dimensions of the eigen spaces. Eigen decomposition of R^n space. Diagonalizability.
  

  References:

  None

• Theme 4 : Size Estimates : Discrete Probability Theory - 10 meetings

  • Meeting 53 : Wed, Oct 30, 09:00 am-09:50 am - Jayalal Sarma

  Why study probability. Structure in the uncertain - isnt there a contradiction?. The definition based on the limits. Shortcomings. Axioms of Modern Probability Theory.

  References	[R] : Chapter 2, Sections 2.1, 2.2, 2.3, 2.4
  Exercises	All the basic ones listed in Page 54-66 in [R]
  Reading

  Why study probability. Structure in the uncertain - isnt there a contradiction?. The definition based on the limits. Shortcomings. Axioms of Modern Probability Theory.
  

  References:	[R] : Chapter 2, Sections 2.1, 2.2, 2.3, 2.4
  Exercises:	All the basic ones listed in Page 54-66 in [R]

  • Meeting 54 : Thu, Oct 31, 12:00 pm-12:50 pm - Jayalal Sarma

  Conditional Probability, Multiplication rule. Examples.

  References	Chapter 2 & 3 : Section 2.4, 3.1 and 3.2
  Exercises	Work out the examples from those sections. We did a few in class. But only a few !.
  Reading

  Conditional Probability, Multiplication rule. Examples.
  

  References:	Chapter 2 & 3 : Section 2.4, 3.1 and 3.2
  Exercises:	Work out the examples from those sections. We did a few in class. But only a few !.

  • Meeting 55 : Mon, Nov 04, 11:00 am-11:50 am - Jayalal Sarma

  Baye's Theorem, Example. Independence. Examples.

  References	Chapter 3 in [R]: Section 3.3, 3.4
  Exercises	Work out the examples in [R] section 3.3 and 3.4 and exercises at the end of chapter 3.
  Reading

  Baye's Theorem, Example. Independence. Examples.
  

  References:	Chapter 3 in [R]: Section 3.3, 3.4
  Exercises:	Work out the examples in [R] section 3.3 and 3.4 and exercises at the end of chapter 3.

  • Meeting 56 : Tue, Nov 05, 10:00 am-10:50 am - Jayalal Sarma

  Random Variables and Expectation.

  References	Chapter 4 in [R], Section 4.2, 4.3 and 4.4
  Exercises	Work out the examples from the textbook and exercises at the end of chapter 4.
  Reading

  Random Variables and Expectation.
  

  References:	Chapter 4 in [R], Section 4.2, 4.3 and 4.4
  Exercises:	Work out the examples from the textbook and exercises at the end of chapter 4.

  • Meeting 57 : Wed, Nov 06, 09:00 am-09:50 am - Jayalal Sarma

  Functions of random variables. Linearity of Expectation.

  References	Chapter 4 in [R] - Section 4.5 and 4.6.<br> <a href="http://www2.informatik.hu-berlin.de/alcox/lehre/lvss11/rapm/linearity_expectation.pdf">Notes</a> (section 2.1)<br> Sections 4.7, 4.8 and 4.9.1 in [R].
  Exercises	Work out the examples from the textbook [R] and try exercises at the end of chapter 4 in [R].
  Reading	<a href="http://www2.informatik.hu-berlin.de/alcox/lehre/lvss11/rapm/linearity_expectation.pdf">Notes</a> (section 2.2 and 2.3)

  Functions of random variables. Linearity of Expectation.
  

  References:	Chapter 4 in [R] - Section 4.5 and 4.6. Notes (section 2.1) Sections 4.7, 4.8 and 4.9.1 in [R].
  Exercises:	Work out the examples from the textbook [R] and try exercises at the end of chapter 4 in [R].
  Reading:	Notes (section 2.2 and 2.3)

  • Meeting 58 : Thu, Nov 07, 12:00 pm-12:50 pm - Jayalal Sarma

  Variance. Examples. Four Random Variables - Bernoulli, Binomial, Poisson and Geometric. Parameters, Expected Value and Variance in each case.

  References	Section 4.7, 4.8 and starting portion of 4.9 of the textbook [R]
  Exercises
  Reading

  Variance. Examples. Four Random Variables - Bernoulli, Binomial, Poisson and Geometric. Parameters, Expected Value and Variance in each case.
  

  References:

  Section 4.7, 4.8 and starting portion of 4.9 of the textbook [R]

  • Meeting 59 : Mon, Nov 11, 02:00 pm-03:00 pm - Jayalal Sarma

  Compensatory Lecture for Short Exam #4 <br> Markov's inequality. An application of Markov's Inequality for a Bernoulli Random Variable case. Stronger Tail Inequality. Chebychev Bounds - proof and applications. Better bounds for the Bernoulli case. Even stronger bounds - Chernoff bound. Application to sum of Bernoulli random variables case.

  References	<ul> <li><a href="http://www2.informatik.hu-berlin.de/alcox/lehre/lvss11/rapm/concentration_measure.pdf">Concentration of Measure</a></li> </ul>
  Exercises
  Reading

  Compensatory Lecture for Short Exam #4
  Markov's inequality. An application of Markov's Inequality for a Bernoulli Random Variable case. Stronger Tail Inequality. Chebychev Bounds - proof and applications. Better bounds for the Bernoulli case. Even stronger bounds - Chernoff bound. Application to sum of Bernoulli random variables case.
  

  References:

  Concentration of Measure

  • Meeting 60 : Tue, Nov 12, 10:00 am-10:50 am - Jayalal Sarma

  A general strategy to arrive at stronger tail bounds. Moment generating functions. Applications in the sum of independent Bernoulli random variables case. Proof of Chernoff Bound. <br> What if the variables are not 0-1 valued but symmetrically distributed. Berstein inequality (without proof). <br> What if symmetry isnt available - Azuma's inequality (without proof).

  References	<ul> <li><a href="http://www2.informatik.hu-berlin.de/alcox/lehre/lvss11/rapm/concentration_measure.pdf">Concentration of Measure</a></li> </ul>
  Exercises
  Reading

  A general strategy to arrive at stronger tail bounds. Moment generating functions. Applications in the sum of independent Bernoulli random variables case. Proof of Chernoff Bound.
  What if the variables are not 0-1 valued but symmetrically distributed. Berstein inequality (without proof).
  What if symmetry isnt available - Azuma's inequality (without proof).
  

  References:

  Concentration of Measure

  • Meeting 61 : Wed, Nov 13, 09:00 am-09:50 am - Jayalal Sarma

  Stochastic Processes, Markov property. Markov Chains. Time invariance. States and Transition Probability Matrix. Example Markov Chains

  References
  Exercises
  Reading

  Stochastic Processes, Markov property. Markov Chains. Time invariance. States and Transition Probability Matrix. Example Markov Chains
  

  References:

  None

  • Meeting 62 : Thu, Nov 14, 10:00 am-12:00 pm -

  (Extra Lecture - not a part of the course lecture) <br> Stationary Distribution for Markov Chains. Examples. Connection to Eigen values. Random Walks on Graphs. Spectral Gap. Random walks on graphs with "sepctral gap" mixes well. <br> An important CS application : Google Page Rank Algorithm - Discussion on "when should we consider a page to be important?". A first attempt. Link farm attack. An innovative answer and the connection to Eigen vectors - world's costliest eigen vector - a connection to stationary distribution and hence to the random walk Markov Chain on the web.A few pitfalls and fixes on the idea. Discussion on "How does one compute the pagerank vector?".

  References	<ul> <li><a href="http://www.ams.org/samplings/feature-column/fcarc-pagerank">How Google Finds Your Needle in the Web's Haystack</a> - David Austin</li> </ul>
  Exercises
  Reading

  (Extra Lecture - not a part of the course lecture)
  Stationary Distribution for Markov Chains. Examples. Connection to Eigen values. Random Walks on Graphs. Spectral Gap. Random walks on graphs with "sepctral gap" mixes well.
  An important CS application : Google Page Rank Algorithm - Discussion on "when should we consider a page to be important?". A first attempt. Link farm attack. An innovative answer and the connection to Eigen vectors - world's costliest eigen vector - a connection to stationary distribution and hence to the random walk Markov Chain on the web.A few pitfalls and fixes on the idea. Discussion on "How does one compute the pagerank vector?".
  

  References:

  How Google Finds Your Needle in the Web's Haystack - David Austin

• Theme 5 : Evaluation Meetings - 7 meetings

  • Meeting 63 : Mon, Aug 26, 11:00 am-11:50 am -

  Short Exam #1 <br> Lectures 01-16.

  References
  Exercises
  Reading

  Short Exam #1
  Lectures 01-16.
  

  References:

  None

  • Meeting 64 : Wed, Sep 11, 08:00 am-08:50 am -

  Quiz #1 <br> Syllabus : Lecture 01-20 + Lectures 28-31

  References
  Exercises
  Reading

  Quiz #1
  Syllabus : Lecture 01-20 + Lectures 28-31
  

  References:

  None

  • Meeting 65 : Mon, Sep 30, 11:00 am-11:50 am -

  Short Exam #2 <br> Syllabus : Lecture 21-27 + Lectures 32-35

  References
  Exercises
  Reading

  Short Exam #2
  Syllabus : Lecture 21-27 + Lectures 32-35
  

  References:

  None

  • Meeting 66 : Thu, Oct 17, 08:00 am-08:50 am -

  Quiz #2 <br> Syllabus : Lecture 21-27 + Lectures 32-45

  References
  Exercises
  Reading

  Quiz #2
  Syllabus : Lecture 21-27 + Lectures 32-45
  

  References:

  None

  • Meeting 67 : Tue, Oct 29, 10:00 am-10:50 am -

  Short Exam #3 (Lecture 43 - 52) <img src="http://www.cse.iitm.ac.in/~jayalal/images/updated.gif">

  References
  Exercises
  Reading

  Short Exam #3 (Lecture 43 - 52)
  

  References:

  None

  • Meeting 68 : Mon, Nov 11, 11:00 am-11:50 am -

  Short Exam #4 (Lectures 53-58)

  References
  Exercises
  Reading

  Short Exam #4 (Lectures 53-58)
  

  References:

  None

  • Meeting 69 : Fri, Nov 22, 01:00 pm-04:00 pm -

  Endsemester Examination

  References
  Exercises
  Reading

  Endsemester Examination
  

  References:

  None