CSL105: Lecture Notes

  • July 23: Introduction, Propositional logic (logical operators).

  • July 25: Propositional logic (logical opreators, tautology, logical equivalence etc.).

  • July 26: Propositional logic (logical equivalences), Predicate logic (predicates, quantifiers).

  • July 30: Predicate logic (quantifiers, equivalence, nested quantifiers).

  • Aug 01: Predicate logic (nested quantifiers, applications, quiz-1).

  • Aug 02: Rules of inference for propositional logic.

  • Aug 06: Resolution principle, Rules of inference for quantified statements.

  • Aug 08: Proofs (direct proof, proof by contraposition, proof by contradiction).

  • Aug 13: Proofs (proof by contradiction, proof by cases, existence proofs etc.).

  • Aug 16: Proofs (existence proofs, proof strategies).

  • Aug 20: Sets, Set operations.

  • Aug 22: Set operations, Functions, Sequences, Cardinality of sets.

  • Aug 23: Cardinality of sets.

  • Aug 27: Cardinality of sets, uncomputable function, Matrices.
    • Minor-I (31st Aug, 2:30 - 3:30, V LT1)

  • Sep 03: Algorithms (Halting Problem, Recap.)

  • Sep 04: Algorithms (Recap.), Basic number theory, Quiz-4.

  • Sep 05: Basic number theory (Euclid's GCD algorithm)

  • Sep 10: Basic number theory (Euclid's GCD algorithm, Extended GCD algorithm).

  • Sep 12: Basic number theory (Extended GCD algorithm, Chinese Remaindering Theorem).

  • Sep 13: Basic number theory (Basic group theory, Fermat's little theorem, RSA).

  • Sep 17: Basic number theory (Diffie-Hellman key exchange), Mathematical Induction.

  • Sep 19: Mathematical Induction, Strong Induction.

  • Sep 24: Recursive functions, recursively defined sets and structures, structural induction, basic counting principles.

  • Sep 26: Counting (Pigeonhole Principle).

  • Sep 27: Counting (Permutation and Combination).

  • Oct 01: Counting (generating permutations and combinations), Discrete Probability (introduction).

  • Oct 03: Discrete Probability (conditional probability, random variable, birthday problem).
    • Minor-II (4th Oct, 2:30 - 3:30, V LT1)

  • Oct 08: Discrete Probability (Probabilistic Algorithms, Probabilistic method (Ramsey number))

  • Oct 10: Discrete Probability (Probabilistic method (Ramsey number), Baye's Theorem)

  • Oct 11: Discrete Probability (Baye's Theorem, Expectation, Linearity of expectation)

  • Oct 15: Discrete Probability (Average-case complexity, Geometric distribution, Independent random variables, Variance, Markov's inequality)

  • Oct 17: Discrete Probability (Chebychev's inequality, Birthday problem, Chernoff bound)

  • Oct 18: Advanced counting techniques (recurrence relations)

  • Oct 29: Advanced counting techniques (solving recurrence relations)

  • Oct 31: Advanced counting techniques (solving recurrence relations, generating functions)

  • Nov 01: Advanced counting techniques (generating functions, inclusion-exclusion), Modeling computation (introduction)

  • Nov 07: Modeling computation (Finite-state machines)

  • Nov 08: Modeling computation (DFA, NFA)

  • Nov 12: Modeling computation (DFA, NFA, non-regular language)

  • Nov 15: Modeling computation (Pumping lemma, PDA, CFG)

  • Nov 19: Modeling computation (Turing machines)

  • Nov 21: Review class (Dynamic programming, Probabilistic method)
    • Major (28th Nov, 10:30 - 12:30, V LT1)