Discrete Structures
Prerequisites
‘C’ or better in MATH 151 (Calculus and Analytic Geometry I) or MATH 140 (Differential Calculus)
Description
This course introduces the fundamental tools, topics and concepts of discrete mathematics needed to study computer science. This course emphasizes counting methods, proof techniques and problem solving strategies. Topics include Boolean algebra; set theory; symbolic logic; predicate calculus; number theory; the methods of direct, indirect and inductive proofs; objective functions; equivalence relations; graphs; set partitions; combinatorics; modular arithmetic; summations; and recurrences.
Course Outcomes
Each student will:
- Explain formal logical statements, including quantified statements and analyze logical arguments to identify errors and determine correctness.
- Apply methods of direct and indirect proof to problems in number theory, set theory, and properties of functions and relations.
- Apply mathematical induction and strong mathematical induction to prove identities.
- Solve recurrence relations and check correctness using mathematical induction.
- Demonstrate fundamental operations of sets, functions, and relations.
- Select and apply appropriate formulas to solve counting problems.
- Determine if a proposed probability distribution satisfies the probability axioms.
- Explain and compute the mean of a probability distribution.
- Illustrate concepts of graphs and their representations.
Student Outcomes
| Level Of Emphasis | |||
| ABET Outcome | Low | Medium | High |
| Analyze a complex computing problem and to apply principles of computing and other relevant disciplines to identify solutions. | x | ||
| Design, implement, and evaluate a computing-based solution to meet a given set of computing requirements in the context of the program’s discipline. | x | ||
| Communicate effectively in a variety of professional contexts. | x | ||
| Recognize professional responsibilities and make informed judgments in computing practice based on legal and ethical principles. | x | ||
| Function effectively as a member or leader of a team engaged in activities appropriate to the program’s discipline. | x | ||
| Apply computer science theory and software development fundamentals to produce computing-based solutions. | x | ||
Text
Either of the following:
- Epp, S. (2019). Discrete Mathematics with Applications. Fifth Edition. Cengage. ISBN-10: 1337694193, ISBN-13: 978-1337694193.
- Rosen, K. (2019). Discrete Mathematics and Its Applications. Eighth Edition. McGraw Hill. ISBN-13: 9781259676512
Topics
- Formal logic including quantified statements; applications to circuits.
- Methods of direct and indirect proof applied to elementary number theory, set theory, functions, and relations.
- Mathematical induction and recursion.
- Set theory, functions, and relations.
- Counting formulas and probability.
- Probability axioms and the mean of a probability distribution.
- Graphs and their representations; trees.
Grading
| 10% – 20% | Homework Assignments |
| 20% – 60% | Quizzes or Midterm Exams |
| 20% – 30% | Final Exam |
| 0% – 10% | Other (participation, in-class assignments, etc.) |
Updated June 19, 2023 by JD and JK