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.
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
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.
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.
Iteration Method, Master Method, Guess and Verify Method, Constructive
Induction, Transformations, Generating Function Techniques,
Inhomogeneous Recurrences, Miscellaneous.
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.
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.
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.
Discrete Probability Theory
Recurrence Equations II
Assignment Problems and Solutions