Department of Computing & Information Technology

CREDITS: 3

1. Basics of Counting: Arithmetic and geometric progressions; Fibonacci numbers; The pigeonhole principle; Basic definitions; Pascal’s identity; The binomial theorem; The Master theorem.

2. Asymptotic Analysis: Limits; Orders of Growth (Big- oh O, Omega Ω and Theta Θ).

3. Graph Theory: Trees; Planarity; Eulerian and Hamiltonian Cycles; Matching and Colouring.

4. Elementary Probability Theory: Counting in event space; Probability Tree; Probability distributions; Finite probability space, probability measure, events; Conditional probability, independence, Bayes’ theorem; Integer random variables, expectation; Law of large numbers.

5. Generating Functions: Convergence Properties; Convolution; Applications.

6. Recurrence Relations.

7. Introduction to Automata, Grammars and Languages: Finite-state machines; Context-free grammars; Language type classification and grammar type. 

 

ASSESSMENT

Coursework	40%
Final Examination	60%