CSE 311: Foundations of Computing I
Spring, 2015
Instructor: James R. Lee
Office hours: MW 2:30-3:30pm, CSE 640
MWF 1:30-2:20pm, MLR 301
Email and discussion:
Class email list: cse311a_sp15 [archives]Please send any e-mail about the course to cse311-staff@cs.
Discussion board (moderated by Gunnar and Ian2)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 | slides (inked) | reading |
| 30-Mar | Propositional logic | 1.1-1.2 (7th), 1.1 (6th) | ||
| 1-Apr | Digital circuits, more logic | 1.1-1.3 (7th) 1.1-1.2 (6th) | ||
| 3-Apr | Booelan algebra, combinatorial logic | 12.1-12.3 (7th) 11.1-11.3 (6th) | ||
| 6-Apr | Boolean algebra and circuits | 12.1-12.3 (7th) 11.1-11.3 (6th) | ||
| 8-Apr | Canonical forms, predicate logic | 1.4-1.5 (7th) 1.3-1.4 (6th) | ||
| 10-Apr | Predicate logic, logical inference | 1.6-1.7 (7th) 1.5-1.7 (6th) | ||
| 13-Apr | Proofs I | 1.6-1.7 (7th) 1.5-1.7 (6th) | ||
| 15-Apr | Proofs II | 1.6-1.7 (7th) 1.5-1.7 (6th) | ||
| 17-Apr | Set theory | 2.1-2.3 (6th,7th) | ||
| 20-Apr | Functions, modular arithmetic | 4.1-4.2 (7th) 3.4-3.5 (6th) | ||
| 22-Apr | Modular arithmetic and applications | 4.1-4.3 (7th) 3.4-3.6 (6th) | ||
| 22-Apr | Proof review session | [optional] | ||
| 24-Apr | Primes, GCD | 4.3-4.4 (7th), 3.5-3.7 (6th) [optional] Sections 1-2 here on hashing/pattern matching. |
||
| 27-Apr | Primes, GCD, fewer tangents | 4.3-4.4 (7th), 3.5-3.7 (6th) | ||
| 29-Apr | Solving modular equations | 4.4, 5.1 (7th), 3.7, 4.1 (6th) | ||
| 1-May | Induction | 5.1 (7th), 4.1 (6th) | ||
| 4-May | Strong induction and recursion | 5.2-5.3 (7th), 4.2-4.3 (6th) | ||
| 6-May | Strong induction and GCD analysis | 5.3 (7th), 4.3 (6th) | ||
| 8-May | MIDTERM exam | |||
| 11-May | Recursively defined sets and structural induction | 5.3 (7th), 4.3 (6th) | ||
| 13-May | Structural induction | 5.3 (7th), 4.3 (6th) | ||
| 15-May | Regular expressions and context-free grammars | |||
| 18-May | Context-free grammars & finite state machines | |||
| 20-May | Finite state machines | |||
| 22-May | State minimization and NFAs | |||
| 25-May | Memorial day | |||
| 27-May | NFAs, DFAs, and regular expressions | |||
| 29-May | Limitations of FSMs: Irregular languages | |||
| 1-Jun | Graphs and relations | 9.1 and pp. 594-601 (7th), 8.1 and pp. 541-548 (6th) | ||
| 3-Jun | Inifinities and diagonalization | |||
| 5-Jun | The halting problem and undecidability | |||
| 6-Jun | Final exam review session |
| TA | Office hours | Room |
| Evan McCarty | Thu, 3-4pm | CSE 021 |
| Mert Saglam | Tue, 11-12pm | CSE 021 |
| Krista Holden | Thu, 10:30-11:30am | CSE 220 |
| Gunnar Onarheim | Tue, 3-4pm | CSE 021 |
| Ian Turner | Wed, 12-1pm | CSE 218 |
| Junhao (Ian) Zhu | Thu 4-5pm | CSE 021 |
| Section | Day/Time | Room |
| AA Evan | Th, 1230-120 | THO 234 |
| AB Mert | Th, 130-220 | DEN 217 |
| AC Ian | Th, 230-320 | MGH 254 |
| AD Krista | Th, 1130-1220 | MGH 251 |
Homeworks [Grading guidelines]:
Assignments will be submitted via Gradescope. An account will be created for you.
- Homework #1, due Friday 10-Apr before class.
- Homework #2, due Friday 17-Apr before class.
- Homework #3, due Friday 24-Apr before class.
- Homework #4, due Friday 1-May before class.
- Homework #5, due Friday 15-May before class.
- Homework #6, due Friday 22-May before class.
- Homework #7, due Friday 29-May before class.
- Homework #8, due Friday 5-Jun before class.
Exams:
- Midterm exam:
In class, 8-May-2015
- Final exam:
EXAM PREP
8-Jun-2015, 2:30-4:20pm
MLR 301 (the usual room)