A. Course
Title Discrete
Mathematics
B. Semester
Credit Value 4
credits
C. Prerequisites MATH
1400 with a grade of C or better or equivalent
D. Catalog
Description
(Formerly MATH 211) 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
graphics trees and spanning trees; recurrence relations; and generating
functions. Applications include Boolean
algebra; algorithms and their efficiency; pigeon hold principle, and the
halting problem.
E. General
Course Purpose
F. Course
Information
1. Hours per Week
a. Classroom 4
b. Laboratory
c. Clinical
d. Other
(describe) 8 hours homework
2. Degree for which Course is Intended AA
3. Program of Study for which Course is Required Transfer
G. Learner Outcomes
1. At the conclusion of the course, the student
should be able to:
A.
Make truth tables for statements involving "not",
"and", "or", "if-then", and "if and only
if".
B.
Transfer to and from symbolic notation.
C.
Demonstrate their knowledge of DeMorgan's Laws, logical equivalence,
tautologies, and contradictions.
D.
Write the negation of a conditional statement.
E.
Write the contrapositive, converse, and inverse of a conditional
statement and know that the contrapositive and the original conditional
statement have the same truth value.
F.
Determine if an argument is valid or invalid by modus ponens, modus
tollens, converse and inverse errors, rule of contradiction, or using a truth
table to determine whether an argument form is valid.
G.
Construct circuits for Boolean expressions and find Boolean expressions
for a given circuit.
H.
Simplify circuits by using Boolean Algebra.
I.
Convert from binary or hexadecimal to decimal and from decimal to
binary or hexadecimal.
J.
Add and Subtract in binary.
K.
Draw a circuit for computer addition.
L.
Rewrite statements using quantifiers in English and rewrite English
statements using quantifiers and variables.
M.
Write the negation of statements that involve quantifiers.
N.
Determine if an argument containing quantifiers is valid or invalid.
O.
Prove statements including rationals, divisibility, mod floor, and
ceiling by direct proof, disprove by counterexample.
P.
Prove statements by using an indirect argument: contradiction and contrapositive.
Q.
Find explicit formulas for sequences, compute summations and products,
and write sums or products in summation or product notation.
R.
Prove statements using Mathematical Induction.
S.
Use the following terms and their symbols correctly: subset, proper subset, element of, equals,
union, intersection, difference, complement, Cartesian product, empty set,
partitions, power sets.
T.
Prove set statements are true directly from the definitions of set
operations or find a counterexample for each statement that is false.
U.
Illustrate set statements by drawing a Venn diagram.
V.
Count elements of a list: permutations,
combinations, and possibility trees.
W.
Find the probability of an event happening.
X.
Calculate (a + b)
using Pascal's triangle and using the Binomial Theorem.
Y.
Determine if a relation is a function, a one-to-one function, onto
function, or inverse function and prove that it is so or give a counterexample.
Z.
Find the finite-state automaton's states, input symbols, initial state,
accepting states, and write its annotated next-state table when given its
transition diagram.
AA. Find the finite-state
automaton's states, input symbols, initial state, accepting states, and draw
its transition diagram when given its annotated next-state table.
BB. Work applications using the
Pigeonhole Principle.
CC. Find the composition of
functions.
DD. List several terms of a
recursively defined function and given a recursively defined function find the
explicit formula for the sequence.
EE. Express Statements using
O-notation.
FF.
Find the best Big-Oh approximation for a polynomial, from the set of
rational power functions, and functions involving logs.
GG. Determine if a binary
relation is reflexive, symmetric, or transitive.
HH. Find the distinct
equivalence classes of an equivalence relation on a set.
II.
For a Finite-state automata A, given by a transition
diagram, find 0-, 1-, etc equivalence classes of states of A. Draw the transition diagram for A, the
quotient automation of A.
JJ.
Determine if two automata are equivalent, given their transition
diagrams.
KK. Draw the Hasse diagram for a
relation.
LL. Determine whether a walk is
a path, closed walk, circuit, simple circuit, or just a walk.
MM. Find an Euler circuit for a
graph that has one or explain why it does not have one.
NN. Find a Hamiltonian circuit
for a graph that has one or explain why is does not have one.
OO. Determine whether a pair of graphs are isomorphic. If they are, find functions that define the
isomorphism. If they are not, give an
isomorphic invariant that they do not share.
PP. Determine whether a graph is
a tree.
QQ. Find a minimal spanning tree
for a graph and indicate the order in which edges are added to form the tree.
H. ARCC Guiding Principle(s) Satisfied
Identify the learner outcomes (from G) which relate to each of the guiding principles listed below or describe how the guiding principle(s) is/are used in this course.
1. Clear Thinking A-QQ
2. Effective Communication A-QQ
3. Accepting Diversity
4. Ethical Decision-Making
I.
J. Entry Level Skills/Knowledge
Choose: 1 (basic), 2 (pre-college), or 3 (college)
1. Mathematics: Knowledge and skills from the
successful completion of MATH 1400 with a grade of C or better or equivalent
2.
3. Writing: 3
K. Major Areas of Course Content:
1.
L. Outcomes Assessment:
1. Learner outcomes that will be assessed (from G): All
2. How information will be collected to assess outcomes:
Assessment methods
throughout the course's duration may include, but not be limited to the
following: assigned and graded homework
problems, assigned and graded problems that are parallel to the homework
problems, group problem-solving sessions, written group reports or summaries,
quizzes/tests consisting of open-ended questions (that require students to
demonstrate certain knowledge and skills as the organize, analyze, and
synthesize ideas), computer lab projects, computer lab reports, and a
comprehensive final exam.
3. When information will be collected (i.e., each semester, yearly):
4. Measure(s) used to determine if an outcome has been achieved:
The student's grade will be
based upon the score earned on the work done for the class, which may include,
but not be limited to, the following: computer lab reports, assigned problems,
quizzes, tests, and a comprehensive final exam.
5. Person/Group responsible for information collection:
6. Person/Group responsible for reviewing the resulting data:
M. Procedure for Credit by Examination:
The student's grade is based on the percent of
points correct on the comprehensive final exam according to the following:
90-100%--A, 80-89%--B, 70-79%--C, 60-69%--D, Below 60%--F.
A "P" grade is 70% or better.
N. Proposed Implementation Date: Fall 1998
N:\CCO\MATH\MATH2100.DOC