Applications of Discrete Structures

In addition to coverage of topics listed, this course will focus on developing problem solving skills explicitly. Development of skills, use of tools, and content coverage should be considered distinct and complementary goals in the course, with the content and tools serving as vehicles for skill development. The course devotes significant time to solving problems in-class with students via proofs and unambiguous pseudocode, with the goal of building problem solving and logical argument skill building.

Logic & Reasoning

Propositional Logic – Reiteration
Predicates and Qualifiers
Proofs
Inference
Induction
Recursion – Reiteration

Fundamental Discrete Structures

Sets – Reiteration
Set Operations – Reiteration
Functions
Assertions
Loop invariants

Computational Complexity

Matrices
Sequences and Series
Best / Average / Worst Case
Asymptotic Complexity
Big-O Notation – Reiteration
Empirical Measurement – Reiteration
Time-Space Tradeoff

Numbers & Counting

Pigeonhole Principle
Permutations and Combinations
Binomial Coefficients
Generalized Permutations and Combinations

Number Theory, Sets, & Probability

Modular Arithmetic
Number Systems
Properties
Representation
Discrete Probability
Probability Theory

Graphs

Models
Types
Representation
Isomorphism
Connectivity
Euler and Hamiltonian Paths