Discrete Structures

Logic, relations, functions, basic set theory, counting, proof techniques, mathematical induction, graph theory, recursion, recurrence relations, number theory and sequence & series. All the topics will be taught in perspective of their applications in computing.

Instructor: Mr. Musawar Ali

Term: Fall

Location: CS Department, National University of Computer & Emerging Sciences, Karachi

Course Overview

A discrete mathematics course has more than one purpose. Students should learn a particular set of mathematical facts and how to apply them; more importantly, such a course should teach students how to think logically and mathematically. To achieve these goals, the focus of this course is on basic mathematical concepts in discrete mathematics and on applications of discrete mathematics in algorithms and data structures.

Students will:

  • Master problem-solving strategies, techniques, and tools used in modern computer science.
  • Understand core concepts of logic, proofs, sets, relations, functions, counting, and probability.
  • Develop an understanding and appreciation of the finite nature inherent in most Computer Science problems.
  • Analyze structures through combinatorial reasoning, abstract algebra, iterative procedures, predicate calculus, tree, and graph structures.

Prerequisites

  • None

Textbooks

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, McGraw Hill, 8th Edition, 2019.
  • Sussana S. Epp, Discrete Mathematics with Applications, Brooks Cole, Cengage Learning, 5th Edition, 2020 (Reference Material).

Grading

  • Assignments/Quizzes: 20%
  • Midterm examination 1: 15%
  • Midterm examination 2: 15%
  • End-term examination: 50%

Schedule

Week Date Topic Materials
1-5 Foundations of Logic, Sets, and Relations

Introduction to Propositional Logic, Applications of Propositional Logic, Propositional Equivalences, Predicates and Quantifiers, Nested Quantifiers, Rules of Inference. Sets, Set Operations, Functions, Sequences and Series. Relations and their Properties, Applications of Relations, Representing Relations, Equivalence Relations, and Partial Orderings.
6-10 Number Theory, Induction, and Counting

Divisibility and Modular Arithmetic, Integer Representation and Algorithms, Primes and Greatest Common Divisors, Congruences and Applications and Cryptography. Mathematical Induction and Recursive Algorithms. Basics of Counting, Pigeonhole Principle, Permutations and Combinations, Binomial Coefficients and Recurrence Relations.
11-15 Graphs, Trees, and Proof Methods

Graphs and Graph Models, Terminologies, Types of Graphs, Representing Graphs and Isomorphism, Connectivity, Euler and Hamiltonian Paths, Planar Graphs, and Graph Coloring. Introduction to Trees, Applications, Tree Traversal, Spanning Trees and Minimum Spanning Trees. Introduction to Proofs and Proof Methods.