CSE 311: Foundations of Computing I
Autumn, 2015
James R. Lee
Section B: MWF 1:30-2:20, EEB 105
Office hours: MW 2:30-3:30, CSE 640
Shayan Oveis Gharan
Section A: MWF 9:30-10:20, CMU 120
Office hours: MW 10:30-11:30, CSE 636
Email and discussion:
Class email list: multi_cse311a_au15 [archives]Please send any e-mail about the course to cse311-staff@cs.
Discussion board (moderated by TBA)Use this board to discuss the content of the course. That includes everything except the solutions to current homework problems. Feel free to discuss homeworks and exams from past incarnations of the course, and any confusion over topics discussed in class. It is also acceptable to ask for clarifications about the statement of homework problems, but not about their solutions.
Textbook:
There is no required text for the course. Some lectures will have associated reading material linked below. Over the first 6 weeks or so, the following textbook can be a useful companion:Rosen, Discrete Mathematics and Its Applications, McGraw-Hill.
(The 6th or 7th editions of the text are equally useful. Used or rental copies of either edition are available for vastly less than the ridiculously high new copy prices.)
Lectures
| date | topic | slides | inked (A) | inked (B) | reading |
| 30-Sep | Propositional logic | 1.1-1.2 (7th), 1.1 (6th) | |||
| 2-Oct | Digital circuits, more logic | 1.1-1.3 (7th) 1.1-1.2 (6th) | |||
| 5-Oct | Booelan algebra, combinatorial logic | 12.1-12.3 (7th) 11.1-11.3 (6th) | |||
| 7-Oct | Boolean algebra and circuits | 12.1-12.3 (7th) 11.1-11.3 (6th) | |||
| 9-Oct | Canonical forms, predicate logic | 1.4-1.5 (7th) 1.3-1.4 (6th) | |||
| 12-Oct | Predicate logic, logical inference | 1.6-1.7 (7th) 1.5-1.7 (6th) | |||
| 14-Oct | Proofs I | 1.6-1.7 (7th) 1.5-1.7 (6th) | |||
| 16-Oct | Proofs II | N/A | N/A | 1.6-1.7 (7th) 1.5-1.7 (6th) | |
| 19-Oct | Set theory | 2.1-2.3 (6th,7th) | |||
| 21-Oct | Functions, modular arithmetic | 4.1-4.2 (7th) 3.4-3.5 (6th) | |||
| 23-Oct | Modular arithmetic and applications | 4.1-4.3 (7th) 3.4-3.6 (6th) | |||
| 26-Oct | Primes, GCD | 4.3-4.4 (7th), 3.5-3.7 (6th) | |||
| 28-Oct | Primes, GCD, fewer tangents | 4.3-4.4 (7th), 3.5-3.7 (6th) | |||
| 30-Oct | Solving modular equations | 4.4, 5.1 (7th), 3.7, 4.1 (6th) | |||
| 2-Nov | Induction | 5.1 (7th), 4.1 (6th) | |||
| 4-Nov | Strong induction and recursion | 5.2-5.3 (7th), 4.2-4.3 (6th) | |||
| 6-Nov | Strong induction and GCD analysis | 5.3 (7th), 4.3 (6th) | |||
| 9-Nov | MIDTERM exam | review slides | |||
| 11-Nov | NO CLASS: Veteran's day | ||||
| 13-Nov | Recursively defined sets and structural induction | 5.3 (7th), 4.3 (6th) | |||
| 16-Nov | Structural induction | 5.3 (7th), 4.3 (6th) | |||
| 18-Nov | Regular expressions and context-free grammars | ||||
| 20-Nov | Context-free grammars & finite state machines | ||||
| 23-Nov | Finite state machines | ||||
| 25-Nov | State minimization and NFAs | ||||
| 27-Nov | NO CLASS: Thanksgiving | ||||
| 30-Nov | NFAs, DFAs, and regular expressions | ||||
| 2-Dec | Limitations of FSMs: Irregular languages | ||||
| 4-Dec | Graphs and relations | 9.1 and pp. 594-601 (7th), 8.1 and pp. 541-548 (6th) | |||
| 7-Dec | Infinities and diagonalization | ||||
| 9-Dec | The halting problem and undecidability | ||||
| 11-Dec | Reductions and Turing machines |
| TA | Office hours | Room |
| Sam Castle | Wed, 12:00-1:00 | CSE 021 |
| Jiechen Chen | Tue, 4:00-5:00 | CSE 218 |
| Rebecca Leslie | Mon, 8:30-9:30 | CSE 218 |
| Evan McCarty | Tue, 11:30-12:30 | CSE 220 |
| Tim Oleskiw | Tue, 3:00-4:00 | CSE 218 |
| Spencer Peters | Tue, 1:00-2:00 | CSE 218 |
| Robert Weber | Wed, 3:30-4:30 | CSE 678 (except Oct 21st at CSE 110) |
| Ian Zhu | Thu, 4:30-5:30 | CSE 021 |
| Section | Day/Time | Room |
| AA Sam | Th, 830-920 | MGH 242 |
| AB Rebecca | Th, 930-1020 | MGH 234 |
| AC Robert | Th, 1030-1120 | JHN 075 |
| BA Jiechen | Th, 1230-120 | MGH 228 |
| BB Tim | Th, 130-220 | MGH 242 |
| BC Evan | Th, 230-320 | MEB 242 |
Homeworks [Grading guidelines]:
Assignments will be submitted via Gradescope. An account will be created for you.
- Homework #1, due Friday, 9-Oct.
- Homework #2, due Friday, 16-Oct.
- Homework #3, due Friday, 23-Oct.
- Homework #4, due Friday, 30-Oct.
- Homework #5, due Friday, 13-Nov.
- Homework #6, due Friday, 20-Nov.
- Homework #7, due Friday, 4-Dec.
- Homework #8, due Friday, 11-Dec.
Exams:
- Midterm exam:
In class, Monday, 9-Nov-2015
- Final exam:
EXAM PREP
Monday, 14-Dec-2015, EEB 105
Sec A: 12:30-2:20pm
Sec B: 2:30-4:20pm