Cpre 310 Public Web
Site - Russell
Course Outline and Syllabus
- 1. The Foundations: Logic, Sets, and Functions
- 1.1 Logic
- 1.2 Propositional Equivalences
- 1.3 Predicates and Quantifiers
- 1.4 Sets
- 1.5 Set Operations
- EXAM #1
- 1.6 Functions
- 1.7 Sequences and Summations
- 1.8 The Growth Functions
- 2. The Fundamentals: Algorithms, the Integers, and
Matrices
- 2.1 Algorithms
- 2.2 Complexity of Algorithms
- 2.3 The Integers and Division
- 2.4 Integers and Algorithms
- 2.5 Applications of Number Theory
- 2.6 Matrices
- EXAM #2
- 3. Mathematical Reasoning
- 3.1 Methods of Proof
- 3.2 Mathematical Induction
- 3.3 Recursive Definitions
- 3.4 Recursive Algorithms
- 3.5 Program Correctness
- 4. Counting
- 4.1 The Basics of Counting
- 4.2 The Pigeonhole Principle
- 4.3 Permutations and Combinations
- 4.4 Discrete Probability
- 4.5 Probability Theory
- 4.6 Generalized Permutations and Combinations
- 4.7 Generating Permutations and Combinations
- 5. Advanced Counting Techniques
- 5.1 Recurrence Relations
- 5.2 Solving Recurrence Relations
- 5.3 Divide-and-Conquer Relations
- 5.4 Generating Functions
- 5.5 Inclusion-Exclusion
- 5.6 Applications of Inclusion-Exclusion
- 6. Relations
- 6.1 Relations and Their Properties
- 6.2 n-ary Relations and Their Applications
- 6.3 Representing Relations
- 6.4 Closures of Relations
- 6.5 Equivalence Relations
- 6.6 Partial Orderings
- 7. Graphs
- 7.1 Introduction to Graphs
- 7.2 Graph Terminology
- 7.3 Representing Graphs and Graph Isomorphism
- 7.4 Connectivity
- 7.5 Euler and Hamilton Paths
- 7.6 Shortest Path Problems
- 7.7 Planar Graphs
- 7.8 Graph Coloring
- 8. Trees
- 8.1 Introduction to Trees
- 8.2 Applications of Trees
- 8.3 Tree Traversal
- 8.4 Trees and Sorting
- 8.5 Spanning Trees
- 8.6 Minimum Spanning Trees
- 9. Boolean Algebra
- 9.1 Boolean Functions
- 9.2 Representing Boolean Functions
- 9.3 Logic Gates
- 9.4 Minimization of Circuits
- 10. Modeling Computation
- 10.1 Languages and Grammars
- 10.2 Finite-State Machines with Output
- 10.3 Finite-State Machines with No Output
- 10.4 Language Recognition
- 10.5 Turing Machines