CSC 226 - Discrete Mathematics for Computer Scientists

Catalog Description:

Propositional logic and predicate calculus. Logic gates and circuits. Methods of proof. Mathematical induction. Recursive definitions and functions. Solving recurrences. Asymptotic growth of functions. Elementary combinatorics and probability. Introduction to graph theory. Binary relations, including posets and equivalence relations. This course assumes knowledge of topics covered in high-school Algebra I and II. Most seats reserved for CSC and CPE majors and Computer Programming minors.


Contact Hours: Prerequisites: None
Co-requisites: None
Restrictions: None
Coordinator: Dr. Jessica Schmidt
Textbook: CSC 226: Discrete Math ZyBook

Course Outcomes:

At the conclusion of this course, students should be able to
  1. Represent logical statements in propositional and predicate calculus, and use truth tables and formal proofs to determine their truth values.
  2. Create a truth table for a logical expression. Derive a logical expression from a given truth table. Design a circuit to perform a simple task.
  3. Construct a circuit from a logical expression using AND, OR, and NOT gates. Simplify logical expressions. Derive a logical expression from a given circuit.
  4. Describe set notations using predicate calculus. Use predicate calculus to prove set theoretic propositions.
  5. Describe and use proof by induction. Derive closed form representations for recursively defined sequences; prove their correctness by induction. Derive recursive sequences from closed form functions and prove their equivalence by induction.
  6. Describe asymptotic growth of functions, compare functions using big-oh notation. Compare asymptotic growth and prove inequalities by induction. Determine and solve recurrences arising from algorithms.
  7. Define binary relations and their properties using predicate calculus. Represent binary relations as ordered pairs, matrices or graphs. Combine binary relations by union, intersection, and composition using matrix operations.
  8. Describe and calculate permutations and combinations with and without replacement and with and without distinguishable objects. Describe and apply the pigeonhole principle. Calculate probabilities using basic principles.
  9. Describe and determine the existence of Euler circuits and paths and Hamilton circuits and paths in graphs. Determine the minimum spanning tree of a graph. Construct and analyze Hasse diagrams for partially ordered sets.


Topics:

See Course Listings

See Course Coordinators