Skip to content

Discrete Structure syllabus

ITM 15310 units · 81 topicsAcademic year 2083/84
Browse the units

Discrete Structure

10 units

1. Logic and Proofs (10 LHs)

  1. Propositional logic
    1. Propositional logic
  2. Logical Operators (AND, OR, NOT, IMPLICATION with its variants, BICONDITIONAL)
    1. Logical Operators (AND, OR, NOT, IMPLICATION with its variants, BICONDITIONAL)
  3. Laws of logical equivalences
    1. Laws of logical equivalences
  4. Translating English sentences
    1. Translating English sentences
  5. Predicate and Quantifiers
    1. Predicate and Quantifiers
  6. Nested and Order in quantifiers
    1. Nested and Order in quantifiers
  7. Translating English sentences using quantifiers
    1. Translating English sentences using quantifiers
  8. Rules of inferences for propositional logic
    1. Rules of inferences for propositional logic
  9. Valid arguments in propositional logic
    1. Valid arguments in propositional logic
    2. Fallacies
  10. Rules of inferences for quantified statements
    1. Rules of inferences for quantified statements
  11. Valid arguments in quantified statements
    1. Valid arguments in quantified statements
  12. Methods of Proving Theorems
    1. Methods of Proving Theorems (Direct Proof, Indirect Proof, Proof by Contradiction, Vacuous and Trivial Proof, Proof of Equivalence, Exhaustive Proof, Proof by Cases, Existence Proof, Uniqueness Proof, Counter Example)
  13. Mistakes in Proof. Learning Outcome
    1. Mistakes in Proof. Learning Outcome: Use connectives like AND ()
    2. OR ()
    3. NOT ()
  14. And implication
    1. and implication () to evaluate the truth value of complex statements (Apply). Describe the different rules of inferences for propositional logic and quantified statements (Understand). Identify the techniques of proof (Remember).

2. Set Theory and Functions (2 LHs)

  1. Sets
    1. Sets
  2. Ways to describe the sets
    1. Ways to describe the sets
    2. Venn diagram
    3. Subset
    4. Size of a set
    5. Power set
    6. Cartesian product
    7. Set operations
    8. Set identities
  3. Computer representations of set
    1. Computer representations of set
    2. Functions
    3. One to one function
    4. Onto function
    5. Bijection
    6. Inverse functions
  4. Composition of functions
    1. Composition of functions
    2. Graph of functions
    3. Floor functions
    4. Ceiling functions
  5. Sequence and Summations
    1. Sequence and Summations
    2. Boolean matrices
  6. Meet and Join operation on Boolean matrices. Learning Outcome
    1. Meet and Join operation on Boolean matrices. Learning Outcome: Describe the sets and Venn diagram (Understand). Use the different representation techniques of set (Apply). Identify the types of functions (Remember).

3. Number Theory (5 LHs)

  1. The division algorithm
    1. The division algorithm
    2. Modular Arithmetic
  2. Representation of Integers
    1. Representation of Integers
  3. Algorithms for Integer Operations
    1. Algorithms for Integer Operations
    2. Primes
  4. Greatest Common Divisors
    1. Greatest Common Divisors
    2. Linear Congruences
  5. The Chinese Remainder Theorem
    1. The Chinese Remainder Theorem
  6. Computer Arithmetic with Large Integers. Learning Outcome
    1. Computer Arithmetic with Large Integers. Learning Outcome: Explain the Chinese Remainder Theorem (Understand). Perform the modular arithmetic operations (Apply). Identify the prime (Remember).

4. Mathematical Induction and Recursion (4 LHs)

  1. Introduction to Mathematical Induction
    1. Introduction to Mathematical Induction
  2. Proof by Mathematical Induction
    1. Proof by Mathematical Induction
    2. Strong Induction
  3. Well Ordering Property
    1. Well Ordering Property
  4. Recursively Defined Functions and Sets
    1. Recursively Defined Functions and Sets
  5. Structural Induction
    1. Structural Induction
  6. Generalized Induction
    1. Generalized Induction
  7. Recursive Algorithms
    1. Recursive Algorithms
  8. Proving the Correctness of Recursive Algorithms. Learning Outcome
    1. Proving the Correctness of Recursive Algorithms. Learning Outcome: Describe the steps of mathematical induction (Understand). Use it to proof the inequalities (Apply). Writing of the recursive algorithms (Remember).

5. Basics of Counting (4 LHs)

  1. Sum Rule
    1. Sum Rule
    2. Product Rule
  2. Principle of Inclusion – Exclusion
    1. Principle of Inclusion – Exclusion
  3. The Pigeonhole Principle (Generalized as well)
    1. The Pigeonhole Principle (Generalized as well)
  4. Permutations and Combinations
    1. Permutations and Combinations
    2. Binomial Theorem
  5. Pascal’s Identity and Triangle
    1. Pascal’s Identity and Triangle
  6. Generalized Permutations and Combinations
    1. Generalized Permutations and Combinations
  7. Permutations with Repetitions
    1. Permutations with Repetitions
  8. Combinations with Repetitions
    1. Combinations with Repetitions
  9. Permutations with Indistinguishable Objects Learning Outcome
    1. Permutations with Indistinguishable Objects Learning Outcome: Explain the generalized Pigeonhole principle (Understand). Generates permutations and combinations (Apply). What is Pascal’s triangle? (Remember).

6. Discrete Probability (4 LHs)

  1. Introduction
    1. Introduction
    2. Finite Probability
  2. Probabilities of Complements and Unions of Events
    1. Probabilities of Complements and Unions of Events
  3. Assigning Probabilities
    1. Assigning Probabilities
  4. Conditional Probability
    1. Conditional Probability
    2. Independence
    3. Random Variable
  5. The Birthday Problem
    1. The Birthday Problem
  6. Expected Value. Learning Outcome
    1. Expected Value. Learning Outcome: What is probability (Understand)? What are the uses of Conditional Probability (Apply)? What is random variable (Remember)?

7. Advanced Counting Techniques (5 LHs)

  1. Recurrence Relations
    1. Recurrence Relations
  2. Modeling with Recurrence Relations
    1. Modeling with Recurrence Relations
  3. Solving Linear Homogeneous Recurrence Relations with Constant Coefficients
    1. Solving Linear Homogeneous Recurrence Relations with Constant Coefficients (Without Proving the Theorem)
  4. The Degree of Two Case (Two Distinct or Equal Characteristic Roots)
    1. the Degree of Two Case (Two Distinct or Equal Characteristic Roots)
  5. The General Case
    1. the General Case (the Degree may be Greater than Two, where the Characteristic Equation has Distinct Roots or Repeated Roots). Learning Outcome: Describe the recurrence solution (Understand). Solve the recurrence relations (Apply). Why do we need to solve it (Remember)?

8. Relations (3 LHs)

  1. Relation and its Properties
    1. Relation and its Properties
    2. n – ary Relations
  2. Representing Relations (using Matrix and Digraphs)
    1. Representing Relations (using Matrix and Digraphs)
  3. Closure of Relations (Reflexive, Symmetric, Transitive)
    1. Closure of Relations (Reflexive, Symmetric, Transitive)
  4. Warshall’s Algorithm to Compute the Transitive Closure of a Relation
    1. Warshall’s Algorithm to Compute the Transitive Closure of a Relation
  5. Equivalence Relations
    1. Equivalence Relations
    2. Equivalence Classes
  6. Partial Ordering. Learning Outcome
    1. Partial Ordering. Learning Outcome: Describe the properties of relation (Understand). Represent the relations using matrix and directed graph (Apply). What is Partial Ordering (Remember)?

9. Graph Theory (8 LHs)

  1. Graph Models
    1. Graph Models
  2. Types of Graphs
    1. Types of Graphs (Simple Graph, Multigraph, Pseduograph, Directed Graph, Null Graph, Bipartite Graph)
  3. Graph Terminologies (Adjacent Vertices, Degree of a Vertex, Isolated Vertex, Pendant Vertex)
    1. Graph Terminologies (Adjacent Vertices, Degree of a Vertex, Isolated Vertex, Pendant Vertex)
    2. Handshaking Theorem
  4. Representation of Graphs (Adjacency List, Adjacency Matrix, Incidence Matrix)
    1. Representation of Graphs (Adjacency List, Adjacency Matrix, Incidence Matrix)
    2. Graph Isomorphism
    3. Graph Connectivity
  5. Euler and Hamilton Path
    1. Euler and Hamilton Path
  6. Necessary and Sufficient Conditions for Euler and Hamilton Path and Circuits (Without Proof)
    1. Necessary and Sufficient Conditions for Euler and Hamilton Path and Circuits (Without Proof)
  7. Shortest Path Algorithm (Dijkstra’s Algorithm)
    1. Shortest Path Algorithm (Dijkstra’s Algorithm)
    2. Planar Graph
  8. Graph Coloring Learning Outcome
    1. Graph Coloring Learning Outcome: Explain the different types of graphs (Understand). Know the theorem related to graph (Apply). What is the use of Dijkstra’s Algorithm (Remember)?

10. Trees (3 LHs)

  1. Introduction to Trees
    1. Introduction to Trees
    2. Rooted Tree
  2. Terminologies of a Tree (Parent, Child, Sibling, Ancestors, Descendants, Leaf, Internal Nodes)
    1. Terminologies of a Tree (Parent, Child, Sibling, Ancestors, Descendants, Leaf, Internal Nodes)
    2. M – ary Tree
    3. Binary Search Tree
    4. Decision Tree
    5. Prefix Codes
    6. Tree Traversal
    7. Spanning Tree
  3. Minimum Spanning Tree
    1. Minimum Spanning Tree
  4. Kruskal’s Algorithm. Learning Outcome
    1. Kruskal’s Algorithm. Learning Outcome: Describe the terminologies of a tree (Understand). Find the MST (Apply). What is M – ary tree (Remember)?
  5. Pedagogical Strategies
    1. Pedagogical Strategies
  6. Lectures with demonstration
    1. Lectures with demonstration
  7. Hands-on lab sessions
    1. Hands-on lab sessions
  8. Problem-based learning
    1. Problem-based learning
  9. Guest lectures from tech industry experts
    1. Guest lectures from tech industry experts
  10. Continuous assessment and feedback
    1. Continuous assessment and feedback
  11. Multimedia presentations to visualize concepts
    1. Multimedia presentations to visualize concepts
    2. Mini project
    3. Mode of Delivery
  12. Lecture sessions (Theory)
    1. Lecture sessions (Theory)
    2. Demonstration
  13. Laboratory work (Practical)
    1. Laboratory work (Practical)
    2. Mini project