IT221 Discrete Math
Unit 1: Introduction to the course
2025-07-31
Welcome to IT221
- How do you wish to be called?
- Where are you from?
- What is your experience with Math?
- What is your goal?
Your Instructor
- Email: robert_b@payap.ac.th
- Office: PC314
(Office hrs by appointment)
Course details
\[{\large \bf IT221\ Discrete\ Mathematics}\] \[\small\begin{matrix}\\ {\bf Credits:}&\rm 3\ (3-0-6)\\ {\bf Days:} &\rm Mon, Thurs\\ {\bf Time:} & \hbox{13:00-14:30}\\ {\bf Venue:} & \rm PC301\\ \end{matrix}\]
Course Mapping
Why take this course?
Discrete Math is key to effective and efficient programming
Discrete approaches simplify a problem by reducing the possibilities for solutions
Many important shortcuts and algorithm improvements come from applications of this discipline
Many failures of computing and business come from the lack of understanding of Discrete Math.
Course Description:
Propositional logic, quantifiers, sets and set theory, induction and recursion, relations and functions, counting methods and discrete probability, graph structures including trees, Boolean algebra, simple logic circuits, the basic concepts of modeling computation, and the basics of finite state machines.
What is Discrete Math??
- Discrete Math
the study of discrete mathematical structures such as integers, graphs, and statements in logic.
- Continuous Math
The study of relationships between real numbers and the surface topology of solution spaces
Course Website
https://classroom.google.com/c/NzkxNTI5NzE1MTcx?cjc=qr6lpr3p
Course Textbook:
Susanna Epp, 2020.
Discrete Mathematics with applications.
Cengage, 5th ed.
Reference Textbooks:
- Oscar Levin, 2024.
Discrete Mathematics: An Open Introduction,
4th edition.
Kenneth Rosen, 2012.
Discrete Mathematics and Its Applications.
McGraw-Hill, 7th editionRonald Graham, Donald E Knuth, Oren Patashnik, 1994
Concrete Mathematics,
Addison-Wesley, 2nd edition
Lesson Plan
1. Speaking Mathematically: 1
Variables; The Language of Sets; The Set-Roster and Set-Builder Notations; Subsets; Cartesian Products; Strings The Language of Relations and Functions; The Language of Graphs; The Logic of Compound Statements.
2. Logical Form and Logical Equivalence: 53
Conditional Statements; Valid and Invalid Arguments; Application: Digital Logic Circuits; Application: Number Systems and Circuits for Addition
3. The Logic of Quantified Statements: 120
Predicates and Quantified Statements; Statements with Multiple Quantifiers; Arguments with Quantified Statements.
4. Elementary Number Theory and Methods of Proof: 208
Direct Proof and Counterexample; Quotient-Remainder Theorem; Direct Proof and Counterexample VI: Floor and Ceiling; Indirect Argument: Contradiction and Contraposition; Indirect Argument: Two Famous Theorems; Application: The Handshake Theorem; Application: Algorithms.
5. Sequences, Mathematical Induction, and Recursion: 258
Sequences; Mathematical Induction I: Proving Formulas; Mathematical Induction II: Applications; Strong Mathematical Induction and Principle for the Integers; Application: Correctness of Algorithms; Defining Sequences Recursively; Solving Recurrence Relations by Iteration; Second-Order Linear Homogeneous Recurrence Relations with Constant Coefficients; General Recursive Definitions and Structural Induction.
6. Set Theory: 377
Set Theory: Definitions and the Element Method of Proof; Properties of Sets; Disproofs and Algebraic Proofs; Boolean Algebras, Russell’s Paradox, and the Halting Problem.
7. Properties of Functions: 425
Functions Defined on General Sets; One-to-One, Onto, and Inverse Functions; Composition of Functions; Cardinality with Applications to Computability.
8. Properties of Relations: 487
Relations on Sets; Reflexivity, Symmetry, and Transitivity; Equivalence Relations; Modular Arithmetic with Applications to Cryptography; Partial Order Relations.
9. Counting and Probability: 564
Introduction to Probability; Definition of Sample Space and Event; Probability in the Equally Likely Case; Counting the Elements of Lists, Sublists, and One-Dimensional Arrays; Possibility Trees and the Multiplication Rule; Possibility Trees; The Multiplication Rule; When the Multiplication Rule Is Difficult or Impossible to Apply; Permutations; Permutations of Selected Elements Counting Elements of Disjoint Sets: The Addition Rule; The Pigeonhole Principle; Counting Subsets of a Set: Combinations; r-Combinations with Repetition Allowed; Pascal’s Formula and the Binomial Theorem; Probability Axioms and Expected Value; Conditional Probability, Bayes’ Formula, and Independent Events; Conditional Probability; Bayes’ Theorem; Independent Events;
10. Theory of Graphs and Trees 677
Trails, Paths, and Circuits; Matrix Representations of Graphs; Isomorphisms of Graphs; Trees: Examples and Basic Properties; Rooted Trees; Spanning Trees and a Shortest Path Algorithm.
11. Analysis of Algorithm Efficiency 769
Big-O, Big-Omega, and Big-Theta Notations; Application: Analysis of Algorithm Efficiency I; Exponential and Logarithmic Functions: Graphs and Orders; Application: Analysis of Algorithm Efficiency II.
12. Regular Expressions and Finite-State Automata 828
Formal Languages and Regular Expressions; Finite-State Automata; Simplifying Finite-State Automata.
Course Assessment
\[\small\begin{matrix}\rm \hline {\bf Type} & {\bf Frequency} & {\bf Time} & {\bf Weight}\\ \hline \rm Class\ participation&\rm Daily & \rm In class& \rm 5\% \\ \rm Assignments & \rm Weekly &\rm Online&\rm 10\% \\ \rm Quizzes & \rm Biweekly &\rm Online &\rm 15\% \\ \rm Midterm & \rm 8\ Oct\ 2025 &\rm 09:00-11:00 & 30\%\\ \rm Finals &\rm 1\ Dec\ 2025 &\rm 13:00-16:00 & 40\%\\ \hline \end{matrix}\]
Course Grading
\[\bf\small\begin{matrix} Score\ Range & Grade\ Letter & Meaning\\ 80 - 100 & A & Excellent \\ 75 - 79 & B+ & Very\ good \\ 70 - 74 & B & Good \\ 65 - 69 & C+ & Above\ adequate\\ 60 - 64 & C & Adequate \\ 55 - 59 & D+ & Poor \\ 50 - 54 & D & Very\ Poor \\ \lt 50 & F & Fail\\ \end{matrix}\]
Example 1:
\[\Large\bf Find\ the\ odd\ one\ within\ 5\ secs\] 
Challenge: Find the odd one
Solution
Interference in the classification
John Ridley Stroop introduce a neurological test back in 1935. He took some color names and just colored them differently. Try it out yourself with the graphics below. Don’t read the words but say aloud the color names of the ink.
If you’re not colorblind, naming a color is an easy thing. But naming a color if it is a colored word of another color name (e.g.
The Stroop Test demonstrates how certain types of information can interfere with others. The test can measure attention, processing speed, and cognitive flexibility: for example, you may be slower or make slightly more errors if you’re distracted, tired, or at a higher-than-normal altitude, and even more so if you’re suffering from dementia or other brain damage.
Adults are also faster at Stroop tasks than children. Those who pass without errors tend to slow their speaking rate down and take a deep breath when they start to feel over whelmed. Conversely, attempting this rapidly in one breath will increase the error rate.
Example 2: Combinorics
The most popular mathematician in the world is throwing a party for all of his friends. To kick things off, they decide that everyone should shake hands. Assuming all 10 people at the party each shake hands with every other person (but not themselves, obviously) exactly once, how many handshakes take place?
Pattern:
\[ a\ b\ \rightarrow {ab} = 1\] \[ a\ b\ c\ \rightarrow {ab,ac,\quad bc}\] \[2 + 1 = 3\] \[ a\ b\ c\ d\ \rightarrow {ab,ac,ad,\quad bc,bd,\quad cd}\] \[3+2+1=6\] \[a\ b\ c\ d\ e\ \rightarrow {ab,ac,ad,ae\quad bc,bd,be\quad cd,ce\quad de}\] \[4+3+2+1=10\]
\[ \therefore {\rm for}\ n\ guests\ \rightarrow \frac{(n-1 +1)(n-1)}{2} =\frac{n(n-1)}{2}\]
Solution:
\[\begin{eqnarray} {\bf Possibilities:}& 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & = 45\\ {\bf Handshakes:}& 1&2&3&4&5&6&7&8&9 &\\ \end{eqnarray}\]
Example 3:
Finding paths
Graph 1:
Graph 2:
Graph 3:
Example 4:
Defining numbers as sequences of integers
\[ 3 \leftarrow 1 + 2\] \[ 6 \leftarrow 1+2+3\]
Defining numbers as the sum of a sequence of integers
\[\large 7+ 8 = 15\] \[\large 6+7+8 = 21\]
Multiple definitions for 15
\[\large\begin{eqnarray} 7+ 8 &=& 15\cr 4+ 5 + 6 &= & 15\cr 1+ 2 + 3 + 4 + 5 &= & 15\cr 0+1+2+3+4+5 &= &15\cr \end{eqnarray}\]
Challenge
Determine all the defining sequences for these numbers:
\[\large 10,\ 16,\ 21, 32,\ 45\]
Answer
\[\small\begin{eqnarray} 10 &:& \{\{1,2,3,4\},\{0,1,2,3,4\}\}\cr 16 &:& \{\}\cr 21 &:& \{\{20,21\},\{6,7,8\},\{1,2,3,4,5,6\},\{0,1,2,3,4,5,6\}\}\cr 32 &:& \{\}\cr 45 &:& \{\{22,23\},\{14,15,16\},\{5,6,7,8,9,10\},\{7,8,9,10,11\},\cr & &\ \ \{1,2,3,4,5,6,7,8,9\},\{0,1,2,3,4,5,6,7,8,9\}\}\cr \end{eqnarray}\]
Sums of Sequences of varying length and startin pts
\[\small\begin{matrix} Start& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10& 11& 12& 13&14 \cr \hline 0 & 1 & 3 & 6 & 10& 15& 21& 28& 36& 45& 55& 66& 78& 91\cr 1 & 3 & 6 & 10& 15& 21& 28& 36& 45& 55& 66& 78& 91& x \cr 2 & 5 & 9 & 14& 20& 27& 35& 44& 54& 65& 77& 90& x & x \cr 3 & 7 & 12& 18& 25& 33& 42& 52& 63& 75& 88& x & x & x \cr 4 & 9 & 15& 22& 30& 39& 49& 60& 72& 85& 99& x & x & x \cr 5 & 11& 18& 26& 35& 45& 56& 68& 81& 95& x & x & x & x \cr 6 & 13& 21& 30& 40& 51& 63& 76& 90& x & x & x & x & x \cr 7 & 15& 24& 34& 45& 57& 70& 84& 99& x & x & x & x & x \cr 8 & 17& 27& 38& 50& 63& 77& 92& x & x & x & x & x & x \cr 9 & 19& 30& 42& 55& 69& 84&100& x & x & x & x & x & x \cr 10 & 21& 33& 46& 60& 75& 91& x & x & x & x & x & x & x \cr 11 & 23& 36& 50& 65& 81& 98& x & x & x & x & x & x & x \cr 12 & 25& 39& 54& 70& 87& x & x & x & x & x & x & x & x \cr 13 & 27& 42& 58& 75& 93& x & x & x & x & x & x & x & x \cr 14 & 29& 45& 62& 80& 99& x & x & x & x & x & x & x & x \cr 15 & 31& 48& 66& 85& x & x & x & x & x & x & x & x & x \cr 16 & 33& 51& 70& 90& x & x & x & x & x & x & x & x & x \cr 17 & 35& 54& 74& 95& x & x & x & x & x & x & x & x & x \cr 18 & 37& 57& 78&100& x & x & x & x & x & x & x & x & x \cr 19 & 39& 60& 82& x & x & x & x & x & x & x & x & x & x \cr 20 & 41& 63& 86& x & x & x & x & x & x & x & x & x & x \cr 21 & 43& 66& 90& x & x & x & x & x & x & x & x & x & x \cr 22 & 45& 69& 94& x & x & x & x & x & x & x & x & x & x \cr 23 & 47& 72& 98& x & x & x & x & x & x & x & x & x & x \cr 26 & 53& 81& x & x & x & x & x & x & x & x & x & x & x \cr 27 & 55& 84& x & x & x & x & x & x & x & x & x & x & x \cr 28 & 57& 87& x & x & x & x & x & x & x & x & x & x & x \cr 29 & 59& 90& x & x & x & x & x & x & x & x & x & x & x \cr 30 & 61& 93& x & x & x & x & x & x & x & x & x & x & x \cr 31 & 63& 96& x & x & x & x & x & x & x & x & x & x & x \cr 32 & 65& 99& x & x & x & x & x & x & x & x & x & x & x \cr 33 & 67& x & x & x & x & x & x & x & x & x & x & x & x \cr 34 & 69& x & x & x & x & x & x & x & x & x & x & x & x \cr 35 & 71& x & x & x & x & x & x & x & x & x & x & x & x \cr 36 & 73& x & x & x & x & x & x & x & x & x & x & x & x \cr 37 & 75& x & x & x & x & x & x & x & x & x & x & x & x \cr 38 & 77& x & x & x & x & x & x & x & x & x & x & x & x \cr 39 & 79& x & x & x & x & x & x & x & x & x & x & x & x \cr 40 & 81& x & x & x & x & x & x & x & x & x & x & x & x \cr 41 & 83& x & x & x & x & x & x & x & x & x & x & x & x \cr 42 & 85& x & x & x & x & x & x & x & x & x & x & x & x \cr 43 & 87& x & x & x & x & x & x & x & x & x & x & x & x \cr 44 & 89& x & x & x & x & x & x & x & x & x & x & x & x \cr 45 & 91& x & x & x & x & x & x & x & x & x & x & x & x \cr 46 & 93& x & x & x & x & x & x & x & x & x & x & x & x \cr 47 & 95& x & x & x & x & x & x & x & x & x & x & x & x \cr 48 & 97& x & x & x & x & x & x & x & x & x & x & x & x \cr 49 & 99& x & x & x & x & x & x & x & x & x & x & x & x \cr \hline \end{matrix}\]
Number of Sequences for each integer 0-200
\[\begin{matrix} & 0 & 1& 2 & 3 & 4& 5 & 6 & 7 & 8 & 9 \cr \hline 000 :& 0& 1& 0& 2& 0& 1& 2& 1& 0& 2\cr 010 :& 2& 1& 1& 1& 1& 4& 0& 1& 2& 1\cr 020 :& 1& 4& 1& 1& 1& 2& 1& 3& 2& 1\cr 030 :& 3& 1& 0& 3& 1& 3& 3& 1& 1& 3\cr 040 :& 1& 1& 3& 1& 1& 6& 1& 1& 1& 2\cr 050 :& 2& 3& 1& 1& 3& 4& 1& 3& 1& 1\cr 060 :& 3& 1& 1& 5& 0& 3& 4& 1& 1& 3\cr 070 :& 3& 1& 2& 1& 1& 5& 1& 3& 4& 1\cr 080 :& 1& 4& 1& 1& 3& 3& 1& 3& 1& 1\cr 090 :& 5& 4& 1& 3& 1& 3& 1& 1& 2& 5\cr 100 :& 2& 1& 3& 1& 1& 8& 1& 1& 3& 1\cr 110 :& 3& 3& 1& 1& 3& 3& 1& 5& 1& 3\cr 120 :& 4& 2& 1& 3& 1& 3& 5& 1& 0& 3\cr 130 :& 3& 1& 3& 3& 1& 7& 2& 1& 3& 1\cr 140 :& 3& 3& 1& 3& 2& 3& 1& 5& 1& 1\cr 150 :& 5& 1& 1& 6& 3& 3& 3& 1& 1& 3\cr 160 :& 1& 3& 4& 1& 1& 7& 1& 1& 3& 2\cr 170 :& 3& 6& 1& 1& 3& 5& 1& 3& 1& 1\cr 180 :& 5& 1& 3& 3& 1& 3& 3& 3& 1& 7\cr 190 :& 4& 1& 1& 1& 1& 7& 2& 1& 5& 1\cr \hline \end{matrix}\]
Another way to look at the problem
\[X_{(x,4)} = x + (x+1)+(x_2)+(x+3)= 4x + 6 = 4(x+1) +2\] \[A_{(4x+6)} =\{6,10,14,18,...,4x+2\}; A_{(4x)} = \{4,8,12,16,...,4x\}\]
\[x=\{0,1,2,3,4,5,6,7,\cdots,\infty\}\]
Yet another way to look at this problem
\[\begin{eqnarray} X_{(2,x)} &=& x + (x+1) &=& 2x + 1\cr X_{(3,x)} &=& x + (x+1) + (x+2) &=& 3x + 3\cr X_{(4,x)} &=& x + (x+1) + (x+2) +(x+3) &=& 4x + 6\cr X_{(5,x)} &=& x + (x+1) + (x+2) +(x+3)+(x+4)&=& 5x + 10\cr X_{(6,x)} &=& x + (x+1)+(x+2)+(x+3)+(x+4)+(x+5)& =& 6x + 15\cr \cr & & x = \{0,1,2,3,4,5,\cdots,\infty\}& &\cr \end{eqnarray}\]
The sum of a sequence
\[\sum_{i=1}^4\ i = \underbrace{1 + \overbrace{2 + 3}+ 4}= 5 + 5 = 10\] \[\eqalign{\sum_{i=n}^{n+3} i &=& n + (n+1)+(n+2)+(n+3) \\ &=&4n +\underbrace{1 + \overbrace{2 + 3}+ 4}\\ &=&4n + 5 + 5 = 4n+ 10\] \[\frac{x(x+1)}{2}=\frac{4(4+1)}{2}=\frac{4\times5}{2}=\frac{20}{2} =10\]
A more generic way to describe this problem
\[ X_{(n,x)} = nx + \frac{\left(n-1\right)\left(\left(n-1\right)+1\right)}{2} = nx + \frac{n(n-1)}{2}\]
Benchmark Comparison
\[\begin{matrix}\hline Algorithm & Time\ required\cr \hline Brute force decomposition& 5.502\ sec\cr Pattern\ trial\ and\ error & 1.431\ sec\cr Summing\ by\ iternation & 0.235\ sec\cr Direct\ calculation & 0.004\ sec\cr \hline \end{matrix}\]
IT221