2/24/2022
1
CS-0901200
Discrete Mathematics
Course Overview and Introduction
Instructor:
Prof. Omar Shatnawi
Prince Hussein bin Abdullah College for Information Technology
2
What is Mathematics?
Mathematics is 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, the concepts can to numbers, symbols, visual
pattern, or anything!
1
2/24/2022
3
What is Discrete Mathematics?
The study of discrete, mathematical objects and structures.
“Discrete” – composed of distinct, separable parts.
“Structures” – objects built up from simpler objects according to
a definite pattern.
Discrete mathematics forms the mathematical foundation of
computer and information science.
A course in discrete mathematics provides the mathematical
background needed for all subsequent courses.
4
Why Study Discrete Mathematics?
The basis of all of digital information processing: Discrete
manipulations of discrete structures represented inmemory.
It’s the basic language and conceptual foundation of all
of computer science.
Discrete concepts are also widely used throughout math,
science, engineering, economics, biology, etc., …
A generally useful tool for rational thought!
2
2/24/2022
5
Course Description
This course is an introduction to the formal mathematical
concepts of computer science for the beginning student and
covers a wide variety of diverse topics that serve as the
mathematicalframework for thedesignandanalysisof algorithms.
Topics include elementary logic, set theory and sequences,
induction and recursion, permutations and combinations,
pigeonhole principles, discrete probability, relations and
functions, tree structures, and an introduction to graph theory
and finite-state machines.
6
Course Objectives
The purpose of this course is to understand and use
discrete structures that are backbones of computer
science.
In particular, this course is meant to introduce sets,
elementary number theory, matrices, logic, proofs,
counting, probability, relations, functions, trees, graph
theory, and finite-state machine, with an emphasis on
applications in computer science.
3
2/24/2022
Table of Contents 7
Chapter 1 Fundamentals
Chapter 2 logic
Chapter 3 Counting
Chapter 4 Relations and Digraphs
Chapter 5 Functions
Chapter 6 Order Relations and Structures
Chapter 7 Trees
Chapter 8 Topics in Graph Theory
Chapter 9 Semigroups and Groups
Chapter 10 Finite-State Machines
Chapter 11 Groups and Coding
Chapter Required
Textbook
@ Discrete Mathematical Structures,,Kolman, Bubsy and Ross,
Chapter 1 6th edition, Pearson Prentice Hall, 2009 8
Fundamentals
This chapter introduces some of the basic tools of discrete mathematics and gives the
background needed to begin our explorations of mathematical structures.
In this chapter, you will study
Sets, subsets, and their operations
Sequence, using both explicit and recursively pattern
Some basic properties of the integers
Matrices and matrix multiplication
4
2/24/2022
@ Discrete Mathematical Structures,,Kolman, Bubsy and Ross,
Chapter 2 6th edition, Pearson Prentice Hall, 2009 9
Logic
Logic is the discipline that deals with the methods of reasoning. This chapter provides
rules and techniques for determining whether a given argument is valid.
In this chapter, you will study
Propositions and logical operations
Conditional statements
Methods of proof
Mathematical Inductions
@ Discrete Mathematical Structures,,Kolman, Bubsy and Ross,
Chapter 3 6th edition, Pearson Prentice Hall, 2009 10
Counting
Techniques for counting are important in mathematics and in computer science,
especially the analysis of algorithms. This chapter presents some counting
techniques, in particular those for permutations and combinations, and looks at two
applications of counting, the pigeonhole principle and probability.
In this chapter, you will study
Permutations
Combinations
Pigeonhole principles
Elements of probability
5
2/24/2022
@ Discrete Mathematical Structures,,Kolman, Bubsy and Ross,
Chapter 4 6th edition, Pearson Prentice Hall, 2009 11
Relations and Digraphs
Relationships between people, numbers, sets, and many other entities can be
formalized in the idea of a binary relation. This chapter develops the concept of
binary relation, discusses a variety of different properties, introduces several useful
operations that may be performed on binary relations.
In this chapter, you will study
Product sets and partitions
Relations and diagraphs
Paths in relations and diagraphs
Properties of relations
Operations on relations
@ Discrete Mathematical Structures,,Kolman, Bubsy and Ross,
Chapter 5 6th edition, Pearson Prentice Hall, 2009 12
Functions
This chapter focuses on a special type of relation, a function, that plays an important
role in mathematics, computer science, and many applications.
In this chapter, you will study
Functions
Growth of functions
Permutation functions
6
2/24/2022
@ Discrete Mathematical Structures,,Kolman, Bubsy and Ross,
Chapter 7 6th edition, Pearson Prentice Hall, 2009 13
Trees
This chapter studies a special type of relation, that is, exceptionally useful in a variety
of biology and computer science applications and is usually represented by its
digraphs. They are called trees or rooted trees, because of the appearance of their
digraphs.
In this chapter, you will study
Trees
Labeled trees
Tree searching
Minimal spanning trees
@ Discrete Mathematical Structures,,Kolman, Bubsy and Ross,
Chapter 8 6th edition, Pearson Prentice Hall, 2009 14
Topics in Graph Theory
Graph theory begins with very simple geometric ideas and has many powerful
applications. Some uses of graphs are discussed in Chapter 4, 6 and 7. in those
chapters a graph is associated with the digraph. This chapter gives an alternate
definition of graph that includes the more general multigraphs.
In this chapter, you will study
Graphs
Euler paths and circuits
Hamiltonian paths and circuits
Transport networks
7
2/24/2022
@ Discrete Mathematical Structures,,Kolman, Bubsy and Ross,
Chapter 10 6th edition, Pearson Prentice Hall, 2009 15
Language & Finite-State Machines
Whenever we tell a modern-day digital computer to perform a task, we must
transmit a set of precise step-by-step instructions to the computers that will instruct
it how to carry out this task. This chapter provides an introduction to the notion of a
finite-state machine, an abstract mathematical model of a computer that is able to
recognize elements of a formal language.
In this chapter, you will study
Finite-state machines
Monoids, machines, and language
16
Assessment Plan
Assessment Methods Weight
Quizzes, Assignments & Participation 20 %
Mid-Term Exam 30 %
Final Exam 50 %
Total 100 %
Blended Learning – Teaching with Technology
(via Moodle)
