Discrete Structures

 

The ideas of discrete structures bring about the science and technology of computer age.

This course introduces students to some of the basic ideas in discrete mathematics and their applications in computer science.

 

Course Outline

 

Propositional Logic

Simple and compound statements, conditional and biconditional statements, logical equivalences, valid and invalid arguments, application to digital logic circuits.

 

Methods of Proofs

Direct proof and counter examples, indirect proofs, proof by contradictions, contrapositive proof, proof by cases, principle of mathematical induction.

 

Set Theory

Operations on sets, set identities, partitions of sets, power set.

 

Combinatorics

The addition rule, the inclusion exclusion rule, the multiplication rule, permutations, permutations with repetitions, combinations, combinations with repetitions, the algebra of combinations, the binomial theorem, algebraic and combinatorial proofs.

 

Relations

Relations on sets, inverse of a relation, reflexive, symmetric and transitive relations, equivalence relations, irreflexive and antisymmetric relations, partial order relations.

 

Functions

Functions defined on a general set, one-to-one functions, onto functions, bijective functions, inverse functions, composition of functions, the pigeonhole principle.

 

Recursion

Recurrence relation, recursively defined sequences, the towers of Hanoi, the Fibonacci numbers, solving recurrence relations by iteration, recursive definition of Boolean expressions.

 

Graph Theory

Introduction to Graphs, subgraphs, complete graphs, bipartite graphs, paths and circuits, Eulerian and Hamiltonian graphs, Matrix representation of graphs, isomorphisms of graphs, trees and their characteristics.

 

Reference Books:

1. Susanna S. Epp, Discrete Mathematics with Applications, 2^nd Edition, Brooks/Cole.

2. Kenneth H. Rosen, Discrete Mathematics and it’s Applications, 4^th/5^th Edition, McGraw Hill.

GC University Lahore

 

Computer Science Department