Mathematical Foundations of Computer Science

Note : Lecture Notes, Problems and Solutions are done with tex to html (tth).
Linux users please append the following line in their .Xdefaults file.
Netscape*documentFonts.charset*adobe-fontspecific: iso-8859-1

Lecture Notes

  1. Introduction to Combinatorics
    Introduction, Basic Counting Principles, Sum Rule, Product Rule, Permutation of Sets, Theorems on Permutation of Sets, Combination of Sets, Counting Paradigms, Partition of a Set, Sampling Paradigm, Sampling without Replacement, Sampling with Replacement, Selection, Worked out examples, Reference.

  2. Counting Principles
    Identities Through Counting, Vandermonde's Identities, Stirling number of second kind, Fat Sets, Pigeon-hole Principle, Binomial Theorem and their Extended Forms, Principle of Inclusion and Exclusion, Examples, Further Examples, Counting through Recurrence Equations, Derangements.

  3. Recurrence Equations, Generating Functions
    Recurrence Relations, Solving Recurrence Relations, Linear Homogeneous Recurrence Relations with Constant Coefficients and Distinct Roots, Case of Repeated Roots, Non Homogeneous Recurrence Relation, Generating Functions, Linear Recurrence Relations, Exponential Generating Function, Catalan Numbers, Derangements.

  4. Recurrence Relations
    Iteration Method, Master Method, Guess and Verify Method, Constructive Induction, Transformations, Generating Function Techniques, Inhomogeneous Recurrences, Miscellaneous.

  5. Sets and Relations I
    Set Theory, Some Definitions, Subset, Power set, Union, & Intersection, Properties of Sets, Ordered Pair, Relation, Inverse Relation, Walk, Trail, Path & Cycle, Some Relations, Equivalence Relation, Closure of Relation, Composition of Relation, Reference.

  6. Problem Solving and Mathematical Modelling
    Introduction, What is a problem?, Abstraction of a Problem, Astavadhani, Step-wise Refinement, Mathematical Models - What and Why?, Components of a Mathematical Model, The Mathematical Modeling Process, Examples - One Way Streets, Examples - Cyclic Quaderilateral Test, Conclusion, Exercises, Reference.

  7. Sets and Relation II
    Introduction, Cantor's Concept of a set, The Basis of a Intuititive Set Theory, Principle of Extensionality, Principle of Abstraction, Principle of Comprehension, Inclusion, Operation on Sets, The Algebra of Sets, Exercise on Sets, Relations, Some Theorems on Relations, Function, Images of Sets under Relations, Relations and Graphs, Special Classes of Relations, Equivalence and Partitions, Exercises on Relations and Functions.

  8. Discrete Probability Theory

  9. Recurrence Equations II

  10. Mathematical Logic

Assignment Problems and Solutions

Assignment Series 1
Introduction to Combinatorics
Assignment Series 2
Combinatorics & Counting Principles
Assignment Series 3
Catalan Numbers, Sets and Relations

Assignment Series 4
Graph Theory

Assignment Series 5
Automata Theory I

Assignment Series 6
Automata Theory II



Page Designed by E. Boopal. Copyright Reserved @ 2008