Syllabus effective from January 2005

2 Credits

Objectives

Since the advent of electronic computers, Discrete Mathematics has become one of the most important theoretical courses for a Master’s level program in Computer Science and Applications. Topics from Discrete Mathematics provide tools for analysis and design of computer hardware and computer software. Also topics like Propositional Calculus provide the foundation for imbedding logical reasoning in computer science.

Syllabus

Propositional Calculus: Propositions, Logical Connectives – Disjunction, Conjunction, Negation, Conditional Connectives, Precedence Rule, Logical Equivalence, Logical Quantifiers.

Methods of Proof: Different methods of proof – Direct Proof, Indirect Proof, Counter examples, Principle of Induction.

Boolean Algebra and Circuits: Boolean Algebras, Boolean Expression, Logic Circuits, Boolean Functions.

Sets, Relations and Functions: Introducing Sets, Operations on sets, Relations, Fuctions.

Combinatorics: Multiplication and Addition Principles, Permutations – Notations, Circular Permutations, Permutations of Objects and Necessarily Distinct, Combinations – Formula for CC(n,r). Combination with Repetition, The Binomial Expansion, Pascal’s Formula for C(n,r), Some Identities Involving Binomial coefficients, The Multinomial Expansion, Applications, to Combinatorial Probability, Elements of Classical Probability Theory, Addition Theorem in Probability.

More About Counting: Pigeon- hole Principle, Inclusion-exclusion Principle, Application to number theory – Euler’s Totient Function, Application to onto maps, Application to Probability, Application to Derangements.

Partitions And Distributions: Integer Partitions, Distributions – Distinguishable Objects into distinguishable, Containers, Generating Function, Approach, Containers with at most one object, distinguishable Objects into Indistinguishable Containers, Indistinguishable Object into Distinguishable Containers, Indistinguishable Object into Indistinguishable Containers.