Academic Catalog

MATH 22: DISCRETE MATHEMATICS

Foothill College Course Outline of Record

Foothill College Course Outline of Record
Heading Value
Effective Term: Summer 2025
Units: 5
Hours: 5 lecture per week (60 total per quarter)
Prerequisite: C S 1A or C S 2A or C S 3A or equivalent; MATH 47 or MATH 48C or equivalent.
Advisory: Demonstrated proficiency in English by placement via multiple measures OR through an equivalent placement process OR completion of ESLL 125 & ESLL 249; not open to students with credit in CIS 18 or C S 18.
Degree & Credit Status: Degree-Applicable Credit Course
Foothill GE: Area 2: Mathematical Concepts & Quantitative Reasoning
Transferable: CSU/UC
Grade Type: Letter Grade (Request for Pass/No Pass)
Repeatability: Not Repeatable
Cross-Listed: C S 18

Student Learning Outcomes

  • Students will apply number theory, combinatorics, discrete probability, graph theory, and recursion to solve various application problems.
  • Students will develop conceptual understanding of formal logic and various methods of arguments that can be used as the basis of a computer program. They will demonstrate and communicate this understanding by writing proofs involving number theory, set theory, combinatorics, and discrete probability.
  • Use formal logic and various methods of arguments to formally write proofs involving number theory, set theory, combinatorics, and discrete probability.
  • Students will develop fluency in deciphering and using the language of logic, proof, and set theory, constructing logical arguments and proofs that can then be used as the basis of a computer program.

Description

This course is for any student majoring in math or computer science, as well as for students interested in the topics taught in this course. Discrete mathematics: set theory, logic, Boolean algebra, methods of proof, mathematical induction, number theory, discrete probability, combinatorics, functions, relations, recursion, algorithm efficiencies, graphs, trees.

Course Objectives

The student will be able to:

  1. Use formal logic in constructing valid arguments.
  2. Write proofs formally, including writing proofs using symbolic logic and Boolean algebra.
  3. Use number theory to solve problems.
  4. Understand the basics of set theory, including solving problems in combinatorics and probability theory.
  5. Prove combination and permutation principles and use them to solve problems.
  6. Understand the definition of functions.
  7. Use recursive thinking and method to solve recurrence relations, including using recursion to analyze algorithms and programs.
  8. Analyze and write algorithms.
  9. Identify relations and their properties.
  10. Draw and analyze graphs and trees, including applying matrices to analyze graphs and trees.
  11. Solve application problems from computer science, including using finite state machines to model computer operations.
  12. Discuss mathematical problems and write solutions in accurate mathematical language and notation.
  13. Interpret mathematical solutions.

Course Content

  1. Logic
    1. Logical Forms and Equivalences
    2. Conditional Statements
    3. Valid and Invalid Arguments
    4. Predicates and Quantified Statements
    5. Boolean Algebra
    6. Application: Digital Logic Circuits
  2. Methods of Proof/Proof Techniques
    1. Direct Proof
    2. Proof by Counterexample
    3. Proof by Division into Cases
    4. Proof by Contradiction and Contraposition
    5. Proof by Induction
    6. Strong Mathematical Induction and Well-Ordering
  3. Number Theory
    1. Properties of Prime and Rational Numbers
    2. Unique Factorization Theorem
    3. Quotient-Remainder Theorem
    4. Modular Arithmetic
    5. Floor and Ceiling Notation
    6. Applications of Number Theory to Problem Solving
    7. Principal of Inclusion and Exclusion
  4. Set Theory
    1. Notation
    2. Operations on Sets
    3. Cartesian Products
    4. Proving Set Identities
  5. Counting and Probability
    1. Events and Sample Space
    2. Possibility Trees and Multiplication Rule
    3. Addition Rule
    4. Pigeonhole Principle
    5. Combinations and Permutations
    6. Pascal's Formula
    7. Binomial Theorem
    8. Discrete Probability Axioms
    9. Expected Value
    10. Conditional Probability, Bayes' Formula
    11. Integer Random Variables
    12. Expectations
    13. Law of Large Numbers
  6. Functions
    1. One-to-One, Onto, Inverses
    2. Compositions
    3. Well Defined Functions
  7. Recursion
    1. Recursively Defined Sequences
      1. Fibonacci Numbers
    2. Solving Recurrence Relations by Iteration
    3. Solving Recurrence Relations using Logarithms
    4. Verifying Solutions by Mathematical Induction
  8. Efficiency of Algorithms
    1. Big-O, Big-Theta, and Big-Omega Notation
    2. Exponential and Logarithmic Orders
    3. Computing Orders of Algorithms
    4. Analysis of Various Sort and Search Algorithms
  9. Relations
    1. Binary Relations, N-ary Relations
    2. Directed Graphs
    3. Inverse Relations
    4. Reflexivity, Symmetry, and Transitivity
    5. Equivalence Relations and Classes
  10. Graphs and Trees
    1. Definitions and Properties
    2. Paths and Circuits
      1. Euler Path
      2. Hamiltonian Circuit
      3. Shortest Path and Minimal Spanning Tree
    3. Matrix Representation of Graphs
    4. Isomorphisms of Graphs
    5. Spanning Trees
    6. Traversal Problems
    7. Decision Trees
    8. Huffman Codes
    9. Warshall's Algorithm
  11. Solve Application Problems from Computer Science
    1. The Application of Mathematical Induction to Recursive Computer Algorithms
    2. The Use of Sequences in Loop Structures
    3. The Application of Computer Logic
      1. AND-, OR- and NOT-GATES
      2. Boolean Algebra Structure
      3. Logic Networks
      4. Minimization
    4. Breaking Down Problems or Functions into Components, Sub-problems, or Sub-functions
    5. The use of Time-complexity to Determine Big-O Growth Rate of Various Algorithms
    6. Articulation Points (Cut Vertices) and Computer Networks
    7. Modeling Arithmetic, Computation, and Languages, Including Algebraic Structures, Finite-state Machines, and Formal Logic
  12. Discuss Mathematical Problems and Write Solutions in Accurate Mathematical Language and Notation
    1. Application Problems from Other Disciplines
    2. Proper Notation
  13. Interpret Mathematical Solutions
    1. Explain the Significance of Solutions to Application Problems

Lab Content

Not applicable.

Special Facilities and/or Equipment

1. Access to graphing technology, such as a graphing calculator or graphing software.
2. When taught online or hybrid: internet access; course management system; specific software related to the course.

Method(s) of Evaluation

Methods of Evaluation may include but are not limited to the following:

Written homework
Quizzes, tests
Proctored comprehensive final examination

Method(s) of Instruction

Methods of Instruction may include but are not limited to the following:

Lecture
Discussion
Cooperative learning exercises

Representative Text(s) and Other Materials

Epp, Susanna. Discrete Mathematics with Applications, 5th ed.. 2020.

Liben-Nowell, David. Connecting Discrete Mathematics and Computer Science, 2nd ed.. 2022.

Types and/or Examples of Required Reading, Writing, and Outside of Class Assignments

  1. Homework problems covering subject matter from text and related material ranging from 30-60 problems per week. Students will need to employ critical thinking in order to complete assignments.
  2. Five hours per week of lecture covering subject matter from text and related material. Reading and study of the textbook, related materials, and notes.
  3. Student projects covering subject matter from textbook and related materials. Projects will require students to discuss mathematical problems, write solutions in accurate mathematical language and notation, and interpret mathematical solutions. Projects may require the use of a computer algebra system such as Mathematica or MATLAB.
  4. Worksheets: Problems and activities covering the subject matter. Such problems and activities will require students to think critically. Such worksheets may be completed inside and/or outside of class.

Discipline(s)

Mathematics