Course Outline for Mathematics 8
Discrete Mathematics

Effective: Fall 2024
SLO Rev:

Catalog Description:

MTH 8 - Discrete Mathematics

3.00 Units

Sets, relations and functions; logic, methods of proof, induction; combinatorics, discrete probability, recursion, and recurrence relations; graphs and trees; logic circuits; finite state machines. Designed for majors in mathematics and computer science.
Prerequisite: MTH 1, Strongly Recommended: CSCI 14.
CB03: TOP Code 1701.00 - Mathematics, General
CIP Code 27.0101 - Mathematics, General.
Course Grading: Letter Grade Only
Type Units Inside of Class Hours Outside of Class Hours Total Student Learning Hours
Lecture 3.00 54.00 108.00 162.00
Laboratory 0.00 18.00 0.00 18.00
Total 3.00 72.00 108.00 180.00

Measurable Objectives:

Upon completion of this course, the student should be able to:
  1. write proofs using symbolic logic and Boolean Algebra;
  2. prove mathematical statements using proof by contradiction, proof by contraposition and proof by cases;
  3. apply mathematical induction to problems in sequences, series, and algorithms;
  4. solve counting problems using elementary counting techniques: sum and product rules; pigeonhole principle, combinations and permutations; inclusion/exclusion principle;
  5. use sets to solve problems in combinatorics and probability theory;
  6. use recursion to analyze algorithms and programs;
  7. apply matrices to analyze graphs and trees;
  8. apply concepts of graph theory to path problems (e.g., shortest path, Euler path, Hamilton path);
  9. perform algorithms to traverse a tree and to find a minimum spanning tree in a graph;
  10. apply laws of Boolean algebra to simplifying logic circuits;
  11. solve probability problems using probability rules and properties of random variables;
  12. use finite state machines to model computer operations;
  13. design a finite state machine to recognize a given language.

Course Content:

  1. Propositional and Predicate Logic
    1. Symbolic representation of statements
    2. Tautologies
    3. Logical implication
    4. Logical Equivalence
    5. Rules of inferrence
    6. Applications to logic programming
  2. Sets, functions and relations
  3. Mathematical induction and applications to proving correctness of recursively defined funtions
  4. Analysis of algorithms
    1. Big Oh notation
    2. Recurrence relations
  5. Combinatorics
    1. Permutaions and cominations
    2. Priciple of inclusion and exclusion
    3. Pigeonhole principle
    4. Binomial Theorem
    5. Applications to probability
  6. Big Oh notation, complexity of algorithms
  7. Graphs and Trees
    1. Their Representations
    2. Decision trees
    3. Huffman Codes
  8. Graphs and Tree Algorithms
    1. Euler and Hamilton paths
    2. Graph isomorphism
    3. Minimal spanning tree
    4. Shortest path
    5. Transversals
    6. Articulation points
    7. Warshall's algorithm
  9. Boolean algebra, logic circuits, Karnaugh maps
  10. Modeling computation with finite automata and languages
    1. Finite state machines
    2. Turing machines
Lab:
  1. Proof techniques
    1. Proof by cases
    2. Proof by contradiction
    3. Proof by contraposition
    4. Constructive and non-constructive existence proofs
  2. Applications in number theory
    1. Infinitude of primes
    2. Irrationality of sqrt(2)
    3. Properties of modular arithmetic

Methods of Instruction:

  1. Lecture/Discussion
  2. Demonstration/Exercise
  3. Problem Solving
  4. Group Activities
  5. Distance Education

Assignments and Methods of Evaluating Student Progress:

1. Typical Assignments
  1. How many different functions are there from a set of 6 elements to itself? How many of them are: (a) onto? (b) not onto? (c) one-to-one (d) not one-to-one?
  2. Let f(x) = x^2 +1, x is real on [ -2, 4]. Define a relation R on A X A to be (a, b) is in R if and only if f(a) = f(b). Show R is an equivalence relation. Describe the equivalence classes.
  3. Design an algorithm that determines whether a function from a set of n elements to itself is one-to-one, and another that determines whether the function is onto.
2. Methods of Evaluating Student Progress
  1. Exams/Tests
  2. Quizzes
  3. Homework
  4. Final Examination
3. Student Learning Outcomes
Upon the completion of this course, the student should be able to:
  1. Critically analyze mathematical problems using a logical methodology.
  2. Communicate mathematical ideas, understand definitions, and interpret concepts.
  3. Increase confidence in understanding mathematical concepts, communicating ideas and thinking analytically.

Textbooks (Typical):

  1. Rosen, Kenneth (2019). Discrete Mathematics (8th). McGraw-Hill Publishers.
Additional Materials:
  • A scientific calculator may be required.

Abbreviated Class Schedule Description:

Sets, relations and functions; logic, methods of proof, induction; combinatorics, discrete probability, recursion, and recurrence relations; graphs and trees; logic circuits; finite state machines. Designed for majors in mathematics and computer science.
Prerequisite: MTH 1, Strongly Recommended: CSCI 14.

Discipline:
Mathematics*, or Computer Science*