Discrete Mathematics for Computer Scientists
Course Number: CS 184
Transcript Title: Discrete Math for CS
Created: May 7, 2014
Updated: May 8, 2014
Total Credits: 4
Lecture Hours: 40
Lecture / Lab Hours: 0
Lab Hours: 0
Satisfies Cultural Literacy requirement: No
Satisfies General Education requirement: No
Grading options: A-F (default), P-NP, audit
Introduces mathematical abstractions and reasoning used in computing, including sets, graphs, trees, functions, relations, and integers. Prerequisites: CS 161 and MTH 112.
Upon successful completion of this course, students will be able to:
- Understand basic properties of sets, bags, tuples, relations, graphs, trees, and functions.
- Construct inductive definitions for sets, grammars for languages (sets of strings), recursive definitions for functions and procedures, and closures with respect to binary properties.
- Perform traversals of graphs and trees. Construct atopological sort of a partially ordered set.
- Construct simple functions by composition of knownfunctions. Determine whether simple functions are injective,surjective, or bijective.
- Classify simple functions by rate of growth.
- Use integers in programs effectively, manipulateinteger representations (including Peano numbers and numberbases), and use modular arithmetic in programs.
Outcome Assessment Strategies
Homework, observation, class discussion, examination.
Course Activities and Design
Lecture, in-class and out-of-class assignments, discussion and examination.
Course Content (Themes, Concepts, Issues and Skills)
- Sets:basics, set operations
- Functions:one-to-one, onto, inverse, composition, graphs
- Integers:greatest common divisor, Euclidean algorithm
- Sequences and Summations
- Mathematical reasoning:Proof strategies, Mathematical Induction, Recursive definitions, Structural Induction
- Counting: basic rules, Pigeon hall principle, Permutations and combinations, Binomial coefficients and Pascal triangle.
- Relations: properties, Combining relations, Closures, Equivalence, partial ordering
- Graphs:directed, undirected graphs.