CS 182: Detailed Syllabus
The course plans to follow the syllabus outlined below. Changes and adjustments may be made during the semester.
Introduction, Logic, and Proofs
- Introduction and course organization (Rosen 1.1, 1.2)
- Propositional equivalences (Rosen 1.3)
- Predicates and quantifies (Rosen 1.4, 1.5)
- Rules and inference (Rosen 1.6)
- Proof methods (Rosen 1.7, 1.8)
Algorithms, and Complexity, Induction, Recursion
- Algorithms and growth (Rosen 3.1)
- Algorithms and growth (Rosen 3.2)
- Complexity (Rosen 3.3)
- Induction (Rosen 5.1, 5.2)
- Recursion (Rosen 5.3, 5.4)
Sums, Counting, and Advanced Counting
- Sequences and summations (Rosen 2.4)
- Counting (Rosen 6.1, 6.2)
- Permuatations and combinations (Rosen 6.3,6.4)
- Advanced counting (Rosen 8.1)
- Divide and conquer (Rosen 8.3)
Graphs, and Trees
- Graphs and graph models, graph terminology, special types of graphs, representing graphs (Rosen 10.1,10.2, 10.3)
- Connectivity, and Shortest-path problems ( Rosen 10.4, 10.6)
- Introduction to trees, applications of trees, and tree traversal (Rosen 11.1, 11.2, 11.3)
- Spanning trees and minimum spanning trees (Rosen 11.4, 11.5)
Sets, Functions, Sequences, and Discrete Probability
- Sets (Rosen 2.1, 2.2)
- Functions ( Rosen 2.3)
- Relations (Rosen 9.1, 9.2, 9.3, 9.4, 9.5)
- Discrete probability (Rosen 7.1, 7.2)
- Expected value and variance (Rosen 7.4)
Number theory, and Boolean Algebra
- Divisibility and modular arithmetic, Integer representations (Rosen 4.1, 4.2)
- Primes and GCD ( Rosen 4.3, 4.4)
- Boolean Functions (Rosen 12.1, 12.2)
- Logic gates (Rosen 12.3)
Modeling Computation, and Finite State Machines
- Languages and grammers (Rosen 13.1)
- Finite state machines ( Rosen 13.2, 13.3)
- Language recognition (Rosen 13.4)
- Turing machines (Rosen 13.5)