University of Florida

Dept. of Computer & Information Science & Engineering

COT 3100
Applications of Discrete Structures
Dr. Michael P. Frank

Slides for a Course Based on the Text

Discrete Mathematics & Its Applications
(5th Edition)
by Kenneth H. Rosen
Slides are online at http://www.cise.ufl.edu/~mpf/cot3100lecs

08/28/25 (c)2001-2004, Michael P. Frank 1

 Module #0:
Course Overview
A few general slides about the subject
matter of this course.
14 slides, ½ lecture

08/28/25 (c)2001-2004, Michael P. Frank 2

 What is Mathematics, really?
• It’s not just about numbers!
• Mathematics is much more than that:
Mathematics is, most generally, the study of
any and all absolutely certain truths about
any and all perfectly well-defined concepts.

• But, these concepts can be about numbers,

symbols, objects, images, sounds, anything!

08/28/25 (c)2001-2004, Michael P. Frank 3

 Physics from Mathematics
• Starting from simple structures of logic &
set theory,
– Mathematics builds up structures that include
all the complexity of our physical universe…
• Except for a few “loose ends.”
• One theory of philosophy:
– Perhaps our universe is nothing other than just
a complex mathematical structure!
• It’s just one that happens to include us!

From Max Tegmark, ‘98

08/28/25 (c)2001-2004, Michael P. Frank 4
 So, what’s this class about?
What are “discrete structures” anyway?
• “Discrete” ( “discreet”!) - Composed of distinct,
separable parts. (Opposite of continuous.)
discrete:continuous :: digital:analog
• “Structures” - Objects built up from simpler
objects according to some definite pattern.
• “Discrete Mathematics” - The study of discrete,
mathematical objects and structures.

08/28/25 (c)2001-2004, Michael P. Frank 5

 Discrete Structures We’ll Study
• Propositions • Sequences
• Predicates • Strings
• Proofs • Permutations
• Sets • Combinations
• Functions • Relations
• Orders of Growth • Graphs
• Algorithms • Trees
• Integers • Logic Circuits
• Summations • Automata

08/28/25 (c)2001-2004, Michael P. Frank 6

 Relationships Between Structures

• “→” :≝ “Can be defined in terms of”

Groups Programs Proofs
Operators Trees
Complex
numbers Propositions
Graphs
Real numbers Strings
Functions
Integers
Natural Relations Matrices
numbers Sequences
Infinite Bits n-tuples
ordinals Vectors
Sets Not all possibilities
08/28/25 (c)2001-2004, Michael P. Frank are shown here. 7
 Some Notations We’ll Learn
p p q pq p q p q x P ( x)
x P ( x) {a1 ,  , an } Z, N, R  {x | P ( x)} xS
n
 S T |S| AB A A
i 1
i

n
f :A B f  1 ( x) f g  x 

a
S
a
i 1
i

O, ,  min, max a /| b gcd, lcm mod a b (mod m)

 n
( a k  a0 ) b [aij ] AT B
AΟ A[ n ]  
r
C (n; n1 ,  , nm ) p( E | F ) R  [ a ]R deg  (v)

08/28/25 (c)2001-2004, Michael P. Frank 8

 Why Study Discrete Math?
• The basis of all of digital information
processing is: Discrete manipulations of
discrete structures represented in memory.
• It’s the basic language and conceptual
foundation for all of computer science.
• Discrete math concepts are also widely used
throughout math, science, engineering,
economics, biology, etc., …
• A generally useful tool for rational thought!
08/28/25 (c)2001-2004, Michael P. Frank 9
 Uses for Discrete Math in Computer Science

• Advanced algorithms • Database management

& data structures systems
• Programming • Cryptography
language compilers & • Error correction codes
interpreters. • Graphics & animation
• Computer networks algorithms, game
• Operating systems engines, etc.…
• Computer architecture • I.e., the whole field!

08/28/25 (c)2001-2004, Michael P. Frank 10

 Instructors: customize topic content & order for your own course

Course Outline (as per Rosen)

1. Logic (§1.1-4) 13. Summations (§3.2)
2. Proof methods (§1.5) 14. Countability (§3.2)
3. Set theory (§1.6-7) 15. Inductive Proofs (§3.3)
4. Functions (§1.8) 16. Recursion (§3.4-5)
5. Algorithms (§2.1) 17. Program verification (§3.6)
6. Orders of Growth (§2.2) 18. Combinatorics (ch. 4)
7. Complexity (§2.3) 19. Probability (ch. 5)
8. Number theory (§2.4-5) 20. Recurrences (§6.1-3)
9. Number theory apps. (§2.6) 21. Relations (ch. 7)
10. Matrices (§2.7) 22. Graph Theory (chs. 8+9)
11. Proof strategy (§3.1) 23. Boolean Algebra (ch. 10)
12. Sequences (§3.2) 24. Computing Theory (ch.11)

08/28/25 (c)2001-2004, Michael P. Frank 11

 Topics Not Covered
Other topics we might not get to this term:
21. Boolean circuits (ch. 10)
- You could learn this in more depth in a digital logic course.
22. Models of computing (ch. 11)
- Many of these are obsolete for engineering purposes now anyway
23. Linear algebra (not in Rosen, see Math dept.)
- Advanced matrix algebra, general linear algebraic systems
24. Abstract algebra (not in Rosen, see Math dept.)
- Groups, rings, fields, vector spaces, algebras, etc.

08/28/25 (c)2001-2004, Michael P. Frank 12

 Course Objectives
• Upon completion of this course, the student
should be able to:
– Check validity of simple logical arguments (proofs).
– Check the correctness of simple algorithms.
– Creatively construct simple instances of valid logical
arguments and correct algorithms.
– Describe the definitions and properties of a variety of
specific types of discrete structures.
– Correctly read, represent and analyze various types of
discrete structures using standard notations.

08/28/25 (c)2001-2004, Michael P. Frank 13

 A Proof Example
• Theorem: (Pythagorean Theorem Pythagoras of Samos
of Euclidean geometry) For any (ca. 569-475 B.C.)

real numbers a, b, and c, if a and b are the

base-length and height of a right triangle,
and c is the length of its hypo-
2 2
tenuse, then a + b = c .
2 2 2
b
c  a  b

• Proof: See next slide.

a

08/28/25 (c)2001-2004, Michael P. Frank 14

 Proof of Pythagorean Theorem
• Proof. Consider the below diagram:
– Exterior square area = c2, the sum of the following regions:
• The area of the 4 triangles = 4(½ab) = 2ab
• The area of the small interior square = (b−a)2 = b2−2ab+a2.
– Thus, c2 = 2ab + (b2−2ab+a2) = a2 + b2. ■
c Note: It is easy to show that the exterior and
½ab a interior quadrilaterals in this construction are
c
b b indeed squares, and that the side length of
a the internal square is indeed b−a (where b is
(b−a)2 ½ab
½ab defined as the length of the longer of the two
b a
c b perpendicular sides of the triangle). These
steps would also need to be included in a
a ½ab c
more complete proof.
Areas in this diagram are in
boldface; lengths are in a
normal font weight.
08/28/25 (c)2001-2004, Michael P. Frank 15
 Finally: Have Fun!

08/28/25 (c)2001-2004, Michael P. Frank 16