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 and Proofs**- 17 meetings- Meeting 01 : Wed, Jul 30, 12:00 pm-12:55 pm - Raghavendra Rao
- Meeting 02 : Fri, Aug 01, 11:00 am-11:50 am - Raghavendra Rao
- Meeting 03 : Mon, Aug 04, 09:00 am-09:50 am - Jayalal Sarma
- Meeting 04 : Tue, Aug 05, 08:00 am-08:50 am - Jayalal Sarma
- Meeting 05 : Wed, Aug 06, 12:00 pm-12:50 pm - Jayalal Sarma
- Meeting 06 : Fri, Aug 08, 11:00 am-11:50 am - Jayalal Sarma
- Meeting 07 : Mon, Aug 11, 09:00 am-09:50 am - Raghavendra Rao
- Meeting 08 : Tue, Aug 12, 08:00 am-08:50 am -
- Meeting 09 : Wed, Aug 13, 06:00 am-06:00 am -
- Meeting 10 : Mon, Aug 18, 09:00 am-09:50 am -
- Meeting 11 : Mon, Aug 18, 04:45 pm-05:35 pm -
- Meeting 12 : Tue, Aug 19, 08:00 am-08:50 am -
- Meeting 13 : Wed, Aug 20, 12:00 pm-01:00 pm -
- Meeting 14 : Fri, Aug 22, 11:00 am-11:50 am -
- Meeting 15 : Mon, Aug 25, 04:45 pm-05:35 pm -
- Meeting 16 : Tue, Aug 26, 08:00 am-08:50 am -
- Meeting 17 : Wed, Aug 27, 09:00 am-09:50 am -

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 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 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: 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. 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] 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] 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 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. 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. 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.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. 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]. 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. 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] 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. 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]. 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 -
- Meeting 19 : Wed, Sep 03, 12:00 pm-01:00 pm -
- Meeting 20 : Fri, Sep 05, 11:00 am-11:50 am -
- Meeting 21 : Mon, Sep 08, 09:00 am-09:50 am -
- Meeting 22 : Mon, Sep 08, 04:45 pm-05:35 pm -
- Meeting 23 : Tue, Sep 09, 10:00 am-10:50 am -
- Meeting 24 : Wed, Sep 10, 12:00 pm-01:00 pm -
- Meeting 25 : Fri, Sep 12, 11:00 am-11:50 am -
- Meeting 26 : Mon, Sep 15, 09:00 am-09:50 am -
- Meeting 27 : Tue, Sep 16, 08:00 am-08:50 am -
- Meeting 28 : Wed, Sep 17, 12:00 pm-01:00 pm -
- Meeting 29 : Fri, Sep 19, 11:00 am-11:50 am -
- Meeting 30 : Mon, Sep 22, 04:45 pm-05:40 pm -

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. 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. 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" 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 Double Counting: More examples. <i> Compensation for Oct 3</i> References [KR] Exercises Reading Double Counting: More examples.*Compensation for Oct 3*References: [KR] 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 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. 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. Linear non-homogeneous recurrences: without proof. References [KR] Exercises Reading Linear non-homogeneous recurrences: without proof.References: [KR] 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] 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] 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 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 -
- Meeting 32 : Wed, Sep 24, 06:00 am-06:00 am -
- Meeting 33 : Fri, Sep 26, 11:00 am-11:50 am -
- Meeting 34 : Mon, Sep 29, 11:00 am-11:50 am -
- Meeting 35 : Tue, Sep 30, 08:00 am-08:50 am -
- Meeting 36 : Wed, Oct 01, 06:00 am-06:00 am -
- Meeting 37 : Tue, Oct 07, 08:00 am-08:50 am -
- Meeting 38 : Wed, Oct 08, 06:00 am-06:00 am -
- Meeting 39 : Fri, Oct 10, 11:00 am-11:50 am -
- Meeting 40 : Mon, Oct 13, 09:00 am-09:50 am -
- Meeting 41 : Wed, Oct 15, 06:00 am-06:00 am -
- Meeting 42 : Fri, Oct 17, 11:00 am-11:50 am -
- Meeting 43 : Mon, Oct 20, 09:00 am-09:50 am -
- Meeting 44 : Tue, Oct 21, 08:00 am-08:50 am -
- Meeting 45 : Fri, Oct 24, 11:00 am-11:50 am -
- Meeting 46 : Mon, Oct 27, 04:45 pm-05:35 pm -
- Meeting 47 : Tue, Oct 28, 08:00 am-08:50 am -
- Meeting 48 : Wed, Oct 29, 12:00 pm-12:30 pm -
- Meeting 49 : Fri, Oct 31, 11:00 am-11: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. 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. 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. 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] 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. 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]. 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. 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. 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: 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. 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: 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 eliminationReferences: 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. 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] 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. 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. 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. 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. 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. 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 -
- Meeting 51 : Wed, Nov 05, 12:00 pm-01:00 pm -
- Meeting 52 : Fri, Nov 07, 11:00 am-11:50 am -
- Meeting 53 : Mon, Nov 10, 09:00 am-09:50 am -
- Meeting 54 : Tue, Nov 11, 08:00 am-08:50 am -
- Meeting 55 : Wed, Nov 12, 06:00 am-06:00 am -
- Meeting 56 : Fri, Nov 14, 11:00 am-11:50 am -
- Meeting 57 : Mon, Nov 17, 03:00 pm-04:15 pm -

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]. 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]. 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]. Continuous vs discrete random variables. References [S]. Exercises Reading Continuous vs discrete random variables.References: [S]. 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. 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. 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 <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 -
- Meeting 59 : Tue, Sep 02, 08:00 am-08:55 am -
- Meeting 60 : Mon, Sep 22, 09:00 am-09:50 am -
- Meeting 61 : Tue, Oct 14, 08:00 am-08:55 am -
- Meeting 62 : Mon, Oct 27, 09:00 am-09:50 am -
- Meeting 63 : Mon, Nov 17, 09:00 am-09:50 am -
- Meeting 64 : Thu, Nov 20, 01:00 pm-04:00 pm -

Short Exam - 1 <br> Syllabus Lectures 1-13. References Exercises Reading Short Exam - 1

Syllabus Lectures 1-13.References: None Quiz-1 <br> Syllabus: Lectures 1-17. References Exercises Reading Quiz-1

Syllabus: Lectures 1-17.References: None Short Exam -2 Syllabus: Lectures 18-29. References Exercises Reading Short Exam -2 Syllabus: Lectures 18-29.References: None Quiz-2 <br> SYllabus Lectures 18-39. References Exercises Reading Quiz-2

SYllabus Lectures 18-39.References: None Short Exam-3 <br> Syllabus: Theme 3, Lectures 31-45. References Exercises Reading Short Exam-3

Syllabus: Theme 3, Lectures 31-45.References: None Short Exam-4 <br> Syllabus: Theme 4. References Exercises Reading Short Exam-4

Syllabus: Theme 4.References: None End Semester Exam <br> Syllabus: Everything. References Exercises Reading End Semester Exam

Syllabus: Everything.References: None