Foothill CollegeApproved Course Outlines

Physical Sciences, Mathematics & Engineering Division
MATH 22DISCRETE MATHEMATICSSummer 2013
5 hours lecture.5 Units

Total Quarter Learning Hours: 60 (Total of All Lecture, Lecture/Lab, and Lab hours X 12)
 
 Lecture Hours: 5 Lab Hours: Lecture/Lab:
 Note: If Lab hours are specified, see item 10. Lab Content below.

Repeatability -
Statement: Not Repeatable.

Status -
 Course Status: ActiveGrading: Letter Grade with P/NP option
 Degree Status: ApplicableCredit Status: Credit
 Degree or Certificate Requirement: AS Degree,   Foothill GE
 GE Status: Communication & Analytical Thinking

Articulation Office Information -
 Transferability: BothValidation: 11/14/12


Cross Listed as:C S 18
Related ID:

1. Description -
Discrete mathematics: set theory, logic, Boolean algebra, methods of proof, mathematical induction, number theory, discrete probability, combinatorics, functions, relations, recursion, algorithm efficiencies, graphs, trees.
Prerequisite: C S 1A; satisfactory score on the mathematics placement test or MATH 48C.
Co-requisite: None
Advisory: Demonstrated proficiency in English by placement into ENGL 1A as determined by score on the English placement test or through an equivalent placement process; not open to students with credit in CIS 18 or C S 18.

2. Course Objectives -
The student will be able to:
  1. Use formal logic in constructing valid arguments.
  2. Write proofs formally.
  3. Use number theory to solve to solve problems.
  4. Understand the basics of naive set 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.
  8. Analyze and write algorithms.
  9. Identify relations and their properties.
  10. Draw and analyze graphs and trees.
  11. Solve Application problems from Computer Science
  12. Discuss mathematical problems and write solutions in accurate mathematical language and notation.
  13. Interpret mathematical solutions.
3. Special Facilities and/or Equipment -
  1. Scientific calculator
  2. When taught hybrid: Four lecture hours per week in face-to-face contact and one hour per week using CCC Confer. Students need internet access.

4. Course Content (Body of knowledge) -
  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
  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, Baye's 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 Logarithm
    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
    3. Matrix Representation of Graphs
    4. Isomorphisms of Graphs
    5. Spanning Trees
    6. Traversal Problems
  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 logic in AND-, OR- and NOT-GATES
    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
  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.
5. Repeatability - Moved to header area.
 
6. Methods of Evaluation -
  1. Written homework
  2. Quizzes, tests
  3. Proctored comprehensive final examination
7. Representative Text(s) -
Epp, Susanna S. Discrete Mathematics with Applications. 4th ed. Brooks/Cole, 2010.

8. Disciplines -
Mathematics
 
9. Method of Instruction -
  1. Lecture
  2. Discussion
  3. Cooperative learning exercises
 
10. Lab Content -
Not applicable.
 
11. Honors Description - No longer used. Integrated into main description section.
 
12. Types and/or Examples of Required Reading, Writing and Outside of Class Assignments -
  1. Homework Problems: 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. Lecture: 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. Projects: 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 both inside and/or outside of class.
13. Need/Justification -
This course is a required core course for the A.S. degrees in Mathematics and Computer Science, and satisfies the Foothill GE requirement for Area V, Communications and Analytical Thinking.


Course status: Active
Last updated: 2014-03-21 20:25:18


Foothill CollegeApproved Course Outlines