ESTR2004 Discrete Mathematics for Engineers
Does any resource help with this course?
Textbook: Mathematics for Computer Science
What is this course about?
This course is an introduction to discrete mathematics for engineering students. The course covers the following topics:
- Introduction
- mathematical induction
- Summation
- multiple summation
- floor and ceiling
- Akra-Bazzi theorem
- inexact summation
- Euler summation formula
- Asymptotics
- tower of hanoi
- big-O, big-Ω, big-Θ
- divide-and-conquer algorithms
- Recurrences and Generating Functions
- recurrences
- repertoire method
- Josephus problem
- generating functions
- Sets and Combinatorial Counting
- set theory
- multiplication principle
- subtraction and division principles
- combinatorial proofs
- distribute objects to people
- Elements of discrete probability
- multinomial theorem
- arrival problems
- inclusion-exclusion principle
- convolution, generalized binomial theorem
- parenthesizing expressions
- Introduction to Graph Theory
- handshaking lemma
- paths, cycles, connectedness
- properties of trees
- proving graph properties with induction
- complete and bipartite graphs
- matching
- Hall's theorem
- verifying Hall's condition
What is discrete mathematics?
Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics therefore excludes topics in "continuous mathematics" such as calculus or Euclidean geometry. Discrete objects can often be enumerated by integers. More formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets (sets that have the same cardinality as subsets of the natural numbers, including rational numbers but not real numbers). However, there is no exact definition of the term "discrete mathematics." Indeed, discrete mathematics is described less by what is included than by what is excluded: continuously varying quantities and related notions.
How the mathematical problem is proved?
- Direct Proof: A direct proof is a method of proof that establishes the truth or validity of a statement by logically showing that it must follow from a given set of assumptions. It is a straightforward method of proof that is used when the conclusion is a direct result of the hypothesis.
- Proof by Contradiction: Proof by contradiction is a method of proof that establishes the truth or validity of a statement by showing that the negation of the statement leads to a contradiction. It is a powerful method of proof that is used when direct proof is not possible or when it is easier to prove the negation of the statement.
- Proof by Induction: Proof by induction is a method of proof that establishes the truth or validity of a statement by showing that it holds for a base case and that if it holds for any case, then it must hold for the next case. It is a method of proof that is used to prove statements about natural numbers or other recursively defined objects.