## Discrete Structures Metrics

### Description

The course covers mathematical topics essential for work in computer science. Topics include: number bases, mathematical induction, sets, relations, functions, congruence, recursion, combinations and permutations, probability, graphs, trees, logic, Boolean algebra, and proof techniques. Computing related problems and examples are integrated throughout the course.

### Minimum Contact Hours

42### Assessment Rubric

#### SE. 1. Apply mathematical induction and other techniques to prove mathematical results.

Emerging Standard

Recognizes valid proofs that use mathematical induction and other techniques.

Recognizes valid proofs that use mathematical induction and other techniques.

Developed Standard

Given a simple problem, such as an identity, constructs a mathematical proof by induction.

Given a simple problem, such as an identity, constructs a mathematical proof by induction.

Highly Developed Standard

Constructs mathematical proofs by induction and other techniques.

Constructs mathematical proofs by induction and other techniques.

#### CS. 25. Examine the logical validity of arguments and proofs as they apply to Boolean expressions.

Emerging Standard

Identifies the properties and structures of Boolean algebra.

Identifies the properties and structures of Boolean algebra.

Developed Standard

Analyzes the steps to simplify a Boolean expression.

Analyzes the steps to simplify a Boolean expression.

Highly Developed Standard

Constructs a proof using the laws of Boolean algebra.

Constructs a proof using the laws of Boolean algebra.

#### CS. 26. Illustrate the basic terminology and properties of graphs and trees.

Emerging Standard

Defines terms and properties for graphs and trees.

Defines terms and properties for graphs and trees.

Developed Standard

Given a problem description illustrates appropriate trees, binary search trees, weighted, directed and undirected graphs solutions.

Given a problem description illustrates appropriate trees, binary search trees, weighted, directed and undirected graphs solutions.

Highly Developed Standard

Applies mathematical proofs to verify the properties of graphs.

Applies mathematical proofs to verify the properties of graphs.

#### CS. 27. Perform binary and hexadecimal conversions of numbers.

Emerging Standard

Converts binary numbers to their decimal equivalent.

Converts binary numbers to their decimal equivalent.

Developed Standard

Converts positive numbers between bases 2, 10, and 16.

Converts positive numbers between bases 2, 10, and 16.

Highly Developed Standard

Performs two-s complement to represent negative integers in binary.

Performs two-s complement to represent negative integers in binary.

#### CS. 28. Perform computations using recursively defined functions and structures.

Emerging Standard

Explains how a simple recursive function is evaluated.

Explains how a simple recursive function is evaluated.

Developed Standard

Computes the correct result produced by a recursive algorithm.

Computes the correct result produced by a recursive algorithm.

Highly Developed Standard

Constructs recursive algorithms for the solution of problems.

Constructs recursive algorithms for the solution of problems.

#### SE. 5. Solve problems involving sets, relations, functions, and congruences.

Emerging Standard

Defines the concepts of sets, relations, functions, and congruences.

Defines the concepts of sets, relations, functions, and congruences.

Developed Standard

Solves problems about sets, relations, functions, and congruences.

Solves problems about sets, relations, functions, and congruences.

Highly Developed Standard

Evaluates a problem and constructs an appropriate solution choosing among sets, relations, functions, and/or congruences.

Evaluates a problem and constructs an appropriate solution choosing among sets, relations, functions, and/or congruences.

#### CS. 32. Use graphs and trees to solve problems algorithmically.

Emerging Standard

Explains standard algorithms for graphs and trees, such as Eulerian circuits, spanning trees, and Kruskal?s algorithm.

Explains standard algorithms for graphs and trees, such as Eulerian circuits, spanning trees, and Kruskal?s algorithm.

Developed Standard

Applies traversal methods for graphs and trees.

Applies traversal methods for graphs and trees.

Highly Developed Standard

Verifies the correctness of graph algorithms using mathematical proofs.

Verifies the correctness of graph algorithms using mathematical proofs.

#### SE. 6. Use methods of combinatorics to solve counting problems.

Emerging Standard

Recognizes the need for combinatorial techniques such as combinations or permutations to solve a problem.

Recognizes the need for combinatorial techniques such as combinations or permutations to solve a problem.

Developed Standard

Solves counting problems using combinatorial techniques such as combinations and permutations.

Solves counting problems using combinatorial techniques such as combinations and permutations.

Highly Developed Standard

Decomposes a complex problem into combinatorial procedures.

Decomposes a complex problem into combinatorial procedures.