Overview Overview
S
Model systems Model systems
T
Translate Translate
L
Propositional and predicate logic Propositional and predicate logic
P
Proof strategies and valid arguments Proof strategies and valid arguments
I
Recursion and Induction Recursion and Induction
M
Modular Arithmetic Modular Arithmetic
U
Use language conventions to improve arguments Use language conventions to improve arguments
N
Mathematical definitions and notation Mathematical definitions and notation

ARCHIVED Discrete Math for CS × Overview Model systems Translate Propositional and predicate logic Proof strategies and valid arguments Recursion and Induction Modular Arithmetic Use language conventions to improve arguments Mathematical definitions and notation

Overview

Modeling and Impact

Description: Understand, guide, shape impact of computing on society/the world. Connect the role of Theory CS classes to other applications (in undergraduate CS curriculum and beyond). Model problems using appropriate mathematical concepts.

Model systems: Selecting and representing appropriate data types and using notation conventions to clearly communicate choices; Connecting logical circuits and compound proposition and tracing to calcluate output values; Determining the properties of positional number representations, including overflow and bit operations; Modeling data structures, such as linked lists or trees, as recursively defined data structures; Modeling data with partitions and functions

Translating between symbolic and English versions of statements using precise mathematical language

Tracing algorithms specified in pseudocode

Representing numbers using positional representations, including decimal, binary, hexadecimal, fixed-width representations, and 2s complement

Translating between truth tables (tables of values) and compound propositions

Drawing graph representations of relations and functions e.g. Hasse diagram and partition diagram

Problem Solving

Description: Know, select and apply appropriate computing knowledge and problem-solving techniques. Reason about computation and systems. Use mathematical techniques to solve problems. Determine appropriate conceptual tools to apply to new situations. Know when tools do not apply and try different approaches. Critically analyze and evaluate candidate solutions.

Propositional and predicate logic: Evaluating compound propositions; Judging logical equivalence of compound propositions using symbolic manipulation with known equivalences, including DeMorgan's Law; Judging logical equivalence of compound propositions using truth tables; Rewriting compound propositions using normal forms; Judging whether a collection of propositions is consistent; Writing the converse, contrapositive, and inverse of a given conditional statement; Determining what evidence is required to establish that a quantified statement is true or false; Evaluating quantified statements about finite and infinite domains

Proof strategies and valid arguments

Identifying the proof strategies used in a given proof

Identifying which proof strategies are applicable to prove a given compound proposition based on its logical structure

Carrying out a given proof strategy to prove a given statement

Carrying out a universal generalization argument to prove that a universal statement is true

Tracing and/or modifying a proof by contradiction

Using proofs as knowledge discovery tools to decide whether a statement is true or false

Recursion and Induction

Using a recursive definition to evaluate a function or determine membership in a set

Using mathematical induction to prove mathematical identities, inequalities, and other invariants

Using strong induction to prove mathematical identities, inequalities, and other invariants

Using structural induction to prove statements about recursively defined objects, e.g. strings and trees

Modular Arithmetic

Using the definitions of the div and mod operators on integers

Using divisibility and primality predicates

Applying the definition of congruence modulo n and modular arithmetic

Communication

Description: Clearly and unambiguously communicate computational ideas using appropriate formalism. Translate across levels of abstraction.

Use language conventions to improve arguments: Distinguishing between tautologies, contradictions, and contingencies; Determining whether a given binary relation is symmetric, antisymmetric, reflexive, and/or transitive; Determining whether a given function is one-to-one, onto, and/or invertible; Determining whether a given binary relation is an equivalence relation and/or a partial order; Distinguishing between structural induction, mathematical induction, and strong induction; Using appropriate signpost words to improve readability of proofs, including 'arbitrary' and 'assume'

Mathematical definitions and notation

Precisely describing a set using appropriate notation e.g. roster method, set builder notation, and recursive definitions

Defining important sets of numbers, e.g. set of integers, set of rational numbers

Defining functions, predicates, and binary relations using multiple representations

Listing the truth tables of atomic boolean functions (and, or, xor, not, if, iff)

Using functions to compare cardinality of sets

Classifying sets into: finite sets, countably infinite sets, uncountable sets