CS6030 - Mathematical Concepts for Computer Science

Meetings  

• Theme 1 : Describing sets: Logic and Proofs - 17 meetings

  • Meeting 01 : Wed, Jul 30, 12:00 pm-12:55 pm - Raghavendra Rao

  Administrative Announcements. Organization of the course and evaluation scheme. Review of Some basic concepts in discrete mathematics: Sets, Functions, and relations.

  References
  Exercises
  Reading

  Administrative Announcements. Organization of the course and evaluation scheme. Review of Some basic concepts in discrete mathematics: Sets, Functions, and relations.
  

  References:

  None

  • Meeting 02 : Fri, Aug 01, 11:00 am-11:50 am - Raghavendra Rao

  TA Introduction, Grouping. Review of some discrete mathematical concepts: Sets, relations, Functions etc.

  References
  Exercises
  Reading

  TA Introduction, Grouping. Review of some discrete mathematical concepts: Sets, relations, Functions etc.
  

  References:

  None

  • Meeting 03 : Mon, Aug 04, 09:00 am-09:50 am - Jayalal Sarma

  Intel FDIV Bug, M$ Blue screens - the need for a formal set up for arguing about systems we design. The problems ultimately boils down to describing and reasoning about some sets. Quick history on propositional logic. Laws of thought. Truth Table. Tautologies, Contradictions and Contingents. Real world examples.

  References	Section 1.1 in Rosen's Textbook.
  Exercises	Think of a logic which might be able represent statements like "Alice knows that Bob ate the pie".
  Reading	<ul> <li><a href="http://en.wikipedia.org/wiki/Pentium_FDIV_bug">Pentium FDIV Bug</a></li> <li>The Classic : <a href="www.gutenberg.org/files/15114/15114-pdf.pdf">An Investigation of the Laws of Thought, by George Boole.</a></li> <li></li> </ul>

  Intel FDIV Bug, M$ Blue screens - the need for a formal set up for arguing about systems we design. The problems ultimately boils down to describing and reasoning about some sets. Quick history on propositional logic. Laws of thought. Truth Table. Tautologies, Contradictions and Contingents. Real world examples.
  

  References:	Section 1.1 in Rosen's Textbook.
  Exercises:	Think of a logic which might be able represent statements like "Alice knows that Bob ate the pie".
  Reading:	Pentium FDIV Bug The Classic : An Investigation of the Laws of Thought, by George Boole.

  • Meeting 04 : Tue, Aug 05, 08:00 am-08:50 am - Jayalal Sarma

  Logical Implications and Equivalences. Practical Applications. Arguments, Argument forms. Validity of an argument. Fallacious Arguments. Propositional Proofs.

  References	Section 1.5 in Rosen's Textbook.
  Exercises
  Reading

  Logical Implications and Equivalences. Practical Applications. Arguments, Argument forms. Validity of an argument. Fallacious Arguments. Propositional Proofs.
  

  References:

  Section 1.5 in Rosen's Textbook.

  • Meeting 05 : Wed, Aug 06, 12:00 pm-12:50 pm - Jayalal Sarma

  Rules of inferences. Composing valid arguments to build proofs. Resolution as a single universal rule of inference. Principle of resolution. Prolog. The limitations of propositional logic.

  References	[KR]
  Exercises
  Reading

  Rules of inferences. Composing valid arguments to build proofs. Resolution as a single universal rule of inference. Principle of resolution. Prolog. The limitations of propositional logic.
  

  References:

  [KR]

  • Meeting 06 : Fri, Aug 08, 11:00 am-11:50 am - Jayalal Sarma

  Need of predicate logic. Quantifiers and Domains of discourse. Interaction between quantifiers between themselves propositional operators. Rules of inference in predicate logic. Example application. First and Second order Logics. Axioms + Rules of inferences. The structure of a proof.

  References	[KR]
  Exercises
  Reading

  Need of predicate logic. Quantifiers and Domains of discourse. Interaction between quantifiers between themselves propositional operators. Rules of inference in predicate logic. Example application. First and Second order Logics. Axioms + Rules of inferences. The structure of a proof.
  

  References:

  [KR]

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

  Various proof techniques: direct proof with two examples. Proof by examples:pitfalls.

  References	[KR] Section 1.6
  Exercises
  Reading

  Various proof techniques: direct proof with two examples. Proof by examples:pitfalls.
  

  References:

  [KR] Section 1.6

  • Meeting 08 : Tue, Aug 12, 08:00 am-08:50 am -

  Indirect proof with examples. Proof by contradiction. How to identify the contradiction? Examples.

  References	[KR] Section 1.6 and 1.8.
  Exercises
  Reading	<a href="http://www.stat.nus.edu.sg/~statba/humour/invalid.proofs.html"> Invalid proof techniques</a> Gives a list of reasons why a proof could be invalid.

  Indirect proof with examples. Proof by contradiction. How to identify the contradiction? Examples.
  

  References:	[KR] Section 1.6 and 1.8.
  Reading:	Invalid proof techniques Gives a list of reasons why a proof could be invalid.

  • Meeting 09 : Wed, Aug 13, 06:00 am-06:00 am -

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

  References	[KR] Sections 1.6 and 1.8.
  Exercises
  Reading

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

  References:

  [KR] Sections 1.6 and 1.8.

  • Meeting 10 : Mon, Aug 18, 09:00 am-09:50 am -

  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 sets </a>, notes by Michael Williams.
  Exercises
  Reading	<a href="http://www.scs.ryerson.ca/~mth110/Handouts/PD/russell.pdf"> Relation between Russell's paradox and uncountability theory. </a> <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 sets , notes by Michael Williams.
  Reading:	Relation between Russell's paradox and uncountability theory. On the origins of Russell's paradox.

  • Meeting 11 : Mon, Aug 18, 04:45 pm-05:35 pm -

  Set of rational numbers is a countably infinite set. Union of countably infinite sets. Enumerability is equivalent to countability. <br> <i> Compensation for Aug 15 </i>

  References	<a href="http://www.math.ucla.edu/~mwilliams/cardinality.pdf"> Cardinality of sets </a>, notes by Michael Williams.
  Exercises
  Reading

  Set of rational numbers is a countably infinite set. Union of countably infinite sets. Enumerability is equivalent to countability.
  Compensation for Aug 15
  

  References:

  Cardinality of sets , notes by Michael Williams.

  • Meeting 12 : Tue, Aug 19, 08:00 am-08:50 am -

  Uncountability of the set of real numbers: Cantor's diagonalization argument.

  References	<a href="http://www.math.ucla.edu/~mwilliams/cardinality.pdf"> Cardinality of sets </a>, notes by Michael Williams. Also see [KR].
  Exercises
  Reading

  Uncountability of the set of real numbers: Cantor's diagonalization argument.
  

  References:

  Cardinality of sets , notes by Michael Williams. Also see [KR].

  • Meeting 13 : Wed, Aug 20, 12:00 pm-01:00 pm -

  Can the cardinality Natural number be equal to that of its power set? Introduction to Mathematical induction.

  References	<a href="http://www.math.ucla.edu/~mwilliams/cardinality.pdf"> Cardinality of sets </a>, notes by Michael Williams.
  Exercises
  Reading

  Can the cardinality Natural number be equal to that of its power set? Introduction to Mathematical induction.
  

  References:

  Cardinality of sets , notes by Michael Williams.

  • Meeting 14 : Fri, Aug 22, 11:00 am-11:50 am -

  The principle of mathematical induction. Proof by induction. Strong induction. Example.

  References	Section 4.1 of [KR]
  Exercises
  Reading

  The principle of mathematical induction. Proof by induction. Strong induction. Example.
  

  References:

  Section 4.1 of [KR]

  • Meeting 15 : Mon, Aug 25, 04:45 pm-05:35 pm -

  The well ordering axiom. An example application. Equivalence to the principle of mathematical Induction.

  References	Section 4.2 in <a href="http://math.berkeley.edu/~hutching/teach/proofs.pdf"> Mathematical Proofs </a>, Notes by M Hutchings.
  Exercises
  Reading

  The well ordering axiom. An example application. Equivalence to the principle of mathematical Induction.
  

  References:

  Section 4.2 in Mathematical Proofs , Notes by M Hutchings.

  • Meeting 16 : Tue, Aug 26, 08:00 am-08:50 am -

  Well ordering principle: an example of a proof using WOP. More proofs by induction: Survivor in a knife fight game.

  References	Example 12 in page 286 of [KR].
  Exercises
  Reading

  Well ordering principle: an example of a proof using WOP. More proofs by induction: Survivor in a knife fight game.
  

  References:

  Example 12 in page 286 of [KR].

  • Meeting 17 : Wed, Aug 27, 09:00 am-09:50 am -

  Fallacies in mathematical induction-- pitfalls in inductions proofs. Further application of diagonalization: Computability. Halting problem is not computable.

  References	<a href="http://www.math.uiuc.edu/~hildebr/347/induction3.pdf"> Fallacies in Induction </a> by AJ Hildebrand. For undecidability of the halting problem: <a href="http://inst.eecs.berkeley.edu/~cs70/sp07/lec/lecture27.pdf"> Lecture Notes </a> by Luca Trevisan.
  Exercises
  Reading

  Fallacies in mathematical induction-- pitfalls in inductions proofs. Further application of diagonalization: Computability. Halting problem is not computable.
  

  References:

  Fallacies in Induction by AJ Hildebrand. For undecidability of the halting problem: Lecture Notes by Luca Trevisan.

• Theme 2 : Size of the Sets: Counting and Combinatorics - 13 meetings

  • Meeting 18 : Mon, Sep 01, 09:00 am-09:50 am -

  Basic counting techniques: Sum rule, Product rule, and the Inclusion Exclusion (without proof). The pigeonhole principle. Examples.

  References	[KR], Chapter 5.
  Exercises
  Reading

  Basic counting techniques: Sum rule, Product rule, and the Inclusion Exclusion (without proof). The pigeonhole principle. Examples.
  

  References:

  [KR], Chapter 5.

  • Meeting 19 : Wed, Sep 03, 12:00 pm-01:00 pm -

  Applications of PHP: non-existence of lossless data compression algorithms. More applications of PHP.

  References	For lossless data compression see <a href="http://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/08/Small08.pdf">Slides </a> from a similar course.
  Exercises
  Reading

  Applications of PHP: non-existence of lossless data compression algorithms. More applications of PHP.
  

  References:

  For lossless data compression see Slides from a similar course.

  • Meeting 20 : Fri, Sep 05, 11:00 am-11:50 am -

  A brief introduction to Ramsey type theorems: R(3,3). A proof from the THE Book.

  References	Martin Aigner and Gunter Ziegler "Proofs from THE BOOK"
  Exercises
  Reading

  A brief introduction to Ramsey type theorems: R(3,3). A proof from the THE Book.
  

  References:

  Martin Aigner and Gunter Ziegler "Proofs from THE BOOK"

  • Meeting 21 : Mon, Sep 08, 09:00 am-09:50 am -

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

  References	[KR], Chapter 5
  Exercises
  Reading

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

  References:

  [KR], Chapter 5

  • Meeting 22 : Mon, Sep 08, 04:45 pm-05:35 pm -

  Double Counting: More examples. <i> Compensation for Oct 3</i>

  References	[KR]
  Exercises
  Reading

  Double Counting: More examples. Compensation for Oct 3
  

  References:

  [KR]

  • Meeting 23 : Tue, Sep 09, 10:00 am-10:50 am -

  Recurrence relations. Example: A recurrence for the number of Derangements. Linear Homogeneous Recurrence Relations. <br>

  References	[KR] Sections 6.1 and 6.2
  Exercises
  Reading

  Recurrence relations. Example: A recurrence for the number of Derangements. Linear Homogeneous Recurrence Relations.
  
  

  References:

  [KR] Sections 6.1 and 6.2

  • Meeting 24 : Wed, Sep 10, 12:00 pm-01:00 pm -

  Linear Homogeneous Recurrence Relations - Distinct roots case, examples.

  References	[KR] Chapter 6.
  Exercises
  Reading

  Linear Homogeneous Recurrence Relations - Distinct roots case, examples.
  

  References:

  [KR] Chapter 6.

  • Meeting 25 : Fri, Sep 12, 11:00 am-11:50 am -

  Linear Homogeneous Recurrence Relations - higher multiplicity (Without proof). General form with multiple roots with higher multiplicities. Linear non-homogeneous recurrences: without proof.

  References	[KR] Chapter 6.
  Exercises
  Reading

  Linear Homogeneous Recurrence Relations - higher multiplicity (Without proof). General form with multiple roots with higher multiplicities. Linear non-homogeneous recurrences: without proof.
  

  References:

  [KR] Chapter 6.

  • Meeting 26 : Mon, Sep 15, 09:00 am-09:50 am -

  Linear non-homogeneous recurrences: without proof.

  References	[KR]
  Exercises
  Reading

  Linear non-homogeneous recurrences: without proof.
  

  References:

  [KR]

  • Meeting 27 : Tue, Sep 16, 08:00 am-08:50 am -

  Generating Functions Method I. Generating functions as power series. Operations + and * on power series.

  References	[KR]
  Exercises
  Reading

  Generating Functions Method I. Generating functions as power series. Operations + and * on power series.
  

  References:

  [KR]

  • Meeting 28 : Wed, Sep 17, 12:00 pm-01:00 pm -

  More on generating functions. Obtaining generating functions. Applications to counting: number of r-combinations with repetitions.

  References	[KR]
  Exercises
  Reading

  More on generating functions. Obtaining generating functions. Applications to counting: number of r-combinations with repetitions.
  

  References:

  [KR]

  • Meeting 29 : Fri, Sep 19, 11:00 am-11:50 am -

  Extended binomial theorem. Example applications of Generating Functions Method II. Counting the number of spanning trees in a Fan-graph of order n.

  References	[KR]. For counting spanning trees see <a href="http://www.math.ualberta.ca/~isaac/cmput204/s00/fan_graphs.ps"> here</a>
  Exercises
  Reading

  Extended binomial theorem. Example applications of Generating Functions Method II. Counting the number of spanning trees in a Fan-graph of order n.
  

  References:

  [KR]. For counting spanning trees see here

  • Meeting 30 : Mon, Sep 22, 04:45 pm-05:40 pm -

  Generating functions: Counting the number of spanning trees in a fan of order n. <i> Compensation for SE-2.</i>

  References
  Exercises
  Reading

  Generating functions: Counting the number of spanning trees in a fan of order n. Compensation for SE-2.
  

  References:

  None

• Theme 3 : Structured sets : Algebraic Structures - 19 meetings

  • Meeting 31 : Tue, Sep 23, 08:00 am-08:50 am -

  Introduction to structured sets: Algebraic structures. Groups, semigrous: definitions.

  References	[KR]. You can also refer to Chapter on groups of any book on Modern Algebra, e.g., Herstein's "Introduction to Algebra". But these books might be more abstract than what we have seen in the class.
  Exercises
  Reading

  Introduction to structured sets: Algebraic structures. Groups, semigrous: definitions.
  

  References:

  [KR]. You can also refer to Chapter on groups of any book on Modern Algebra, e.g., Herstein's "Introduction to Algebra". But these books might be more abstract than what we have seen in the class.

  • Meeting 32 : Wed, Sep 24, 06:00 am-06:00 am -

  Subgroups. Size of a subgroup of a finite group: Lagrange's theorem.

  References	[KR] Chapter 11, Section 4.
  Exercises
  Reading

  Subgroups. Size of a subgroup of a finite group: Lagrange's theorem.
  

  References:

  [KR] Chapter 11, Section 4.

  • Meeting 33 : Fri, Sep 26, 11:00 am-11:50 am -

  Lagrange's theorem (Contd). Permutation groups:. Generating sets, Graph Automorphism group.

  References	[KR]. No reference for Graph automorphisms. You can also look into "Groups" chapter in Herstein's book. Also, Freleigh's Introduction to Abstract Algebra has a good exposition on Groups.
  Exercises
  Reading

  Lagrange's theorem (Contd). Permutation groups:. Generating sets, Graph Automorphism group.
  

  References:

  [KR]. No reference for Graph automorphisms. You can also look into "Groups" chapter in Herstein's book. Also, Freleigh's Introduction to Abstract Algebra has a good exposition on Groups.

  • Meeting 34 : Mon, Sep 29, 11:00 am-11:50 am -

  Cyclic groups. Abelian groups. Examples. Cyclic groups are abelian. Normal Subgroups. Coset structure of normal subgroups. Isomorphisms.

  References	[KR]. Also see [Herstein]
  Exercises
  Reading

  Cyclic groups. Abelian groups. Examples. Cyclic groups are abelian. Normal Subgroups. Coset structure of normal subgroups. Isomorphisms.
  

  References:

  [KR]. Also see [Herstein]

  • Meeting 35 : Tue, Sep 30, 08:00 am-08:50 am -

  More structured sets: Rings. Examples. Integral domains. Fields. Examples.

  References	You can look into [KR], or first section of Chapter on rings in any book on abstract algebra. Though it is best advised to refer to your own notes from the class.
  Exercises	Try exercises at the end of Chapter on rings in Herstein's Algebraa book.
  Reading

  More structured sets: Rings. Examples. Integral domains. Fields. Examples.
  

  References:	You can look into [KR], or first section of Chapter on rings in any book on abstract algebra. Though it is best advised to refer to your own notes from the class.
  Exercises:	Try exercises at the end of Chapter on rings in Herstein's Algebraa book.

  • Meeting 36 : Wed, Oct 01, 06:00 am-06:00 am -

  Introduction to vectors: first notion of vectors. Definition of vector space. Examples: Cartesian product of a field, polynomials of degree n, functions over reals. Properties of a vector space.

  References	[S].
  Exercises
  Reading

  Introduction to vectors: first notion of vectors. Definition of vector space. Examples: Cartesian product of a field, polynomials of degree n, functions over reals. Properties of a vector space.
  

  References:

  [S].

  • Meeting 37 : Tue, Oct 07, 08:00 am-08:50 am -

  Notion of a subspace. Properties of a subspace. Notion of linear combinations. Linear combinations and relations to linear equations. Notion of linear independence and dependence.

  References	[S]. Also please use your class notes. "Linear Algebra" by Friedberg, Insel and Spence is also a good reference. Some of the definitions and examples are taken from this book.
  Exercises	For TRUE/FALSE type questions please check the exercises at the end of each section in Friedberg-Insel-Spence. Also try other exercises therein.
  Reading

  Notion of a subspace. Properties of a subspace. Notion of linear combinations. Linear combinations and relations to linear equations. Notion of linear independence and dependence.
  

  References:	[S]. Also please use your class notes. "Linear Algebra" by Friedberg, Insel and Spence is also a good reference. Some of the definitions and examples are taken from this book.
  Exercises:	For TRUE/FALSE type questions please check the exercises at the end of each section in Friedberg-Insel-Spence. Also try other exercises therein.

  • Meeting 38 : Wed, Oct 08, 06:00 am-06:00 am -

  Examples. Basis of a vector space. All bases are of the same cardinality. Notion of Dimension. Definition and examples.

  References	[S]."Linear Algebra" by Friedberg, Insel and Spence is also a good reference. Some of the definitions and examples are taken from this book.
  Exercises
  Reading

  Examples. Basis of a vector space. All bases are of the same cardinality. Notion of Dimension. Definition and examples.
  

  References:

  [S]."Linear Algebra" by Friedberg, Insel and Spence is also a good reference. Some of the definitions and examples are taken from this book.

  • Meeting 39 : Fri, Oct 10, 11:00 am-11:50 am -

  Notion of dimension. Examples. Linear transformations--matrices.

  References	[S]. Also please use your class notes. "Linear Algebra" by Friedberg, Insel and Spence is also a good reference. Some of the definitions and examples are taken from this book.
  Exercises
  Reading

  Notion of dimension. Examples. Linear transformations--matrices.
  

  References:

  [S]. Also please use your class notes. "Linear Algebra" by Friedberg, Insel and Spence is also a good reference. Some of the definitions and examples are taken from this book.

  • Meeting 40 : Mon, Oct 13, 09:00 am-09:50 am -

  Linear Transformations: Null space and range spaces. Rank nullity theorem. Linear transformations as matrices.

  References	[S]. "Linear Algebra" by Friedberg, Insel and Spence is also a good reference. The definitions and examples used in the class are taken from this book.
  Exercises	For TRUE/FALSE type questions please check the exercises at the end of each section in Friedberg-Insel-Spence.
  Reading

  Linear Transformations: Null space and range spaces. Rank nullity theorem. Linear transformations as matrices.
  

  References:	[S]. "Linear Algebra" by Friedberg, Insel and Spence is also a good reference. The definitions and examples used in the class are taken from this book.
  Exercises:	For TRUE/FALSE type questions please check the exercises at the end of each section in Friedberg-Insel-Spence.

  • Meeting 41 : Wed, Oct 15, 06:00 am-06:00 am -

  Matrices as linear transformations. More on matrices.

  References	inear Algebra by Friedbrg-Insel-Spence. Also see [S]
  Exercises	For TRUE/FALSE type questions please check the exercises at the end of each section in Friedberg-Insel-Spence.
  Reading

  Matrices as linear transformations. More on matrices.
  

  References:	inear Algebra by Friedbrg-Insel-Spence. Also see [S]
  Exercises:	For TRUE/FALSE type questions please check the exercises at the end of each section in Friedberg-Insel-Spence.

  • Meeting 42 : Fri, Oct 17, 11:00 am-11:50 am -

  Matrix multiplication is equivalent to composition of linear transformations. System of Linear equations-two interpetations. Solving system of linear equations: Gaussian elimination

  References	Linear Algebra by Friedbrg-Insel-Spence. Also see [S]
  Exercises	For TRUE/FALSE type questions please check the exercises at the end of each section in Friedberg-Insel-Spence. Similar review questions are available in the problems sub-section of [S] at the end of each section.
  Reading

  Matrix multiplication is equivalent to composition of linear transformations. System of Linear equations-two interpetations. Solving system of linear equations: Gaussian elimination
  

  References:	Linear Algebra by Friedbrg-Insel-Spence. Also see [S]
  Exercises:	For TRUE/FALSE type questions please check the exercises at the end of each section in Friedberg-Insel-Spence. Similar review questions are available in the problems sub-section of [S] at the end of each section.

  • Meeting 43 : Mon, Oct 20, 09:00 am-09:50 am -

  Systems of linear equations (contd). Rank of a matrix. A normal form for a rank r matrix. A characterization of feasibility of linear equations (Without proof).

  References	"Linear Algebra" By Friedberg, Insel and Spence. Also see [S]
  Exercises
  Reading

  Systems of linear equations (contd). Rank of a matrix. A normal form for a rank r matrix. A characterization of feasibility of linear equations (Without proof).
  

  References:

  "Linear Algebra" By Friedberg, Insel and Spence. Also see [S]

  • Meeting 44 : Tue, Oct 21, 08:00 am-08:50 am -

  Notion of determinant. Properties of determinant (without proof). Inverse of a matrix.

  References	Friedberg-Insel-Spence.
  Exercises
  Reading

  Notion of determinant. Properties of determinant (without proof). Inverse of a matrix.
  

  References:

  Friedberg-Insel-Spence.

  • Meeting 45 : Fri, Oct 24, 11:00 am-11:50 am -

  Elementary operations as pre (post) multiplication by matrices. Multiplication by a non-sinular matrix does not change the rank. Computing inverse of a matrix using Gaussian elimination.

  References	Friedberg-Insel-Spence.
  Exercises
  Reading

  Elementary operations as pre (post) multiplication by matrices. Multiplication by a non-sinular matrix does not change the rank. Computing inverse of a matrix using Gaussian elimination.
  

  References:

  Friedberg-Insel-Spence.

  • Meeting 46 : Mon, Oct 27, 04:45 pm-05:35 pm -

  More on orthogonality: Null space is orthogonal to range space. Notion of an orthogonal basis. Gram-Schmidt orthogonalization. Spaces orthogonal to a subspace. Eigen spaces and Eigen values. <i> Compensation for Short Exam -3</i>

  References	Friedberg-Insel-Spence.
  Exercises
  Reading

  More on orthogonality: Null space is orthogonal to range space. Notion of an orthogonal basis. Gram-Schmidt orthogonalization. Spaces orthogonal to a subspace. Eigen spaces and Eigen values. Compensation for Short Exam -3
  

  References:

  Friedberg-Insel-Spence.

  • Meeting 47 : Tue, Oct 28, 08:00 am-08:50 am -

  Eigen Values and Eigen vectors of a matrix.

  References	Friedberg-Insel-Spence.
  Exercises
  Reading

  Eigen Values and Eigen vectors of a matrix.
  

  References:

  Friedberg-Insel-Spence.

  • Meeting 48 : Wed, Oct 29, 12:00 pm-12:30 pm -

  More on Eigen spaces. Eigen vectors corresponding to distinct Eigen values are linearly independent. <br> <i> TCF forms will be given. </i>

  References	Friedberg-Insel-Spence.
  Exercises
  Reading

  More on Eigen spaces. Eigen vectors corresponding to distinct Eigen values are linearly independent.
  TCF forms will be given.
  

  References:

  Friedberg-Insel-Spence.

  • Meeting 49 : Fri, Oct 31, 11:00 am-11:50 am -

  Some sample applications of linear algebra. Introduction to Probability. Why probability?

  References
  Exercises
  Reading

  Some sample applications of linear algebra. Introduction to Probability. Why probability?
  

  References:

  None

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

  • Meeting 50 : Mon, Nov 03, 09:00 am-09:50 am -

  Sample space and events. Axioms of probability. Conditional probability.

  References	[S].
  Exercises	Look at the examples and exercises given in [S].
  Reading

  Sample space and events. Axioms of probability. Conditional probability.
  

  References:	[S].
  Exercises:	Look at the examples and exercises given in [S].

  • Meeting 51 : Wed, Nov 05, 12:00 pm-01:00 pm -

  Notion of independence. Notion of random variables. Expectation and Variance. Examples of continuous and discrete random variables.

  References	[S].
  Exercises
  Reading

  Notion of independence. Notion of random variables. Expectation and Variance. Examples of continuous and discrete random variables.
  

  References:

  [S].

  • Meeting 52 : Fri, Nov 07, 11:00 am-11:50 am -

  Examples of random variables: Bernouli, Binomial, Poisson. Linearity of expectation. Application to Max Cut.

  References	[S].
  Exercises
  Reading

  Examples of random variables: Bernouli, Binomial, Poisson. Linearity of expectation. Application to Max Cut.
  

  References:

  [S].

  • Meeting 53 : Mon, Nov 10, 09:00 am-09:50 am -

  Continuous vs discrete random variables.

  References	[S].
  Exercises
  Reading

  Continuous vs discrete random variables.
  

  References:

  [S].

  • Meeting 54 : Tue, Nov 11, 08:00 am-08:50 am -

  Markov's inequality. Applications. Chebyshev's inequality. Sum of 0/1 random variables. Chernoff's bound.

  References	[S], Class Notes.
  Exercises
  Reading

  Markov's inequality. Applications. Chebyshev's inequality. Sum of 0/1 random variables. Chernoff's bound.
  

  References:

  [S], Class Notes.

  • Meeting 55 : Wed, Nov 12, 06:00 am-06:00 am -

  Chernoff's bound (proof). Notion of martingales and Azuma-Hoeffding ineqaulity (statement only).

  References	Class Notes.
  Exercises
  Reading

  Chernoff's bound (proof). Notion of martingales and Azuma-Hoeffding ineqaulity (statement only).
  

  References:

  Class Notes.

  • Meeting 56 : Fri, Nov 14, 11:00 am-11:50 am -

  Markov Chains: Definitions and first properties (without proof).

  References	[S], Class notes
  Exercises
  Reading

  Markov Chains: Definitions and first properties (without proof).
  

  References:

  [S], Class notes

  • Meeting 57 : Mon, Nov 17, 03:00 pm-04:15 pm -

  <i> Optional</i>, No attendance will be taken. <br> The GOOGLE page rank algorithm (overview and intuition). Review of the course.

  References
  Exercises
  Reading

  Optional, No attendance will be taken.
  The GOOGLE page rank algorithm (overview and intuition). Review of the course.
  

  References:

  None

• Theme 5 : Evaluation Meetings - 7 meetings

  • Meeting 58 : Mon, Aug 25, 09:00 am-09:50 am -

  Short Exam - 1 <br> Syllabus Lectures 1-13.

  References
  Exercises
  Reading

  Short Exam - 1
  Syllabus Lectures 1-13.
  

  References:

  None

  • Meeting 59 : Tue, Sep 02, 08:00 am-08:55 am -

  Quiz-1 <br> Syllabus: Lectures 1-17.

  References
  Exercises
  Reading

  Quiz-1
  Syllabus: Lectures 1-17.
  

  References:

  None

  • Meeting 60 : Mon, Sep 22, 09:00 am-09:50 am -

  Short Exam -2 Syllabus: Lectures 18-29.

  References
  Exercises
  Reading

  Short Exam -2 Syllabus: Lectures 18-29.
  

  References:

  None

  • Meeting 61 : Tue, Oct 14, 08:00 am-08:55 am -

  Quiz-2 <br> SYllabus Lectures 18-39.

  References
  Exercises
  Reading

  Quiz-2
  SYllabus Lectures 18-39.
  

  References:

  None

  • Meeting 62 : Mon, Oct 27, 09:00 am-09:50 am -

  Short Exam-3 <br> Syllabus: Theme 3, Lectures 31-45.

  References
  Exercises
  Reading

  Short Exam-3
  Syllabus: Theme 3, Lectures 31-45.
  

  References:

  None

  • Meeting 63 : Mon, Nov 17, 09:00 am-09:50 am -

  Short Exam-4 <br> Syllabus: Theme 4.

  References
  Exercises
  Reading

  Short Exam-4
  Syllabus: Theme 4.
  

  References:

  None

  • Meeting 64 : Thu, Nov 20, 01:00 pm-04:00 pm -

  End Semester Exam <br> Syllabus: Everything.

  References
  Exercises
  Reading

  End Semester Exam
  Syllabus: Everything.
  

  References:

  None