Meetings

Click on the theme item for the meeting plan for that theme.Click on the meeting item for references, exercises, and additional reading related to it.

**Theme 1 : Describing Sets : Logic & Proofs**- 16 meetings- Meeting 01 : Mon, Jul 29, 11:00 am-11:50 am -
- Meeting 02 : Tue, Jul 30, 10:00 am-10:50 am - Raghavendra Rao
- Meeting 03 : Wed, Jul 31, 09:00 am-09:50 am - Raghavendra Rao
- Meeting 04 : Thu, Aug 01, 12:00 pm-12:50 pm - Raghavendra Rao
- Meeting 05 : Mon, Aug 05, 11:00 am-11:50 am - Raghavendra Rao
- Meeting 06 : Tue, Aug 06, 10:00 am-10:50 am - Raghavendra Rao
- Meeting 07 : Wed, Aug 07, 09:00 am-09:50 am - Raghavendra Rao
- Meeting 08 : Thu, Aug 08, 12:00 pm-12:50 pm - Raghavendra Rao
- Meeting 09 : Mon, Aug 12, 11:00 am-11:50 am - Raghavendra Rao
- Meeting 10 : Mon, Aug 12, 02:00 pm-03:00 pm - Raghavendra Rao
- Meeting 11 : Tue, Aug 13, 10:00 am-10:50 am - Raghavendra Rao
- Meeting 12 : Wed, Aug 14, 09:00 am-09:50 am - Raghavendra Rao
- Meeting 13 : Mon, Aug 19, 11:00 am-11:50 am - Raghavendra Rao
- Meeting 14 : Tue, Aug 20, 10:00 am-10:50 am - Raghavendra Rao
- Meeting 15 : Wed, Aug 21, 09:00 am-09:50 am - Raghavendra Rao
- Meeting 16 : Thu, Aug 22, 12:00 pm-12:50 pm - Raghavendra Rao

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]. 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 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. 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]. 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]. 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? ExamplesReferences: The material is from [KR], and examples are taken from various sources. Reading: Invalid Proof Techniques 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. 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 paradoxUnion 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 setReferences: [KR] pages 169-173.

Cardinality Notes by M WilliamsCompensatory 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 WilliamsUncountability 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 WilliamsFurther 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.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. 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.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 inductionFurther 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
- Meeting 18 : Wed, Aug 28, 09:00 am-09:50 am - Raghavendra Rao
- Meeting 19 : Mon, Sep 02, 11:00 am-11:50 am - Raghavendra Rao
- Meeting 20 : Wed, Sep 04, 09:00 am-09:50 am - Raghavendra Rao
- Meeting 21 : Thu, Sep 12, 12:00 pm-12:50 pm - Raghavendra Rao
- Meeting 22 : Mon, Sep 16, 11:00 am-11:50 am - Raghavendra Rao
- Meeting 23 : Tue, Sep 17, 10:00 am-10:50 am - Raghavendra Rao
- Meeting 24 : Wed, Sep 18, 09:00 am-09:50 am - Raghavendra Rao
- Meeting 25 : Thu, Sep 19, 12:00 pm-12:50 pm - Raghavendra Rao
- Meeting 26 : Mon, Sep 23, 11:00 am-11:50 am - Raghavendra Rao
- Meeting 27 : Mon, Sep 23, 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]. 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] 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.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] 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 RelationsReferences: Sections 6.1 and 6.2 of [KR] 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] 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] 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] 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] 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 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
- Chapter 11 in [KR], Section 2 & 3
- Meeting 29 : Thu, Aug 29, 12:00 pm-12:50 pm - Jayalal Sarma
- Chapter 11 in [KR], Section 4
- Meeting 30 : Tue, Sep 03, 10:00 am-10:50 am - Jayalal Sarma
- Meeting 31 : Thu, Sep 05, 12:00 pm-12:50 pm - Jayalal Sarma
- Meeting 32 : Tue, Sep 10, 10:00 am-10:50 am - Jayalal Sarma
- Chapter 11 of [KR], Section 5.
- Meeting 33 : Tue, Sep 24, 10:00 am-10:50 am - Jayalal Sarma
- Meeting 34 : Wed, Sep 25, 09:00 am-09:50 am - Jayalal Sarma
- Chapter 2 of [Strang]
- Web source 1
- Meeting 35 : Thu, Sep 26, 12:00 pm-12:50 pm - Jayalal Sarma
- Meeting 36 : Mon, Sep 30, 02:00 pm-03:00 pm - Jayalal Sarma
- Chapter 1 of Gilbert Strang's Book.
- Meeting 37 : Tue, Oct 01, 09:00 am-09:50 am - Jayalal Sarma
- Meeting 38 : Thu, Oct 03, 12:00 pm-12:50 pm - Jayalal Sarma
- Meeting 39 : Mon, Oct 07, 11:00 am-11:50 am - Jayalal Sarma
- Meeting 40 : Mon, Oct 07, 02:00 pm-03:00 pm - Jayalal Sarma
- Meeting 41 : Tue, Oct 08, 10:00 am-10:50 am - Jayalal Sarma
- Meeting 42 : Wed, Oct 09, 09:00 am-09:50 am - Jayalal Sarma
- Meeting 43 : Thu, Oct 10, 12:00 pm-12:50 pm - Jayalal Sarma
- Online resource
- Chapter 3, Page 141-144, of [Strang]
- Meeting 44 : Mon, Oct 14, 11:00 am-11:50 am - Jayalal Sarma
- Online resource
- Chapter 3, Page 179-180, of [Strang]
- Meeting 45 : Tue, Oct 15, 10:00 am-10:50 am - Jayalal Sarma
- 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
- Meeting 47 : Mon, Oct 21, 02:00 pm-03:00 pm - Jayalal Sarma
- Meeting 48 : Tue, Oct 22, 10:00 am-10:50 am - Jayalal Sarma
- Determinants - Properties Notes 1 and Notes 2
- Determinant - a means to calculate volume
- Meeting 49 : Wed, Oct 23, 09:00 am-09:50 am - Jayalal Sarma
- 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
- Meeting 51 : Mon, Oct 28, 11:00 am-11:50 am - Jayalal Sarma
- Meeting 52 : Mon, Oct 28, 02:00 pm-03:00 pm - 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. 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. 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: 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 : 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: 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". 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 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: 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 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: (Wednesday's Time Table) <br> Under permutations. PA = LU. Example. References Exercises Reading (Wednesday's Time Table)

Under permutations. PA = LU. Example.References: None 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 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 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 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 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 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: 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: 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 :

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.(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 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 :

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. 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: Exercises: 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.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 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
- Meeting 54 : Thu, Oct 31, 12:00 pm-12:50 pm - Jayalal Sarma
- Meeting 55 : Mon, Nov 04, 11:00 am-11:50 am - Jayalal Sarma
- Meeting 56 : Tue, Nov 05, 10:00 am-10:50 am - Jayalal Sarma
- Meeting 57 : Wed, Nov 06, 09:00 am-09:50 am - Jayalal Sarma
- Meeting 58 : Thu, Nov 07, 12:00 pm-12:50 pm - Jayalal Sarma
- Meeting 59 : Mon, Nov 11, 02:00 pm-03:00 pm - Jayalal Sarma
- Meeting 60 : Tue, Nov 12, 10:00 am-10:50 am - Jayalal Sarma
- Meeting 61 : Wed, Nov 13, 09:00 am-09:50 am - Jayalal Sarma
- Meeting 62 : Thu, Nov 14, 10:00 am-12:00 pm -
- How Google Finds Your Needle in the Web's Haystack - David Austin

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] 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 !. 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. 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. 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.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] 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: 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: 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 ChainsReferences: None (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: **Theme 5 : Evaluation Meetings**- 7 meetings- Meeting 63 : Mon, Aug 26, 11:00 am-11:50 am -
- Meeting 64 : Wed, Sep 11, 08:00 am-08:50 am -
- Meeting 65 : Mon, Sep 30, 11:00 am-11:50 am -
- Meeting 66 : Thu, Oct 17, 08:00 am-08:50 am -
- Meeting 67 : Tue, Oct 29, 10:00 am-10:50 am -
- Meeting 68 : Mon, Nov 11, 11:00 am-11:50 am -
- Meeting 69 : Fri, Nov 22, 01:00 pm-04:00 pm -

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

Lectures 01-16.References: None Quiz #1 <br> Syllabus : Lecture 01-20 + Lectures 28-31 References Exercises Reading Quiz #1

Syllabus : Lecture 01-20 + Lectures 28-31References: None Short Exam #2 <br> Syllabus : Lecture 21-27 + Lectures 32-35 References Exercises Reading Short Exam #2

Syllabus : Lecture 21-27 + Lectures 32-35References: None Quiz #2 <br> Syllabus : Lecture 21-27 + Lectures 32-45 References Exercises Reading Quiz #2

Syllabus : Lecture 21-27 + Lectures 32-45References: None 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 Short Exam #4 (Lectures 53-58) References Exercises Reading Short Exam #4 (Lectures 53-58)References: None Endsemester Examination References Exercises Reading Endsemester ExaminationReferences: None