CSCI 2100 - Discrete Mathematics
Credits: 4
Catalog Description
Intended for math and/or computer science majors/minors. Topics include: logic, sets, functions, partitions and equivalence relations, binary operations, composition of functions, mathematical induction, combinatorics, matrix representations of graphs, isomorphisms of graphs, trees and spanning trees, recurrence relations, and generating functions. Applications include: Boolean algebra, algorithms and their efficiency, pigeonhole principle, and the halting problem.
Prerequisite(s) (must have a grade of C or better): MATH 1400 with a grade of C or better, or equivalent.
Cross-Listed Course(s): MATH 2100
Additional fee to student: No
Learner Outcomes
- Utilize the laws of logic to determine if statements are equivalent or arguments are valid.
- Demonstrate knowledge of DeMorgan’s Laws, logical equivalence, tautologies, and contradictions.
- Distinguish between universally quantified statements and existentially quantified statements and be able to negate each.
- Construct combinatorial circuits and utilize Boolean Algebra to simplify circuits.
- Prove statements by method of induction, direct proof, proof by contradiction, proof of contrapositive and proof by smallest counterexample.
- Demonstrate knowledge in set theory including power sets, subsets, and perform set operations of union, intersection, complement, and differences of sets.
- Utilize Venn diagrams to represent the combination of sets.
- Determine if a relation on a set is a partial order; construct a Haase diagram for a partial order.
- Determine if a binary relation is reflexive, symmetric, or transitive.
- Define the distinct equivalence classes of an equivalence relation on a set.
- Prove that a function is one-to-one, onto, or a bijection.
- Compute the composition of functions.
- Determine Big-Oh, Big-Omega, and other approximations of a function.
- Determine the run-time complexity of an algorithm.
- List several terms of a recursively defined function and given a recursively defined function, determine an explicit formula for the sequence.
- Solve recurrence relations using the techniques of substitution (iteration) and characteristic roots.
- Proof and application of elementary number theory topics including divisibility, floor and ceiling function, Euler’s phi-function, Euclid’s algorithm, modular arithmetic, and factorials.
- Apply elementary number theory to represent numbers in different bases, and solve problems in cryptology.
- Elementary graph theory and applications involving representation of graphs, connectedness, cycles, isomorphisms of graphs, Euler circuits and Hamiltonian circuits.
- Find a minimal spanning tree for a graph and indicate the order in which edges are added to form the tree.
- Model physical situations using graphs and apply elementary graph theory to find solutions.
- Elementary combinatorics including possibility trees, permutations and combinations, and the inclusion and exclusion principle.
- Apply the pigeonhole principle.
- Probability theory including conditional probability and independence.
Major Areas of Course Content
- Logic and proof
- Elementary set theory
- Relations and functions
- Recurrence relations
- Elementary number theory and applications
- Elementary graph theory and applications
- Combinatorics and probability
Credit for Prior Learning Options
Course-Specific Exam
Credit for Prior Learning Option Procedure(s)
- The student should contact an instructor currently teaching or scheduled to teach the desired course.
- The instructor will provide and schedule an exam date.
- The student is to bring the Credit by Exam form to the scheduled exam.
- The faculty member will notify the student and Records Office of the results.
Add to Portfolio (opens a new window)
|
