![[Rice University]](http://staff.rice.edu/images/staff/branding/shield.jpg)
|
|
COMP 280: The Mathematics of Computation |
This course provides an introduction to the use of mathematics in modeling and reasoning about problems in computer science. The course will focus on ideas and techniques that are widely used in Computer Science, and will present these ideas in action. Emphasis will be given in linking the material of the course with applications. The class will cover logic, proof methods (including mathematical and structural induction), reasoning about recursive and iterative programs, sets, functions and their asymptotic growth, counting, and modular arithmetic.
Class administration information
| Assignment due | Date | Topic | Reading | |||
|---|---|---|---|---|---|---|
| T | 6 | Jan | Introduction | |||
| Logic — a language for reasoning and modeling | ||||||
| Propositional Logic: A formal vocabulary | Rosen 1.1-1.2 | See corresponding sections of Intro to Logic. | ||||
| Th | 8 | |||||
| T | 13 | Propositional Logic: Reasoning with truth tables and equivalences | ||||
| 1 (sol'n) | Th | 15 | Propositional Logic: Reasoning with inference rules | Rosen 1.5 beginning | ||
| T | 20 | |||||
| 2 (sol'n) | Th | 22 | First-order Logic: Motivation and vocabulary | Rosen 1.3-1.4, 8.1 | ||
| T | 27 | |||||
| 3 (sol'n) | Th | 29 | First-order Logic: Reasoning | Rosen 1.5 ending; see also 1.6-1.7 | ||
| T | 3 | Feb | ||||
| Th | 5 | |||||
| Sets, Relations, and Functions — a language for data | ||||||
| Sets | Rosen 2.1-2.2 | |||||
| 4 (sol'n) | T | 10 | ||||
| Functions | Rosen 2.3 | |||||
| 5 (sol'n) | Th | 12 | ||||
| T | 17 | Cardinality & Computability | Rosen 2.4 ending, 3.1 ending, 12.5 ending | |||
| 6 (sol'n) | Th | 19 | ||||
| Relations & Graphs | Rosen 8.1, 8.3, 8.4 beginning, 8.5, 8.6 beginning, 9.1-9.3 | |||||
| T | 24 | Reasoning about data and programs | ||||
| Induction | Rosen 4.1-4.3 | |||||
| Exam 1 (sol'n) | Th | 26 | ||||
| T | 3 | Mar | Midterm Recess | |||
| Th | 5 | |||||
| T | 10 | Induction | Rosen 4.1-4.3 | |||
| 7 (sol'n) | Th | 12 | ||||
| T | 17 | Program proofs | Rosen 4.5 | |||
| 8 (sol'n) | Th | 19 | ||||
| T | 24 | Arithmetic | ||||
| Algorithm complexity | Rosen 3.1-3.3 | |||||
| Summations | Rosen 2.4 | |||||
| 9 (sol'n) | Th | 26 | Recurrences | Rosen 7.1-7.3 | ||
| T | 31 | Apr | ||||
| Th | 2 | Spring Recess | ||||
| T | 7 | Counting | Rosen 5.1-5.4,7.5-7.6 | |||
| 10 (sol'n) | Th | 9 | ||||
| Modular arithmetic & encryption | Rosen 3.4-3.7 | |||||
| T | 14 | |||||
| Th | 16 | |||||
| 11 (sol'n) | Fr | 17 | ||||
| Exam 2 (sol'n) | W | 29 | ||||