Discrete Structures Course Outline - University of Sargodha

Course Title: Discrete Structures

Course Code: CMP-2111
Course Structure: Lectures: 3 / Labs: 0
Credit Hours: 3
Prerequisites: None

Course Objectives:

The course provides a solid theoretical foundation of discrete structures as they apply to
Computer Science problems and structures. The students will learn how to use mathematical
notation and solve problems using mathematical tools.

Course Syllabus:

Logic: Propositional Equivalences, Predicates and Quantifiers, Nested Quantifiers, Methods of
Proof. Sets & Functions. Algorithms: the Growth of Functions, Complexity of Algorithms, the
Integers and Division, Matrices. Number Theory and Cryptography. Mathematical Reasoning:
Proof Strategy, Sequences and Summations, Mathematical Induction, Recursive Definitions and
Structural Induction, Recursive Algorithms, Program Correctness. The Basics of Counting: The
Pigeonhole Principle, Permutations and Combinations, Binomial Coefficients, Generalized
Permutations and Combinations, Generating Permutations and Combinations. Advanced
Counting Techniques: Recurrence Relations, Solving Recurrence Relations, Divide-and-Conquer
Algorithms and Recurrence Relations, Generating Functions, Inclusion-Exclusion & its
Application. Relations and Their Properties, n-ary Relations and Their Applications,
Representing Relations, Closures of Relations, Equivalence Relations, Partial Orderings. Graph:
Representing Graphs and Graph Isomorphism, Connectivity, Euler and Hamilton Paths, Shortest-
Path Problems, Planar Graphs, Graph Coloring. Trees: Applications of Trees, Tree Traversal,
Spanning Trees.

Course Outline:

1.     Logic: Propositional Equivalences, Predicates and Quantifiers, Nested Quantifiers,
Methods of Proof. [TB: Ch. 1]

2.       Sets & Functions. [TB: Ch. 2]

3.      Algorithms: the Growth of Functions, Complexity of Algorithms, the Integers and
Division, Matrices. [TB: Ch. 3]

4.     Number Theory and Cryptography. [TB: Ch. 4]

1.      Mathematical Reasoning: Proof Strategy, Sequences and Summations, Mathematical
Induction, Recursive Definitions and Structural Induction, Recursive Algorithms,
Program Correctness. [TB: Ch. 5]

2.      The Basics of Counting: The Pigeonhole Principle, Permutations and Combinations,
Binomial Coefficients, Generalized Permutations and Combinations, Generating
Permutations and Combinations. [TB: Ch. 6]

3.      Advanced Counting Techniques: Recurrence Relations, Solving Recurrence Relations,
Divide-and-Conquer Algorithms and Recurrence Relations, Generating Functions,
Inclusion-Exclusion & its Application. [TB: Ch. 8]

4.      Relations and Their Properties, n-ary Relations and Their Applications, Representing
Relations, Closures of Relations, Equivalence Relations, Partial Orderings. [TB: Ch. 9]

5.      Graph: Representing Graphs and Graph Isomorphism, Connectivity, Euler and Hamilton
Paths, Shortest-Path Problems, Planar Graphs, Graph Coloring. [TB: Ch. 10]

6.      Trees: Applications of Trees, Tree Traversal, Spanning Trees, Minimum Spanning Trees.
[TB: Ch. 11]

Textbook(s):

•         Discrete Mathematics and Its Applications by Kenneth H. Rosen, McGraw-Hill
Science/Engineering/Math; 7^thEdition (2011). ISBN-10: 0073383090

Reference Material:

•         Discrete Mathematics by Richard Johnsonbaugh, Pearson; 7th Edition (January 8, 2008).
ISBN-10: 0131593188

•         Discrete Algorithmic Mathematics by Stephen B. Maurer and Anthony Ralston, A K
Peters/CRC Press; 3rd Edition (August 2004). ISBN-10: 1568811667

•         Discrete Mathematical Structures by Bernard Kolman, Robert Busby and Sharon C. Ross,
Pearson; 6th Edition (2008). ISBN-10: 0132297515

•         Discrete Mathematics with Ducks by sarah-marie Belcastro, A K Peters/CRC Press; 1st
Edition (June 21, 2012). ISBN-10: 1466504994

Note: This content is obtained from official documents of University of Sargodha and applied on BS Computer Science for Main Campus, Sub Campuses, and Affiliated Colleges.