Discrete Structures Metrics
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 Hours42
SE. 1. Apply mathematical induction and other techniques to prove mathematical results.
Recognizes valid proofs that use mathematical induction and other techniques.
Given a simple problem, such as an identity, constructs a mathematical proof by induction.
Constructs mathematical proofs by induction and other techniques.
CS. 25. Examine the logical validity of arguments and proofs as they apply to Boolean expressions.
Identifies the properties and structures of Boolean algebra.
Analyzes the steps to simplify a Boolean expression.
Constructs a proof using the laws of Boolean algebra.
CS. 26. Illustrate the basic terminology and properties of graphs and trees.
Defines terms and properties for graphs and trees.
Given a problem description illustrates appropriate trees, binary search trees, weighted, directed and undirected graphs solutions.
Applies mathematical proofs to verify the properties of graphs.
CS. 27. Perform binary and hexadecimal conversions of numbers.
Converts binary numbers to their decimal equivalent.
Converts positive numbers between bases 2, 10, and 16.
Performs two-s complement to represent negative integers in binary.
CS. 28. Perform computations using recursively defined functions and structures.
Explains how a simple recursive function is evaluated.
Computes the correct result produced by a recursive algorithm.
Constructs recursive algorithms for the solution of problems.
SE. 5. Solve problems involving sets, relations, functions, and congruences.
Defines the concepts of sets, relations, functions, and congruences.
Solves problems about sets, relations, functions, and 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.
Explains standard algorithms for graphs and trees, such as Eulerian circuits, spanning trees, and Kruskal?s algorithm.
Applies traversal methods for graphs and trees.
Verifies the correctness of graph algorithms using mathematical proofs.
SE. 6. Use methods of combinatorics to solve counting problems.
Recognizes the need for combinatorial techniques such as combinations or permutations to solve a problem.
Solves counting problems using combinatorial techniques such as combinations and permutations.
Decomposes a complex problem into combinatorial procedures.