Discrete Mathematics I

Curriculum Guideline

Effective Date:
Course
Discontinued
No
Course Code
MATH 1130
Descriptive
Discrete Mathematics I
Department
Mathematics
Faculty
Science & Technology
Credits
3.00
Start Date
End Term
Not Specified
PLAR
No
Semester Length
15 weeks
Max Class Size
35
Course Designation
None
Industry Designation
None
Contact Hours
Lecture:   4 hours/week
and  
Tutorial: 1 hour/week
Method(s) Of Instruction
Lecture
Tutorial
Learning Activities

Lectures, problem sessions, tutorial sessions and assignments

Course Description
MATH 1130 is the first of two courses for computing science students. Topics include logic, set theory, functions, algorithms, mathematical reasoning, recursive definitions, counting and relations.
Course Content
  1. Logic
  2. Methods of Proof
  3. Set Theory
  4. Functions
  5. Sequences and Summation
  6. Algorithms
  7. Growth of Functions
  8. Divisibility and Modular Arithmetic
  9. Representation of Integers
  10. Mathematical Induction
  11. Recursion
  12. Counting
  13. Probability
  14. Relations

Optional Topics

  1. Formal Languages
  2. Finite State Machines
Learning Outcomes

Upon completion of this course, successful students will be able to:

  • translate an English statement into symbolic form using propositional variables or functions, logical connectives and quantifiers.
  • determine the truth value of a compound proposition.
  • state the converse, inverse, and contrapositive of an implication.
  • verify logical equivalencies.
  • determine whether a proposition is a tautology, contingency, or contradiction.
  • find the dual of a proposition.
  • negate a quantified expression.
  • derive a valid conclusion using rules of inference.
  • analyze the validity of an argument using rules of inference.
  • apply direct proof, indirect proof, and proof by contradiction methods to prove a mathematical theorem.
  • determine the cardinality of sets, subsets, power sets and Cartesian products.
  • combine sets using set operators.
  • prove set identities using the method of subsets, membership tables, and derivations from standard set identities.
  • determine if a function is an injection, surjection or a bijection.
  • describe the domain, codomain, and range of a function.
  • find the image and preimage of a point or set of points of a function.
  • find the composition of two or more functions.
  • find the inverse of a bijective function.
  • derive properties related to the floor and ceiling functions.
  • find the value of a term in a sequence.
  • represent a sequence in recursive and closed forms.
  • evaluate finite sums.
  • give a big-O estimate for a function.
  • write a simple algorithm.
  • determine the time complexity of a simple algorithm.
  • use divisibility properties of integers and the division algorithm to derive and prove properties of congruences and modular arithmetic.
  • find the greatest common divisor of two integers using the Euclidean algorithm.
  • convert the representation of an integer from one base to another.
  • prove mathematical theorems using strong and weak principles of mathematical induction.
  • convert the representation of a function or set from recursive to closed form, and visa versa.
  • solve counting problems using sum, product, inclusion-exclusion (up to three sets), and pigeon hole principles.
  • count the number of different combinations and permutations of elements selected from a set. This includes cases of distinguishable and indistinguishable elements as well as selection with and without replacement.
  • find the expansion of a binomial expression.
  • determine the probability of an event for an equi-probable sample space.
  • determine whether or not a relation is reflexive, irreflexive, symmetric, antisymmetric, or transitive.
  • represent a relation as a matrix and a digraph.

Optional Topics:

  • determine whether a string belongs to the language generated by a given grammar.
  • classify a grammar.
  • find the language created by a grammar.
  • draw the state diagram for a finite-state machine.
  • construct a finite-state machine to perform a function.
  • determine the output of a finite state machine.
Means of Assessment

Assessment will be carried out in accordance with Douglas College Evaluation policy.  The instructor will present a written course outline with specific evaluation criteria at the beginning of the semester.  Evaluation will be based on the following:

Weekly quizzes 0-40%
Term tests 20-70%
Assignments 0-20%
Attendance 0-5%
Class participation 0-5%
Tutorials 0-10%
Final examination 30-40%
Total 100%
Textbook Materials

Consult the Douglas College Bookstore for the latest required textbooks and materials.

Example textbooks and materials may include:

Rosen, H.R., Discrete Mathematics and Its Applications, current edition, McGraw Hill.

Grimaldi, R.P, Discrete and Combinatorial Mathematics: An Applied Introduction, current edition, Pearson.

Prerequisites

Precalculus 12 with a C or better; or Foundations of Math 12 with a C or better.

Which Prerequisite