CMP200 - Discrete Mathematics (Course Outline)

BS Computer Science (2nd year) Punjab University Course Outline:
to see the course outline of all subjects click here.
 
Course Outline of CMP200 - Discrete Mathematics (Paper VI - 100 Marks)

Objectives

This course introduces the foundations of discrete mathematics as they apply to Computer Science, focusing on providing a solid theoretical foundation for further work. It aims to develop understanding and appreciation of the finite nature inherent in most Computer Science problems and structures through study of combinatorial reasoning, abstract algebra, iterative procedures, predicate calculus, tree and graph structures. The following topics will be covered in the course: Introduction to logic and proofs, Direct proofs, proof by contradiction, Sets, Combinatorics, Sequences, Fomtal logic, Propositional and predicate calculus, Methods of Proof, Mathematical Induction and Recursion, loop invariants, Relations and functions, Pigeon whole principle, Trees and Graphs, Elementary number theory, Optimization and matching, Fundamental structures, Functions (subjections, injections, inverses, composition), relations (reflexivity, symmetry, transitivity, equivalence relations), sets (Venn diagrams, complements, Cartesian products, power sets), pigeonhole principle; cardinality and countability.

Prerequisites
None

Text Book
Rosco, Discrete Mathematics and Its Applications, 5th edition, McGraw-Hill, ISBN:
0072424346

Reference Material

•  Richard Johnsonbaugh, Discrete Mathematics. Prentice Hall, ISBN: 0135 l 82425
•  Kolman, Busby & Ross, Discrete Mathematical Structures, 4th Edition, 2000, Prentice-l lall, ISBN: 0130831433