CSE 311: Foundations of Computing I

Winter, 2020

Paul Beame

MWF 1:30-2:20, CSE2 G01 (Streaming online in Panopto/Canvas as of 3/9/20)
Office hours: M 2:30-4:00, WF 2:30-3:00
CSE 668 (Online as of 3/9/20)

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 pdf pdf pp.878-880 (7th) pp. 817-819 (6th)
18 Fri, Feb 21 Regular Expressions, Context-Free Grammars pdf pdf pp.851-854 (7th) and pp.790-793 (6th)
19 Mon, Feb 24 CFGs, Relations, Directed Graphs pdf pdf 9.1 and pp. 594-601 (7th), 8.1 and pp. 541-548 (6th)
20 Web, Feb 26 Finite State Machines pdf pdf
21 Fri, Feb 28 DFAs, FSMs with output pdf pdf
22 Mon, Mar 2 Minimization, NFAs pdf pdf
23 Wed, Mar 4 RegExp to NFAs, NFAs to DFAs pdf
24 Fri, Mar 6The Limitations of DFA/NFA/RegExp pdf html
25 Mon, Mar 9 Cardinality, Diagonalization, Uncomputability pdf pdf p.201 + 13.5 (7th) p.177 + 12.5 (6th)
26 Wed, Mar 11 Undecidability of the Halting Problem pdf pdf
27 Fri, Mar 13 Undecidability, Reductions, and Turing Machines pdf pdf

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
07 Feb 20 pdf pdf
08 Feb 27 pdf pdf
09 Mar 5 pdf pdf
10 Mar 12 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.
  • Homework #6, due Wednesday, February 26 2020, at 11:00 PM.
  • Homework #7, due Wednesday, March 4 2020, at 11:00 PM.
  • Homework #8, due Wednesday, March 11 2020, at 11:00 PM (Problems 1-4) and Friday, March 13, 12:00 PM (Problems 5 and 6 Extra Credit).
  • Final Homework, due Wednesday, March 18 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:
    UPDATE 3/11: There will be a comprehensive Final Homework Assignment to replace the final exam. It will be due March 18 at 11:00 p.m. and submitted in Gradescope, just like ordinary homework assignments, but it will not use grinch so that we can give partial credit. It will be worth more than a regular homework assignment and less than the midterm. The final exam will online at the officially scheduled time Monday 16-Mar-2020, 2:30-4:20 pm (possibly extending later to compensate for the online format). (The percentage associated with the final exam will be at most that of the midterm.)

    Submission will be using ordinary Gradescope like your homework assignments with solutions written on paper (in ink for legibility) and photographed and submitted just like homework, except that each question will be a separate submission so there is no confusion about tagging.

    We will also ask you to join an exam Zoom meeting with video enabled and audio off so we can monitor the class during the exam.

    (The Zoom meeting won't have flow control like office hours do, so all can join. I have been involved in several Zoom meetings with dozens of people already this week and this works well.)

    Information about the coverage of the final as well as a practice final and some other sample questions , even more sample questions are on the final exam preparation web page. Note that the sample exams may include occasional problems on topics we did not cover.

Grading Scheme (Roughly):
Because of the fact that we cannot run an in-person final exam, the percentage associated with the final exam is reduced. The following table is no longer accurate since there won't be a final exam.

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