ChabotCollege

Course Outline for Mathematics 8, Page 1

Fall 2008

ChabotCollegeFall 2008

Course Outline for Mathematics 8

DISCRETE MATHEMATICS

Catalog Description:

8 Discrete Mathematics 4 units

Sets, relations and functions; logic, methods of proof, induction; combinatorics, recursion, recurrence relations and complexity of algorithms; graphs and trees; logic circuits; automata. Designed for majors in mathematics and computer science. Prerequisite: Mathematics 1(completed with a grade of “C” or higher).

4 hours.
[Typical contact hours: 70]

Prerequisite Skills:

Before entering the course, the student should be able to:

1.use delta notation;

2.explain limits and continuity;

3.use Newton’s method;

4.apply the definition of the derivative of a function;

5.define velocity and acceleration in terms of mathematics;

6.differentiate algebraic and trigonometric functions;

7.apply the chain rule;

8.find all maxima, minima and points of inflection on an interval;

9.sketch the graph of a differentiable function;

10.apply implicit differentiation to solve related rate problems;

11.apply the Mean Value Theorem;

12.demonstrate an understanding of the definite integral as the limit of a Riemann sum;

13.demonstrate an understanding of the Fundamental Theorem of Integral Calculus;

14.demonstrate an understanding of differentials and their applications;

15.integrate using the substitution method;

16.find the volume of a solid of revolution using the shell, disc, washer methods;

17.find the volume of a solid by slicing;

18.find the work done by a force;

19.find the hydrostatic force on a vertical plate;

20.find the center of mass of a plane region;

21.approximate a definite integral using Simpson’s Rule and the Trapezoidal Rule.

Expected Outcomes for Students:

Upon completion of the course, the student should be able to:

  1. apply principles of symbolic logic to the construction of formal proofs;
  2. prove mathematical statements using proof by contradiction, proof by contraposition and proof by cases.(Example: prove that there are infinitely many primes.);
  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;

  1. usecounting principles to measure the complexity of computer algorithms;
  2. solve recurrence relations and apply them to the analysis of recursive programs;
  3. apply concepts of graph theory to path problems (e.g.,shortest path, Euler path, Hamilton path);
  4. apply properties of trees to analysis of simple games and sorting problems;
  5. apply laws of Boolean algebra to simplifyinglogic circuits;
  6. design a finite automaton to recognize a given language.

Course Content:

  1. Symbolic logic and rules of inference
  2. Informal proof techniques: proof by cases, proof by contradiction, proof by contraposition, existence vs. constructive proofs. Applications in number theory (e.g., infinitude of primes, irrationality of )
  3. Sets, functions and relations
  4. Boolean algebra, logic circuits, Karnaugh maps
  5. Mathematical induction and it's relation to recursion, recurrence equations
  6. Big Oh notation, complexity of algorithms
  7. Counting: permutations and combinations, inclusionexclusion principle, pigeonhole principle, divide and conquer algorithms
  8. Graphs: Euler and Hamilton paths, coloring, isomorphism, representations, minimal path, planarity, connectivity
  9. Trees: traversal, minimal spanning trees, game trees
  10. Finite automata, languages

Methods of Presentation:

1.Lecture/demonstration.

2.Discussion.

Typical Assignments and Methods of Evaluating Student Progress:

  1. Typical Assignments
  2. 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? 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.
  3. Let f(x) = x2 +1, x is real on [ -2, 4]. Define a relation R on A X A as: (a, b) is in R if and only if f(a) = f(b). Show R is an equivalence relation. Describe the equivalence classes.
  1. Methods of Evaluating Student Progress
  2. Homework
  3. Quizzes
  4. Exams and final exam

Textbook(s) (Typical):

Discrete Mathematics, 6th Edition, Kenneth Rosen: McGraw-Hill Publishers, 2007

Discrete Mathematics with Applications, 3rd Edition, Suzanna Epp: Brooks/Cole Publishing Company, 2007

Special Student Materials:

A calculator may be required.

Revised 9/18/2007 J. Traugott, M. Ho