Active Outline

General Information

Course ID (CB01A and CB01B)
MATHD022H
Course Title (CB02)
Discrete Mathematics - HONORS
Course Credit Status
Credit - Degree Applicable
Effective Term
Fall 2023
Course Description
This course explores elements of discrete mathematics with applications to computer science. Topics include methods of proof, mathematical induction, logic, sets, relations, graphs, combinatorics, and Boolean algebra. Because this is an honors course, students will be expected to complete extra assignments to gain deeper insight into discrete mathematics.
Faculty Requirements
Course Family
Not Applicable

Course Justification

This course satisfies the CSU GE/Breadth requirement Area B4 Mathematics and Quantitative Reasoning. This course satisfies the IGETC requirement Area 2 Mathematical Concepts and Quantitative Reasoning. This course belongs on the Liberal Arts AA degree and is CSU and UC transferable. This course in Discrete Mathematics represents an alternate introduction to college-level mathematics, with emphasis on rigorous mathematical thinking and mathematical proof, distinct from calculus. Discrete mathematics is the branch of mathematics dealing with objects that can assume only distinct, separated values, in contrast to the continuous characteristics of calculus. The content in this course is required for advanced courses in mathematics and computer science. This class is the honors version of Discrete Mathematics and as a result, includes more advanced assignments and assessments.

Foothill Equivalency

Does the course have a Foothill equivalent?
Yes
Foothill Course ID
MATH F022.

Course Philosophy

Course Philosophy
Discrete Mathematics encompasses a variety of topics of contemporary importance in applications, especially in areas of decision science, computer science, and computer engineering, but also in diverse fields such as biology and the social sciences. The Mathematics Association of America recommends that the course be taught at the "intellectual level" of calculus. Discrete mathematics incorporates work with algorithms, which are the codified procedures used to solve particular problems. The course explores what proof is, and provides students with practice in constructing proofs of different types, especially mathematical induction. Graph theory, investigating how things are connected, and combinatorics, the science of counting complex arrangements, are important components of this course. It explores recursion and may go as deeply into that subject as to include generating functions. It also includes an introduction to symbolic logic and set theory, and their ramifications, and notes how Boolean algebras arise in each of these subjects. As the seemingly diverse topics covered in this course are examined, the student discovers that these distinct topics are interwoven and interrelated at many levels. Discrete mathematics can engage the student in challenging problem-solving and leaves room for the instructor to include topics of contemporary and historical interest and the worldwide history of these topics.

Formerly Statement

Course Development Options

Basic Skill Status (CB08)
Course is not a basic skills course.
Grade Options
  • Letter Grade
  • Pass/No Pass
Repeat Limit
0

Transferability & Gen. Ed. Options

Transferability
Transferable to both UC and CSU
CSU GEArea(s)StatusDetails
CGB4CSU GE Area B4 - Mathematics/Quantitative ReasoningApproved
IGETCArea(s)StatusDetails
IG2XIGETC Area 2 - Mathematical Concepts and Quantitative ReasoningApproved
C-IDArea(s)StatusDetails
MATHMathematicsApprovedC-ID COMP 152

Units and Hours

Summary

Minimum Credit Units
5.0
Maximum Credit Units
5.0

Weekly Student Hours

TypeIn ClassOut of Class
Lecture Hours5.010.0
Laboratory Hours0.00.0

Course Student Hours

Course Duration (Weeks)
12.0
Hours per unit divisor
36.0
Course In-Class (Contact) Hours
Lecture
60.0
Laboratory
0.0
Total
60.0
Course Out-of-Class Hours
Lecture
120.0
Laboratory
0.0
NA
0.0
Total
120.0

Prerequisite(s)

MATH D032. or MATH D032H (with a grade of C or better) or equivalent, and CIS D022A or CIS D035A (with a grade of C or better) or equivalent

Corequisite(s)

Advisory(ies)

ESL D272. and ESL D273., or ESL D472. and ESL D473., or eligibility for EWRT D001A or EWRT D01AH or ESL D005.

Limitation(s) on Enrollment

  • (Not open to students with credit in the non-Honors related course.)
  • (Admission into this course requires consent of the Honors Program Coordinator.)

Entrance Skill(s)

General Course Statement(s)

(See general education pages for the requirements this course meets.)

Methods of Instruction

Lecture and visual aids

Discussion of assigned reading

Discussion and problem-solving performed in class

In-class exploration of internet sites

Quiz and examination review performed in class

Homework and extended projects

Guest speakers

Collaborative learning and small group exercises

Collaborative projects

Problem solving and exploration activities using applications software

Assignments

  1. Reading of specified sections from the textbook such as explanations of topics discussed in class and solved examples.
  2. Problem-solving exercises
    1. Solve assigned problems from the text.
    2. Problems requiring written explanations of key concepts, analysis of problem-solving strategies, and use of mathematical vocabulary.
    3. Critical thinking problems, which may involve the analysis of discrete mathematical structures.
  3. An essay on a contemporary or historical mathematical source, which may require the student to read and present the essay in oral form to the class using visual aids and/or demonstrations.
  4. Participation in and contribution toward classroom discussions and collaborative group written analytical work involving comparative source materials such as the text or recent news articles.
  5. Periodic quizzes and/or assignments based on lecture topics composed of short answer questions, fill in the blanks, multiple choice questions, and/or numerical problems.
  6. A minimum of two mid-term examinations composed of short answer questions, fill in the blanks, multiple-choice questions, critical thinking question, and/or numerical problems.
  7. Group or individual projects on topics to be assigned by the instructor where the student will conduct research or analyze patterns of discrete mathematical structures.
  8. A project utilizing pseudocode to describe and/or analyze problems involving one or more topics of the course.
  9. In addition, the honors project assignment should include completion of additional sets of advanced problems that require a deeper understanding of the topics and/or a written research report (10 to 15 pages). Note: The honors project will require 10 or more hours of work beyond the regular (non-honors) course requirements, and will include higher expectations for achievement in this more advanced work.

Methods of Evaluation

  1. Reading assignments and problem-solving exercises will be evaluated in quizzes and examinations for accuracy of responses, critiques of mathematical statements for their truth values, formulations of mathematical proofs, or constructions of counterexamples. Students will receive a numerical score or a letter grade based on a scoring rubric to be developed by the instructor.
  2. Written essay will be evaluated for critical thinking skills and ability to analyze and apply patterns of discrete mathematical structures.
  3. Classroom discussions will be evaluated based on the extent of participation and contribution to the class dynamics.
  4. Projects will be evaluated based on presentation of the concepts and analyses of the given problem for completeness and scope of research.
  5. A final comprehensive examination will test the overall understanding of the student to critique a mathematical statement for its truth value, formulate a mathematical proof, construct a counterexample, or analyze and apply patterns of discrete mathematical structures. The comprehensive examination may be in a variety of formats such as multiple-choice questions, free-response questions, numerical problem solving, essay and short answer questions, and/or objective-type questions. Accuracy of responses will be scored and success to be evaluated based on a scoring rubric that will be developed by the instructor.
  6. The honors project will be evaluated based on depth of understanding and mastery of advanced techniques employed within the project.


Essential Student Materials/Essential College Facilities

Essential Student Materials: 
  • Scientific or graphing calculator
Essential College Facilities:
  • None.

Examples of Primary Texts and References

AuthorTitlePublisherDate/EditionISBN
*Epp, Susanna S., "Discrete Mathematics: Introduction to Mathematical Reasoning." 1st ed. Boston, MA: Cengage, 2011.
Rosen, Kenneth H., "Discrete Mathematics and Its Applications," 8th ed., New York, N.Y.; McGraw Hill, 2019
Dossey, John A. et al. "Discrete Mathematics." 5th ed. Pearson, 2006.
Epp, Susanna S., "Discrete Mathematics with Applications." 5th ed. Cengage Learning, 2020.

Examples of Supporting Texts and References

AuthorTitlePublisher
Andreescu, Titu, and Zuming Feng. A Path to Combinatorics for Undergraduates: Counting Strategies. Boston: Birkhauser, 2004
Gersting, Judith L. Mathematical Structures for Computer Science: A Modern Treatment of Discrete Mathematics. 7th Ed. New York: W. H. Freeman and Company, 2014.
Grimaldi, Ralph P. Discrete and Combinatorial Mathematics. 5th ed. Pearson, India, 2018.
Lovasz, L., J. Pekikan, and K. Vesztergombi. Discrete Mathematics: Elementary and Beyond. 3rd edition. New York: Springer, 2003.
Johnsonbaugh, Richard. Discrete Mathematics. 7th ed. Upper Saddle River, New Jersey: Pearson, 2007.
Marcus, Daniel A. Combinatorics, A Problem Oriented Approach. Wash. D.C.: Mathematical Association of America, 1998.
Washburn, Sherwood et al. Discrete Mathematics. Addison-Wesley Longman, Inc., 2000.
Ascher, Marcia. Ethnomathematics. Chapman & Hall/CRC, 1998.
Ascher, Marcia. Mathematics Elsewhere: An Exploration of Ideas Across Cultures. Princeton: Princeton Univ. Press, 2010.
Dunham, William. Journey Through Genius. Penguin Books USA, Inc., 1991.
Eglash, Ron. African Fractals. New Brunswick, N.J.: Rutgers University Press, 1999.
Joseph, George Gheverghese. The Crest of the Peacock: Non-European Roots of Mathematics. 3rd edition. Princeton, NJ: Princeton Univ. Press, 2010.
Using History to Teach Mathematics. Ed. by Victor J. Katz. Washington D.C.: Mathematical Association of America, 2000.
Vita Mathematica, Historical Research and Integration with Teaching. Ed. by Ronald Calinger. Washington D.C.: Mathematical Association of America, 1996.
Gardner, Martin. Martin Gardner's Mathematical Games: The Entire Collection of His Scientific American Columns. Searchable CD, The Mathematical Assoc. of America, 2005.
Hopkins, Brian. Resources for Teaching Discrete Mathematics. Mathematical Association of America, 2009.
What's Happening in the Mathematical Sciences? Vol. 1-5. Ed. by Barry Cipra. Washington D.C.: Mathematical Association of America.
Assessment Practices in Undergraduate Mathematics. Washington, D.C.: Mathematical Association of America, 1999.
Discrete Mathematics in the Schools. Ed. by Rosenstein et al. American Mathematical Society and National Council of Teachers of Mathematics, 1997.
Tucker, Alan. Discrete Mathematics in the Core Curriculum, in Dossey, John A., ed. Confronting the Core Curriculum: Considering Change in the Undergraduate mathematics Major. MAA Notes #45, 1998.
Barabasi, Albert-Laszlo. Linked: How Everything is Connected to Everything Else, and What it Means. Basic Books, 2014.
Buchanon, Mark. Nexus: Small Worlds and the Groundbreaking Science of Networks. New York: W.W. Norton and Company, 2003.
Introductory Discrete Mathematics. Dover Books on Computer Science. V. K . Balakrishnan. Dover Publications 2010.
Discrete Mathematics with Proof, Eric Gossett. Wiley 2009.
Discrete Mathematical Structures, 6th Edition. Bernard Kolman, Robert Busby, Sharon C. Ross. Prentice Hall 2008.

Learning Outcomes and Objectives

Course Objectives

  • Describe how formal tools of symbolic logic are used to model real-life situations, including those arising in computing contexts such as program correctness, database queries, and algorithms; Develop logical reasoning skills for both direct and indirect arguments.
  • Construct mathematical proofs, including proofs by induction; Relate the ideas of mathematical induction to recursion and recursively defined structures.
  • Formulate combinatorial techniques; Basics of counting
  • Investigate and solve recurrence relations by employing recursive thinking and methods; Analyze a problem to create relevant recurrence equations.
  • Examine properties of sets and mathematical relations on sets
  • Examine the algebraic structure of a Boolean algebra.
  • Diagram, examine, and analyze graphs and trees; Demonstrate different traversal methods for trees and graphs.
  • Apply the Binomial Theorem to independent events and Bayes Theorem to dependent events.
  • Examine the theory and application of discrete mathematics through projects, extended reading, or programming and computational problems.

CSLOs

  • Critique a mathematical statement for its truth value, defend choice by formulating a mathematical proof or constructing a counterexample.

  • Analyze and apply patterns of discrete mathematical structures to demonstrate mathematical thinking.

Outline

  1. Describe how formal tools of symbolic logic are used to model real-life situations, including those arising in computing contexts such as program correctness, database queries, and algorithms; Develop logical reasoning skills for both direct and indirect arguments.
    1. Discuss logic as the science of reasoning and symbolic logic as the theoretical basis of digital logic circuit design, relational database theory, automata theory, and artificial intelligence.
    2. Explain an argument as a sequence of statements that demonstrates the validity of an assertion.
    3. Recognize whether an argument is valid or not.
    4. Use the argument forms modus ponens and modus tollens correctly.
    5. Write the converse, inverse, and contrapositive of a conditional statement.
    6. Translate between formal and informal language.
    7. Examine the logic of quantified statements.
    8. Investigate applications and history such as
      1. circuit design
      2. search engines
      3. history of two-valued logic in Africa, China, Europe, etc, such as the logic of divination in Madagascar
      4. non-two valued logic, such as fuzzy logic, quantum logic, three-valued logic, etc
  2. Construct mathematical proofs, including proofs by induction; Relate the ideas of mathematical induction to recursion and recursively defined structures.
    1. Discuss the importance of proof in mathematics
      1. As a carefully reasoned argument meant to convince others that a given statement is true
      2. To promote precision and clarity in mathematical thought
      3. As justification to support methods used for solving problems
    2. Prove existential statements using constructive proofs.
    3. Disprove universal statements using counterexamples.
    4. Use logical reasoning to construct direct proofs.
    5. Compose indirect proofs using contradiction and contraposition.
    6. Verify conjectures about mathematical patterns using mathematical induction, and strong induction.
    7. Investigate the history and variety of proof techniques, such as
      1. Deductive proof
      2. Constructive vs. non-constructive proof of existence
      3. Introduction of proof by induction by Italian mathematician Francesco Maurolico in 1575
      4. Controversies related to informal proof, or proof by example and the history of such arguments, such as in ancient Egyptian and Babylonian mathematics
      5. "Visual" proof
      6. Emerging role of computers in proof, such as proof by a massive computer application, proof correctness software, and theorem proving software
  3. Formulate combinatorial techniques; Basics of counting
    1. Discuss combinatorial reasoning as a type of reasoning that produces a result by counting things that are combined in different ways.
    2. Count the elements of a list.
    3. Count possibilities with and without repetition.
    4. Count the number of arrangements of objects.
    5. Count the number of unordered selections of objects, with and without repetition.
    6. Apply the Pigeonhole Principle.
    7. The principle of inclusion/exclusion and (optional) derangements
    8. Discuss history and applications such as
      1. probability,
      2. assignment of identification numbers
      3. history of binomial coefficients, counting techniques, and the arithmetical triangle in Indian, Chinese, Islamic, Jewish, and European sources, including the work of Pascal
  4. Investigate and solve recurrence relations by employing recursive thinking and methods; Analyze a problem to create relevant recurrence equations.
    1. Discuss a recurrence relation as a formula that relates each term of a sequence to some of the previous terms.
    2. Formulate recurrence relations to model problems and to describe sequences, including arithmetic and geometric progressions.
    3. Find an explicit formula for a recursively defined sequence.
    4. (Optional) Check the correctness of an explicit formula for a recursively defined sequence using mathematical induction.
    5. (Optional) Solve counting problems with generating functions
    6. Discuss history and applications of recursion to disciplines such as computer science and programming, including Euclidean Algorithm, such as
      1. the analysis of algorithms, their complexity, and efficiency
      2. coding theory in electrical engineering
      3. database searches
      4. use of modular arithmetic and recursion in the generation of pseudorandom numbers
      5. Fibonacci, the Fibonacci numbers, and their appearance in nature
  5. Examine properties of sets and mathematical relations on sets
    1. Investigate sets and properties of sets
      1. Discuss a set as a collection of objects and abstract set theory as a foundation of mathematical thought.
      2. Understand the basic definitions, notation, and operations in set theory
      3. (Optional) Prove set-theoretic properties and use counterexamples to disprove statements about sets
      4. Use Venn diagrams as a tool to analyze sets and set operations
    2. Define and analyze the mathematics of relations
      1. Discuss a mathematical relation as a subset of the Cartesian product of two sets.
      2. Examine properties of relations including reflexivity, symmetry, and transitivity
      3. Define a mathematical function as a special type of relation
      4. Examine properties of functions
        1. One-to-one (injection)
        2. Onto (surjection)
        3. One-to-one correspondence (bijection)
        4. Inverse functions
      5. (Optional) Investigate partial order relations
      6. Investigate applications such as finite state automata, databases, the order of magnitude of functions, the flow of individual tasks in a project, or the nondenumerability of the continuum.
    3. Discuss the multicultural and historical development of number theoretic concepts such as properties of prime numbers and composite numbers, the Chinese Remainder Theorem, and uses of modular arithmetic concepts in calendar calculations in many cultures
  6. Examine the algebraic structure of a Boolean algebra.
    1. Define a Boolean Algebra
    2. Recognize the similarities between logical equivalence and set identity.
    3. Briefly discuss the role of Boolean algebra in other aspects of mathematics such as applications in circuit theory
    4. (Optional) Discuss other algebraic structures and applications, such as
      1. Partially Ordered Sets
      2. Symmetry groups and applications in coding
      3. Finite fields
      4. Switching functions: Normal forms
  7. Diagram, examine, and analyze graphs and trees; Demonstrate different traversal methods for trees and graphs.
    1. Discuss various methods of representing graphs
      1. Formal definition of a graph
      2. Representations of graphs using adjacency and/or incidence matrices
    2. Define directed and undirected, weighted and unweighted graphs.
    3. Discuss concepts such as the degree of a vertex and connectedness and graph isomorphism.
    4. Recognize different ways to traverse a graph including Euler and Hamiltonian circuits
    5. Define trees as special kinds of graphs. Examine spanning trees/forests.
    6. Use algorithms to find minimal spanning trees of weighted graphs.
    7. Discuss applications and history of graphs and trees in the areas such as
      1. artificial intelligence
      2. chemistry
      3. bioinformatics
      4. scheduling problems
      5. networking
      6. parallel processing
      7. transportation systems.
      8. De Bruijn sequences and Sanskrit rhythm cycles, and applications in DNA sequencing
      9. African sand figures
      10. the small world phenomenon and very large graphs
  8. Apply the Binomial Theorem to independent events and Bayes Theorem to dependent events.
    1. Examine definitions of probability and related concepts, including finite probability space, events, conditional probability, integer random variables, expectation, and the law of large numbers
    2. Understand the difference between independent and dependent events
    3. Use Bayes Theorem to compute conditional probability
    4. Investigate the binomial distribution and use the Binomial Theorem to compute corresponding probabilities
  9. Examine the theory and application of discrete mathematics through projects, extended reading, or programming and computational problems.
    1. Typical problem-solving topics may include any of the following:
      1. Solve challenging problems in number theory, combinatorics, and recursive

        relations
      2. Prove statements from set theory and Boolean algebra
      3. Write challenging proofs using mathematical induction and strong mathematical

        induction
    2. Typical applied projects may include any of the following:
      1. Investigate and write about topics in modular arithmetic and its applications, such

        as cryptography
      2. Investigate and write about topics in graph theory and its applications
      3. Investigate and write about topics in formal logic
      4. Construct computer program(s) implementing discrete structures and related

        algorithms
Back to Top