# Discrete Structures

## Course Description

Introduces mathematical abstractions and reasoning used in computing, including sets, graphs, trees, functions, relations, and integers.  Prerequisite: CS 160. Audit available.

## Intended Outcomes

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

1. Use sets, bags, tuples, relations, graphs, trees, and functions to model problems.
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 a topological sort of a partially ordered set.
4. Construct simple functions by composition of known functions. Determine whether simple functions are injective, surjective, or bijective.
5. Classify simple functions by rate of growth.
6. Use integers in programs effectively, manipulate integer representations (including Peano numbers and number bases), 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.