SECI1037 - 07 DISCRETE STRUCTURE

by FIKRI AKMAL AIZUDDIN BIN BAHRIM

LECTURER : DR. MUHAMMAD ALIFF BIN AHMAD

COURSE SYNOPSIS

This course introduces students to the principles and applications of discrete structure in the field of computer science. The topics that are covered in this course are set theory, proof techniques, relations, functions, recurrence relations, counting methods, graph theory, trees, and finite automata. At the end of the course, the students should be able to use set theory, relations, and functions to solve computer science problems, analyze and solve problems using recurrence relations and counting methods, apply graph theory and trees in real-world problems and use deterministic finite automata finite state machines to model electronic devices and problems.

OVERVIEW OF COURSE

CHAPTER 1: Set Theory & Logic

  • 1.1 Set Theory
    • Set and Subset
    • Operations on Sets
  • 1.2 Propositions, Conditional Propositions, and Logical Equivalences
  • 1.3 Quantifiers
    • Basic Quantifiers
    • Nested Quantifiers
  • 1.4 Proof Techniques
    • Direct Proof
    • Indirect Proof

CHAPTER 2: Relations & Function

  • 2.1 Relations
    • Digraph
    • Matrices of Relations
    • Characteristics of Relations
    • Equivalence Relations
    • Partial Orders
  • 2.2 Function
    • One-to-one, Onto, Bijection, Inverse functions
    • Composition
    • Recursive Algorithm
  • 2.3 Recurrence Relation
    • Sequences
    • Solving Recurrence Relation

CHAPTER 3: Counting Method & Probability

  • 3.1 Basic Principle
  • 3.2 Permutations
  • 3.3 Combinations
  • 3.4 Pigeonhole Principle (First, Second, Third Form)
  • 3.5 Discrete Probability Theory
    • Discrete Probability Theory
    • Bayes’ Theorem

CHAPTER 4: Graph Theory

  • 4.1 Graph Definition and Notations
  • 4.2 Representation of Graphs
  • 4.3 Isomorphism of Graphs
  • 4.4 Path and Cycles
  • 4.5 Euler Cycles
  • 4.6 Hamiltonian Cycles
  • 4.7 Dijkstra’s Shortest Path Algorithm
  • 4.8 Trees
    • Terminology and Characterizations of Trees
    • Rooted Trees
    • Binary Trees
    • Tree Traversals
    • Spanning Tree – Kruskal’s Algorithm

CHAPTER 5: Finite Automata

  • 5.1 Deterministic finite automata
  • 5.2 Finite state machines
Updated on 27 January 2022, 7:09 PM; 249 page visits from 13 January 2022 to 31 October 2025