Close

Student e-mail will be down at 8 am Friday (12/19) to 5 pm Monday (12/22).

# Discrete Mathematics for Computer Scientists

## Course Description

Introduces mathematical abstractions and reasoning used in computing, including sets, graphs, trees, functions, relations, and integers.  Prerequisites: CS 161 and MTH 112.

## Intended Outcomes

Upon successful completion of this course, students will be able to:

1. Understand basic properties of sets, bags, tuples, relations, graphs, trees, and functions.
2. Construct inductive definitions for sets, grammars for languages (sets of strings), recursive definitions for functions and procedures, and closures with respect to binary properties.
3. Perform traversals of graphs and trees. Construct atopological sort of a partially ordered set.
4. Construct simple functions by composition of knownfunctions. Determine whether simple functions are injective,surjective, or bijective.
5. Classify simple functions by rate of growth.
6. 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.