Chabot College

Course Outline for Mathematics 8, Page 1

Fall 2004

Chabot CollegeFall 2004

Course Outline for Mathematics 8

DISCRETE MATHEMATICS

Catalog Description:

8 Discrete Mathematics 3 units

Counting techniques, sets and logic, Boolean algebra, analysis of algorithms, graph theory, trees, combinatorics, recurrence relations, introduction to automata. Designed for majors in mathematics and computer science. Prerequisite: Mathematics 1 (completed with a grade of C or higher). 3 hours.

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 propositional logic to the construction of formal proofs;
  2. apply mathematical induction to problems in sequences, series, and algorithms;
  3. measure complexity and efficiency of a variety of computer algorithms;
  4. apply concepts of combinatorics to analysis of recursive algorithms;
  5. apply concepts of graph theory to shortest path problems;
  6. solve recurrence relations and apply them to sorting and searching algorithms;
  7. apply properties of trees to analysis of simple games and sorting problems;
  8. apply laws of Boolean algebra to simplification of combinatorial circuits;
  9. design finite machines and automata.

Course Content:

1.Rules of inference, sets, sequences, functions, relations, recurrence equations

2.Boolean algebra, logic circuits, Karnaugh maps

3.Mathematical induction, Big Oh notation, complexity of algorithms

4.Counting: permutations and combinations, inclusionexclusion principle, divide and conquer algorithms

5.Graphs: Euler and Hamilton paths, coloring, isomorphism, representations, minimal path, planarity, connectivity

6.Trees: traversal, minimal spanning trees, game trees

7.Finite state machines, 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, Kenneth Rosen, McGraw-Hill Publishers, 2003

Discrete Mathematics, James A Anderson, Prentice Hall, 2001

Special Student Materials:

A calculator may be required.

CB:al

Revised: 10/03/03