Home »People Faculty Staff »Students »Alumni Areas of Interest »Publications »Projects Courses Contact Details

## 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.

### 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

### Quiz

Page Designed by E. Boopal. Copyright Reserved @ 2008