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.
Developed Standard
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.

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.
Developed Standard
Analyzes the steps to simplify a Boolean expression.
Highly Developed Standard
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.
Developed Standard
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.

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

Emerging Standard
Converts binary numbers to their decimal equivalent.
Developed Standard
Converts positive numbers between bases 2, 10, and 16.
Highly Developed Standard
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.
Developed Standard
Computes the correct result produced by a recursive algorithm.
Highly Developed Standard
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.
Developed Standard
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.

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.
Developed Standard
Applies traversal methods for graphs and trees.
Highly Developed Standard
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.
Developed Standard
Solves counting problems using combinatorial techniques such as combinations and permutations.
Highly Developed Standard
Decomposes a complex problem into combinatorial procedures.