El Camino College - Division of Mathematical Sciences

Math 210
Introduction to Discrete Structures
4 units; 4 hours lecture

Catalog Description Course Objectives and Methods of Evaluation
Outline of Subject Matter Planned Instructional Activities

Grading Method: Letter

Associate Degree Credit --- Transfers to CSU and Transfers to UC

Prerequisite: Mathematics 190 with a minimum grade of C.

Catalog Description:
This course is a study of mathematical ideas and techniques to analyze problems and algorithms which occur in Computer Science. Topics covered include: logic, set algebra, functions, algorithms, the integers, mathematical induction, elementary matrix algebra, mathematical reasoning, combinatorics, recurrence relations, relations, graphs and trees.

Course Objectives and Methods of Evaluation:

  1. Course objectives (list the major objectives stated as student outcomes in behaviorally measurable terms.)
    1.  Use the standard operations and techniques of propositional logic, set algebra, functions, sequences, and series.
    2. Determine the complexity of algorithms.
    3. Use the division and Euclidean algorithms and other techniques to find the prime factorization of a given integer, to find the least common multiple and greater common divisor of a given set of integers, to rewrite a given number in another base, and to perform modular arithmetic.
    4. Prove mathematical theorems using direct proofs, indirect proofs, trivial proofs, proof by contradiction, proof by contraposition, proof by cases, and proof by mathematical induction.
    5. Disprove a statement by producing a valid counterexample.
    6. Define sequences and sets recursively.
    7. Evaluate a given algorithm that is defined recursively.
    8. Solve combinatoric problems using permutations, combinations, inclusive-exclusion, and the pigeonhole principle.
    9. Prove the binomial formula and use it to expand a given binomial and to find the coefficient of a particular term in an expansion.
    10. Model a combinatoric problem with a recurrence relation and solve it.
    11. Determine whether or not a given relation is an equivalence relation.
    12. Solve problems in graph theory that relate to graph isomorphisms, planar graphs, and Eulerian and Hamiltonian paths.
    13. Prove the standard graph theorems.
    14. Solve problems using tree traversal, spanning trees, and minimal spanning trees.
  1. Methods of Evaluation - Associate Degree Credit Course
    1. Substantial writing assignments are inappropriate for this degree applicable course because:
      1. The course primarily involves skill demonstrations or problem solving.
    2. Computational or non-computational problem-solving demonstrations, including:
      1. Exam
      2. Quizzes
      3. Homework Problems

Return to the top of the page.

Outline of Subject Matter
 

Approximate Time

Major Topic

10 hours

I. Logic; propositional equivalences; predicates and quantifiers; sets; set operations; functions; sequences and summations; and the growth of functions.

8 hours

II. Algorithms; complexity of algorithms; the integers and division; and matrices.

8 hours

III. Methods of proof, mathematical induction; and recursive definitions.

10 hours

IV.  The basics of counting; the pigeonhole principle; permutations and  combinations; and generalized permutations and combinations.

8 hours

V. Recurrence relations; solving recurrence relations; and inclusion-exclusion.
6 hours VI. Relations and their properties; representing relations; and equivalence relations.
10 hours VII. Introduction to graphs; graph terminology; representing graphs and graph isomorphism; connectivity; and Euler and Hamiltonian paths.
4 hours VIII. Introduction to trees.

  8 hours

Examinations

Total:

72 Hours

Return to the top of the page.

Planned Instructional Activities:

Lecture, discussion, individual assistance, calculator activities, and computer aided instruction

Entrance Skills and Knowledge:

List the required skills and/or knowledge without which a student would be highly unlikely to receive a grade of A, B, C, or Credit (or for Health and Safety, would endanger self or others) in the Target Course.

  1. Solve application problems at the Calculus I level.
Return to the top of the page.
 
Source of information: Course Outline of Record dated February, 1999


 Last Updated On: 4/20/06