MAD101 - DISCRETE MATHEMATICS

Course's description

• General information

  • Class: SE18C02–MAD101–Spring 2024

  • Time: Tuesday (Slot 4) and Friday (Slot 4) from 02/01/2024 – 22/03/2024

  • Location: Room 419, Beta Building, Quy Nhon AI Campus, FPT University, Quy Nhon City, Binh Dinh, Vietnam

  • Instructor: Dr. Trinh Hoang Minh

• References

[1] K. Rosen, Discrete Mathematics and its Applications, 8th Edition, McGraw Hill, 2019.

[2] S. Lipschutz, M. Lipson, Schaum's outlines of Discrete Mathematics, 3rd Edition, McGraw Hill, 2007.

[3] Instructor’s slide

Course's contents

0 Introduction                                                           

1 Logic and Proofs                                                    

1.1 Propositional logic

1.2 Propositional equivalences

1.3 Predicates and quantifiers

1.4 Rules of inference

1.6 Introduction to proofs

2 Sets, Functions and Sequences                          

2.1 Sets

2.2 Set operations

2.3 Functions

2.4 Sequences and summations

2.5 Cardinality of sets

3 Algorithms                                                             

3.1 Algorithms

3.2 The growth of functions

3.3 The complexity of algorithms

4 Number theory and cryptography                    

4.1 Divisibility and modular arithmetic

4.2 Representation of integers

4.3 Hash table, pseudo-random number

4.4 Primes and greatest common divisors

4.5 Solving congruence

4.6 Classical cryptography

5 Induction and Recursion                                    

5.1 Mathematical induction

5.2 Strong induction and well-ordering properties

5.3 Structural induction and recursive definition

5.4 Recursive algorithms

5.5 Program correctness

6 Counting                                                               

6.1 Basics of counting

6.2 The pigeonhole principle

6.3 Permutation and combinations

6.4 Binomial coefficients

7 Recurrence relations                                        

7.1 Recurrence relations

7.2 Solving linear recurrence relations

7.3 Divide-and-conquer algorithms

8 Graphs                                                                 

8.1 Graphs and graph models

8.2 Special graphs

8.3 Representing graphs by matrices and graph isomorphism

8.4 Connectivity

8.5 Eulerian and Hamiltonian paths

8.6 Shortest path and the traveling salesperson problem

9 Trees                                                                

9.1 Trees and its properties

9.2 Applications of tree

• Decision tree and binary search tree

• Prefix code and Huffman tree

9.3 Tree traversal

• Pre-order, in-order, post-order

• Prefix-, infix-, and postfix forms

9.4 Spanning trees

• Enumeration of spanning trees

• Depth-first and breadth-first searches

9.5 Minimum spanning trees

• Prim algorithm

• Kruskal algorithm