CMPS 300 Discrete Structures
Course Description

Computer Science Department
California State University, Bakersfield
V1, 6/3/2003

Catalog Description:

Elementary logic and set theory, functions and relations, induction and recursion, elementary algorithm analysis, counting techniques, and introduction to computability.

Prerequisite:

CMPS 223

Units:

5

Coordinator:

Larry Taylor

Goals/Objectives:
  • To provide the student with a basis in mathematical logic
  • To provide an introduction to functions, relations, and sets
  • To provide an introduction to techniques of proof
  • To provide reinforcement for understanding of recursion

Current Text(s):

??? Rosen. Discrete Mathematics and its Applications (5th edition)

Topics:
  • (DS2) Statement and predicate logic including: truth tables, normal forms, equivalences including de Morgan's rules and equivalents to implication, multiple quantifiers and negation of predicates
  • (DS1) Functions (1-1, onto, inverses and composition), relations (reflexive, transitive, symmetric, equivalence), and sets (Venn diagrams, elementary operations, product and power sets)
  • (DS3) Techniques of proof (direct, indirect, contradiction, mathematical induction, pigeonhole principle, recursively defined functions
  • (AL2,AL3) Development of recursive algorithms ( divide-and-conquer, search, sort, fast multiplication, knapsack, etc.)
  • (DS4) Counting arguments (sum, product, permutations and combinations), theoretical lower bounds
  • (DS6) Discrete proability (finite sample spaces)
  • (AL5) Turing machines
  • (AL6) NP-Completeness (P and NP, examples of NP-complete problems)

ACM Sub Areas or Units Covered:
(DS1) Functions, relations and sets 0.6 (required .6)
(DS2) Basic logic 1.0 (required 1.0)
(DS3) Proof techniques 1.2 (required 1.2 total .9 in their course)
(DS4) Basics of Counting 0.5 (.5 required)
(DS6) Discrete Probability 0.6 (.6 required)
(AL2) Algorithmic Strategies 0.2 (not required here)
(AL3) Fundamental computing algorithms 0.2 (not required here)
(AL5) Basic Computability 0.6 (.6 but not here)
(AL6) The complexity classes P and NP 0.1 (not required at all)
DS: Discrete Structures    AL: Algorithms and Complexity   
Laboratory:

 The laboratory session will parallel the lectures, providing students with the opportunity to develop algorithms and problem-solving skills
Oral and Written Communication:
Assigned work requires written documentation.
Social and Ethical Issues:
Problem Analysis:
Solution Design:
Emphasis on recursive algorithms
Version & Date:
Version 1, 6/3/2003
Comments:
The first draft based on ACM curricula 2001 in the format of ABET sample course description.