Transcript What is Discrete Math?

WHAT IS DISCRETE MATH?
Fall 2014
Day 1
Sarah Spence Adams
Professor of Mathematics and Electrical and Computer Engineering
Some slides and graphics adapted from Denise Troxell
DISCRETE MEANS…

Discrete:
consisting of distinct or unconnected elements
 taking on or having a finite or countably infinite number
of values


Not Continuous:
Real numbers are no longer the base
 Integers are the primary tool

WHY DISCRETE?


DM provides models and tools for real world
phenomena that change abruptly or have distinct
states
DM has become increasingly important in the
digital/computer age
DM INTERSECTS OTHER AREAS
Computer Science
 Electrical Engineering
 Operations Research
 Probability
 Statistics
 Number Theory
 Cryptology
 Group Theory
 Graph Theory
 Coding Theory
 Set Theory
 Logic, and more

APPLICATIONS
algorithms
 network flows
 telephone routing
 delivery routes
 computer networks
 airplane schedules
 personnel assignments
 genetics
 election procedures
 secure and reliable wireless communications
 design of statistical experiments
 bin packing, and more…

MORE ON APPLICATIONS



Software engineering – uses sets, graphs, trees, and
other structures
Analysis of algorithms – requires ability to count
number of operations, proofs of correctness
Recursive algorithms – require solution to recurrence
relations, proofs of correctness through induction

Cryptology – requires number theory

AI – requires logic

Theory of computation and compiler design –
requires proofs including proofs by induction
WHAT’S IN STORE THIS SEMESTER?

Learn how to count!

You may be surprised that counting certain things can be
really, really hard!

But you may also be surprised at how good you’ll get at
counting!
COUNT THINGS LIKE..
 Number
of ways to buy a dozen donuts from a
choice of 32 different varieties
 Number
of ways to triangulate an n-gon
 Number
of ways to configure a network so that
certain connectivity requirements are met
 Number
of ways to assign students to groups,
considering certain constraints on student
preferences
THE PIGEON-HOLE PRINCIPLE

Learn how to use pigeons to “unlock the common sense
in your head”
FIND OUT HOW MANY COLORS IT TAKES TO
COLOR ANY MAP SUCH THAT NO “NEIGHBOR
STATES” HAVE THE SAME COLOR
LEARN ABOUT THE KÖNIGSBERG BRIDGE
PROBLEM
c
Euler - 1736
River Pregel

Is it possible?
 Start at locations a, b, c, or d
 Cross each bridge exactly once
 Return to the starting location
d
a
b
STUDY HOW THE NASA MARINER MISSION
SENT PICTURES BACK TO EARTH
UNLOCK THE SECRETS OF ISBN AND UPC
DISCOVER WHY THIS IS PERHAPS THE COOLEST
FIGURE IN MATHEMATICS
RSA CRYPTOSYSTEM

Learn how the famous RSA algorithm actually
works
LEARN HOW TO PROVE THINGS LIKE:


Every amount of postage of 12 cents or more
can be formed using just 4-cent and 5-cent
stamps.
For all positive integers n, a 2n x 2n
chessboard with one square removed can be
tiled using L-shaped pieces, where these
pieces cover 3 squares at a time, as shown
WHAT ELSE CAN YOU EXPECT?

Work lots of hard but fun problems

Learn to argue clearly, convincingly, and flawlessly

Improve technical writing and presentation skills

Investigate topics in small groups

Participate actively in class

Get help early and often

Work closely with classmates and professor
NUMBER 1 PIECE OF ADVICE
FROM PREVIOUS STUDENTS
Do Practice
Problems