CMSC 56: Discrete Mathematical Structures 1
Course Description
Principles of logic, set theory, relations and functions; Boolean algebra; matrices
Course Learning Outcomes
After completion of the course, the student should be able to:
- Understand definitions and proofs, including quantifiers and induction
- Understand basic set theory and set-theoretic notation
- Manipulate commonly used functions like exponentials and logarithms
- Solve counting problems
- Solve asymptotic notation problems
- Solve recurrences
Course Outline
UNIT 1. The Foundations Principles of Logic
- Logic
- Propositional Equivalences
- Predicates and Quantifiers
- Nested Quantifiers
- Rules of Inference
- Introduction to Proofs
- Proof Methods and Strategy
UNIT 2. Basic Structures: Sets, Functions, and Summations
- Set Notation and Relations
- Basic Set Operations
- Cartesian Products and Power Sets
- Summation Notation and Generalizations
UNIT 3. The Fundamentals: Algorithms, the Integers, and Matrices
- Algorithms
- The Growth of Functions
- Complexity of Algorithms
- Integers and Division/li>
- Integers and Algorithms
UNIT 4. Induction and Recursion
- Mathematical Induction
- Recursive Definitions and Structural Induction
- Recursive Algorithms
- Program Correctness
UNIT 5. Relations
- Relations and their Properties
- n-ary Relations and their Applications
- Representing Relations
- Closures of Relations
- Equivalence of Relations
- Partial Orderings
UNIT 6. Matrices
- Properties
- Operations
- Applications