ECE 20869 - Discrete Mathematics for Computer Engineering


This course ran as ECE 36900 prior to Fall 2022

Course Details

Lecture Hours: 3 Credits: 3

Counts as:

Normally Offered:

Each Fall, Spring


On-campus only


ECE 20875 or ECE 26400 [may be taken concurrently]

Requisites by Topic:

Advanced programming experience.

Catalog Description:

This course introduces discrete mathematical structures, with a focus on developing problem-solving skills and abstract reasoning. Students will attain substantial experience formulating and reasoning about a wide range of discrete mathematics problems. Topics generally include sets, sequences, relations, mappings, recursive definition, formal logic syntax and semantics, mathematical induction, recursion and loop invariants, counting and combinatorics, countability, asymptotic complexity, finite-state automata, regular expressions, and non-determinism.

Required Text(s):

  1. Mathematical Structures for Computer Science , 7 Edition , Judith L. Gersting , W. H. Freeman , 2014 , ISBN No. 978-1429215107

Recommended Text(s):


Learning Outcomes:

A student who successfully fulfills the course requirements will have demonstrated:
  1. an ability to define, reason about, and operate on sets using basic set operations and recursive definition. [1,7]
  2. an ability to represent and verify entailment arguments in predicate logic, both syntactically and semantically. [1,3,7]
  3. an ability to argue carefully using a variety of informal proof techniques, including mathematical induction. [1,3,7]
  4. an ability to count in a wide range of settings including permutations, combinations, countable infinities, and recurrence equations. [1,7]
  5. an ability to define and reason about functions and binary relations and work with their useful properties. [1]
  6. an ability to define finite-state automata and regular expressions for languages, and relate these formalisms using non-determinism. [1,7]
  7. an ability to formulate algorithmic problems as decision problems and reason about their decidability and scalable solvability. [1,7]

Lecture Outline:

Weeks Topic
2 Sets and recursive definition
3 Boolean and predicate logics: syntax, semantics, entailment, proof
2 Informal proof: direct and indirect proof, case analysis and proof by contradiction, mathematical induction, loop invariants
3 Counting: countability/uncountability, permutation and combinations, pigeonhole principle, binomial theorem, inclusion/exclusion, recurrence equations
1 Relations and functions: equivalence relations, partial orders, injection/surjection/bijection, inverse and composition
4 Decision problems: undecidability, finite-state automata, regular expressions and Kleene's theorem, asymptotic complexity, P and NP

Assessment Method:

Problem sets, exams and Participation