Course Outcomes for CSC 226 - Discrete Mathematics for Computer Scientists
- Represent logical statements in propositional and predicate calculus, and use truth tables and formal proofs to determine their truth values.
- 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.
- Construct a circuit from a logical expression using AND, OR, and NOT gates. Simplify logical expressions. Derive a logical expression from a given circuit.
- Describe set notations using predicate calculus. Determine the power of a set. Use predicate calculus to prove set theoretic propositions.
- Describe and use the first, second, and general principles of 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.
- 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. Determine big-oh running times for algorithms.
- Define binary relations and their properties using predicate calculus. Represent binary relations as ordered pairs, matrices, predicates, or graphs. Combine binary relations by union, intersection, and composition using matrix operations. Find the reflexive, symmetric, and transitive closures of a binary relation.
- Describe and calculate permutations and combinations with and without replacement and with and without distinguishable objects. Describe and apply the pigeonhole principle.
- 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.
See Course Listings