Discrete Structures syllabus

A Hunt for Reaching Horizon of Science



Fundamentals of Logic: Basic Connectives and Truth Tables, Logical Equivalence, Logical Implication, Use of Quantifiers, Definitions and the Proof of Theorems.


Set Theory: Set and Subsets, Set Operations, and the Laws of Set theory, Counting and Venn Diagrams.
Properties of the Integers: The well – ordering principle, Recursive definitions, the division algorithms, fundamental theorem of arithmetic.



Relations and Functions: Cartesian Product, Functions onto Functions, Special Functions, Pigeonhole Principle, Composition and Inverse Functions, Computational Complexity.
Relations: Partial Orders, Equivalence Relations and Partitions.
Principle of Inclusion and Exclusion: Principles of Inclusion and Exclusion, Generalization of Principle, Derangements, Rock Polynomials, Arrangements with Forbidden Positions.



Generating Functions: Introductory examples, definition and example Partitions of Integers, exponential generating function, summation operator. Recurrence Relations: First – order linear recurrence relation, second – order linear homogenous recurrence relation with constant coefficients, Non homogenous recurrence relation, divide and conquer algorithms.



Algebraic Structures: Algebraic System – General Properties, semi groups, Monoids, homomorphism, Groups, Residue arithmetic, group codes and their applications.


Graph Theory: Definitions and examples, subgraphs, complements and graph Isomorpshim, Vertex degree, Planar graphs, Hamiltonian paths and Cycles, Graph Coloring.
Trees: Definitions, properties and Examples, Rooted Trees, Spanning Trees and Minimum Spanning Trees.


Suggested Reading:

1.Ralph P.Grimaldi, Discrete and Combinatorial Mathematics, 4th edition, 2003, Pearson
2.J.P.Tremblay, R.Manohar, Discrete Mathematical Structure with Applications to Computer
   Science, McGraw Hill, 1987.
3.Joe L.Mott, A.Kandel, T.P.Baker, Discrete Mathematics for Computer Scientists &
   Mathematicians, Prentice Hall N.J., 1986.
4.Thomas Koshy, Discrete Mathematics with Applications, Elsevier Inc.2004.