DISCRETE STRUCTURES

(SW325) | Introduction

Redesigned Lecture Notes • By: Hira Noman

This deck has been redesigned with fresh, everyday examples, clearer visual organization, and two
practice exercises with full worked solutions — built on top of the original course material.

Fair Use Notice: educational material adapted for classroom teaching purposes.
 Course Learning Outcomes (CLOs)

CLO Description Taxonomy Level PLO

1 Explain basic set theory and proofs, including quantifiers and induction. C3 1

2 Solve combination, permutation and recurrence relation problems. C4 2

Recommended Books

● Discrete Mathematics and its Applications, 8th Edition — Kenneth Rosen.

● Mathematics of Discrete Structures for Computer Science, 2012 — Pace G.J.
● Discrete Mathematics with Applications, 5th Edition — Susanna S. Epp.
 What is Discrete Mathematics?

Discrete mathematics is the branch of mathematics that studies discrete (separate, countable) objects
rather than continuous ones. Calculus, which deals with smoothly varying quantities, is not part of discrete
mathematics.

Classic examples of discrete objects:

● Integers.
● Steps taken by a computer program.
● Distinct paths from point A to point B on a road network.
● Ways to pick a winning set of numbers in a lottery.

Fresh, everyday examples:

New Example 1 — A Cricket/Football Match

The number of runs scored, wickets taken, or goals in a match are all discrete — you can't
score 2.5 goals. But the total distance a player runs during the match is continuous.

New Example 2 — Ordering Food Online

The number of items in your cart is discrete (1, 2, 3 pizzas). The delivery time and the weight
of the food package are continuous — they can take any value on a scale.

New Example 3 — Social Media

Number of likes, comments, or followers on a post are discrete counts. The time you spent
scrolling (in seconds/minutes) is continuous.
 Types of Data

Quantitative (Numerical) Qualitative (Categorical)

Discrete (cannot be split) | Continuous Described using labels/categories, e.g.

(measured on a scale) "Statistics is fun"

Illustration — "This Bookcase..."

Qualitative Quantitative

Is made of wood Is 3 feet tall

Was built in Italy Weighs 100 pounds
Is deep brown Has 15 books on it
Has golden knobs Has 3 shelves
Smells like oak Has 2 cabinets
Has a smooth finish Sells for $1500

Discrete vs. Continuous Data (at a given time)

Discrete Data Continuous Data

Number of boys in a class — 9 Height of a person — 5 ft 3 in

Number of candies in a packet — 10 Time in a race — 2 min 40 sec

Number of bags lost by an airline — 4 Distance travelled by a car — 2.3 km

NEW: Number of likes on a photo — 248 NEW: Battery charge level — 63.5%

NEW: Chapters completed in a book — 6 NEW: Room temperature — 24.7°C

New rows (highlighted in bold-italic idea) show that even modern digital quantities — likes, battery %, temperature readings —
fit the same discrete/continuous split.
 Problems Solved Using Discrete Mathematics

Classic questions:
● How many ways can a password be chosen following specific rules?
● How many valid Internet addresses are there?
● What is the probability of winning a particular lottery?
● Is there a link between two computers in a network?
● How can I identify spam email messages?
● How can I encrypt a message so that no unintended recipient can read it?
● How can we build a circuit that adds two integers?

New, everyday questions discrete math also answers:

● How does Google Maps find the shortest route between two cities? (Graph theory)
● How does Netflix recommend the next show based on what you watched? (Relations, sets)
● How many different seating arrangements are possible for 6 friends at a round table? (Permutations)
● How does a Sudoku solver check whether a placement is valid? (Constraint/combinatorics)
● How does WhatsApp guarantee your messages stay private? (Number theory, cryptography)
 Why Study Discrete Mathematics?

Discrete Mathematics is a gateway to many courses:

● Computer Science, Computer Architecture, Data Structures, Algorithms, Programming Languages.
● Compilers, Computer Security, Databases, Artificial Intelligence, Networking, Graphics, Game
Design, Theory of Computation.
● Mathematics: Logic, Set Theory, Probability, Number Theory, Abstract Algebra, Combinatorics,
Graph Theory, Game Theory, Network Optimization.

Discrete Structures
● Propositions. ● Integers.
● Predicates. ● Proofs.
● Sets. ● Finite State Machines.
● (Discrete) Functions. ● Permutations.
● Orders of Growth. ● Combinations.
● Algorithms. ● Relations, Graphs, Trees.

Discrete Objects
Discrete objects are separate/unconnected from each other, e.g. integers, automobiles, houses, people.
Computers represent and manipulate all data in a discrete fashion — as binary digits (0s and 1s).
Mapping of Discrete Structures to Applications

Discrete Structure Application Area

Set theory Software Testing, Databases

Relations Databases

Proof techniques Analysis of Algorithms (Efficiency, Optimality)

Graphs Social Networks, Software Design, Transportation Networks

Trees Data Structures

Permutations, Recurrence Relations, Number Theory Cryptography

NEW: Combinatorics NEW: Machine Learning feature selection, A/B test design

NEW: Graph Coloring NEW: Exam timetabling, mobile network channel allocation
 The Caesar Cipher

Encryption: E(x) = (x + n) mod 26 | Decryption: D(x) = (x - n) mod 26

Original Example (shift n = 3)

Plaintext: THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG

Ciphertext: WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ

NEW Example (shift n = 5)

Plaintext: HELLO FRIEND

H(7)+5=12=M, E(4)+5=9=J, L(11)+5=16=Q, L(11)+5=16=Q, O(14)+5=19=T → MJQQT

F(5)+5=10=K, R(17)+5=22=W, I(8)+5=13=N, E(4)+5=9=J, N(13)+5=18=S, D(3)+5=8=I →

KWNJSI

Ciphertext: MJQQT KWNJSI

 Practice Exercises

Exercise 1 — Classify the Data

For each item below, state whether it represents discrete or continuous data. Briefly justify your answer.
● a) Number of cars sold by a dealership in a day.
● b) Height of students in a classroom.
● c) Number of moves made in a chess game.
● d) Amount of fuel remaining in a car's tank.
● e) Number of text messages sent in an hour.

Solution

a) Discrete — cars sold are counted in whole numbers (0, 1, 2, ...); you cannot sell half a car.

b) Continuous — height can take any value within a range (e.g. 162.4 cm) and is measured,
not counted.

c) Discrete — moves are counted individually; a game has a whole number of moves.

d) Continuous — fuel level is measured on a scale (e.g. 32.7 litres) and can take any value
in a range.

e) Discrete — the number of messages is a countable whole number.

Exercise 2 — Caesar Cipher

Using the Caesar cipher formulas E(x) = (x + n) mod 26 and D(x) = (x - n) mod 26 (A = 0, B = 1, ..., Z = 25):
● a) Encrypt the plaintext MATH IS FUN using a shift of n = 5.
● b) Decrypt the ciphertext YMJ VZNHP KTC, which was encrypted using a shift of n = 5.

Solution

a) Encryption (n = 5): Shift each letter forward by 5 positions in the alphabet.

M(12)+5=17=R, A(0)+5=5=F, T(19)+5=24=Y, H(7)+5=12=M → MATH becomes RFYM

I(8)+5=13=N, S(18)+5=23=X → IS becomes NX

F(5)+5=10=K, U(20)+5=25=Z, N(13)+5=18=S → FUN becomes KZS

Ciphertext: RFYM NX KZS

b) Decryption (n = 5): Shift each letter back by 5 positions.

Y(24)-5=19=T, M(12)-5=7=H, J(9)-5=4=E → YMJ becomes THE

V(21)-5=16=Q, Z(25)-5=20=U, N(13)-5=8=I, H(7)-5=2=C, P(15)-5=10=K → VZNHP becomes

QUICK

K(10)-5=5=F, T(19)-5=14=O, C(2)-5=-3 mod 26=23=X → KTC becomes FOX

Plaintext: THE QUICK FOX