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