CSE 311: Foundations of Computing I

Winter, 2020

Paul Beame

MWF 1:30-2:20, CSE2 G01
Office hours: M 2:30-4:00, WF 2:30-3:00
CSE 668

Email and discussion:
email list: cse311a_wi20     [archives]

Please send any e-mail about the course to cse311-staff@cs.

We will use the Ed discussion board for this class. You will need to sign up by accepting the invitation. Use this board to discuss the content of the course. That includes everything except the solutions to current homework problems. Feel free to discuss 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. Especially over the first 6-7 weeks of the course, the following textbook can be a useful companion: Rosen, Discrete Mathematics and Its Applications, McGraw-Hill. There are many editions of this book and lots of used copies available; new copies are extremely expensive. A copy should be available on short-term loan from the Engineering Library.


Lectures

# date topic slides inked reading (Rosen)
1 Mon, Jan 6 Propositional Logic pdf pdf 1.1, 1.2 (7th) 1.1 (6th)
2 Wed, Jan 8 Logical Equivalence/Gates pdf pdf 1.1-1.3 (7th) 1.1-1.2 (6th)
3 Fri, Jan 10 Circuits/Proofs of Equivalence pdf pdf 12.1-12.3 (7th) 11.1-11.3 (6th)
4 Mon, Jan 13 Boolean Algebra/Circuits pdf pdf 12.1-12.3 (7th) 11.1-11.3 (6th)
5 Wed, Jan 15 Canonical Forms, Predicate Logic pdf pdf 1.4-1.5 (7th) 1.3-1.4 (6th)
6 Fri, Jan 17Predicate Logic, Inference pdf pdf 1.6-1.7 (7th) 1.5-1.7 (6th)
Mon, Jan 20Martin Luther King Day NO CLASS
7 Wed, Jan 22 Logical Inference and Proofs pdf pdf 1.6-1.7 (7th) 1.5-1.7 (6th)
8 Fri, Jan 24 Predicate Logic Proofs pdf pdf 1.6-1.7 (7th) 1.5-1.7 (6th)
9 Mon, Jan 27 Set Theory pdf pdf 2.1-2.3 (6th, 7th)
10 Wed, Jan 29 Modular Arithmetic pdf pdf 4.1-4.2 (7th) 3.4-3.5 (6th)
11 Fri, Jan 31 Applications of Mod, Number Theory, Factoring pdf pdf 4.1-4.3 (7th) 3.4-3.6 (6th)
12 Mon, Feb 3 GCD, Euclid's Algorithm, Modular Equations pdf pdf 4.3-4.4 (7th), 3.5-3.7 (6th)
5:20-8:25 of this video
13 Wed, Feb 5 Induction pdf pdf 5.1 (7th), 4.1 (6th)
14 Fri, Feb 7 Induction and Strong Induction pdf pdf 5.1 (7th), 4.1 (6th)
15 Mon, Feb 10 Strong Induction and Recursion pdf pdf 5.2-5.3 (7th), 4.2-4.3 (6th)
16 Wed, Feb 12 Recursively Defined Sets & Structural Induction pdf pdf 5.3 (7th), 4.3 (6th)
Fri, Feb 14 MIDTERM exam
Mon, Feb 17President's Day NO CLASS
17 Wed, Feb 19 Structural Induction, Regular Expressions pp.878-880 (7th) pp. 817-819 (6th)
18 Fri, Feb 21 Context-Free Grammars pp.851-854 (7th) and pp.790-793 (6th)
19 Mon, Feb 24 Relations, Directed Graphs 9.1 and pp. 594-601 (7th), 8.1 and pp. 541-548 (6th)
20 Web, Feb 26 Finite State Machines
21 Fri, Feb 28 Finite State Machines
22 Mon, Mar 2 FSMs with Output
23 Wed, Mar 4 Minimization, NFAs
24 Fri, Mar 6NFAs, RegExp, NFAs to DFAs
25 Mon, Mar 9 The Limitations of DFA/NFA/RegExp
26 Wed, Mar 11 Cardinality, Uncomputability p.201 + 13.5 (7th) p.177 + 12.5 (6th)
27 Fri, Mar 13 Undecidability of theHalting Problem
28 Fri, Jun 1 Undecidability, Reductions, and Turing Machines

TA Office hours Room
Siddharth Iyer Tuesdays 3:30-4:20 CSE2 151
Suraj Jagadeesh Tuesdays 1:00-1:50 CSE 220
Karishma Mandyam Wednesdays 10:30-11:20 CSE2 152
Josh Shin Mondays 12:30-1:20 CSE2 153
Tuesday, Jan 21 12:00-12:50 CSE 220
Betty Sun Fridays 3:30-4:20 CSE 220
Jason Waataja Mondays 4:00-4:50 CSE2 153
Tuesday, Jan 21 10:30-11:20 CSE 220

Section Day/Time Room
AA Siddharth Iyer Th 11:30-12:20 DEN 213
AB Jason Waataja/Betty Sun Th 12:30-1:20 LOW 220
AC Suraj Jagadeesh Th 1:30-2:20 LOW 101
AD Karishma Mandyam/Josh Shin Th 2:30-3:20 LOW 101

Section Materials Date Problems Solns
01 Jan 9 pdf pdf
02 Jan 16 pdf pdf
03 Jan 23 pdf pdf
04 Jan 30 pdf pdf
05 Feb 6 pdf pdf
06 Feb 13 pdf pdf

Homework [Grading guidelines, Submission instructions]:

  • Homework #1, due Wednesday, January 15 2020, at 11:00 PM.
  • Homework #2, due Wednesday, January 22 2020, at 11:00 PM.
  • Homework #3, due Wednesday, January 29 2020, at 11:00 PM.
  • Homework #4, due Wednesday, February 5 2020, at 11:00 PM.
  • Homework #5, due Wednesday, February 12 2020, at 11:00 PM.

Exams:

  • Midterm exam:
    In class, Friday 14-Feb-2020,

    The midterm will cover everything up to the end of ordinary induction (but not strong induction). It will be closed book and closed notes. However, you will get lists of inference and equivalence rules with the exam.

    To get an idea of the content and length of the exam, take a look at the following material

    There will be a review session on Thursday, Feb 13th 5:00-6:30 p.m. in Sieg 134.

     

  • Final exam:
    The final exam will at the officially scheduled time Monday 16-Mar-2020, 2:30-4:20 pm.

Grading Scheme (Roughly):

Homework 50%
Midterm 15-20%
Final Exam 30-35%