Difference between revisions of "CS 2800 Spring 2020"

From CS2800 wiki
(Schedule)
(Schedule)
 
(47 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
This is the course website for CS 2800, Spring 2020.
 
This is the course website for CS 2800, Spring 2020.
  
* Instructor: [http://www.cs.cornell.edu/~mdgeorge Michael George].  Office hours TBD.
+
* Instructor: [http://www.cs.cornell.edu/~mdgeorge Michael George].  Office hours Wednesday 3-5 in Ward B01.
 
 
 
* Class meets Monday, Wednesday, Friday, 10:10-11:00am in Statler 185
 
* Class meets Monday, Wednesday, Friday, 10:10-11:00am in Statler 185
 
* Please read the [[syllabus]]
 
* Please read the [[syllabus]]
Line 14: Line 13:
 
   -- do not edit!
 
   -- do not edit!
 
   -->
 
   -->
 +
 +
You are responsible for learning the material in the "prep" page '''before''' the corresponding lecture.  The prep page will also contain a link to the previous semester's notes.  If you want to look ahead to lectures where I haven't yet posted the prep page, you can visit the [[CS 2800 Fall 2019]] page.
  
 
{|class="wikitable"
 
{|class="wikitable"
Line 19: Line 20:
 
  |-
 
  |-
 
  |rowspan=4| [[:Category:Set theory|Sets]] and [[:Category:Proof techniques|Proof techniques]]
 
  |rowspan=4| [[:Category:Set theory|Sets]] and [[:Category:Proof techniques|Proof techniques]]
  | 1/22  || [[SP20:Lecture 1 Introduction|Introduction]]  
+
  | 1/22  || [[SP20:Lecture 1 Introduction|Introduction]] ([[SP20:Lecture 1 prep|prep]], [[Media:sp20-lec01-slides.pdf|slides]])
 
  |-
 
  |-
  | 1/24  || [[SP20:Lecture 2 Set and function definitions|Set and function definitions]]  
+
  | 1/24  || [[SP20:Lecture 2 Set definitions|Set definitions]] ([[SP20:Lecture 2 prep|prep]], [[Media:sp20-lec02-slides.pdf|slides]])
 
  |-
 
  |-
  | 1/27  || [[SP20:Lecture 3 Set constructions|Set constructions]]  
+
  | 1/27  || [[SP20:Lecture 3 Set constructions|Set constructions]] ([[SP20:Lecture 3 prep|prep]], [[Media:sp20-lec03-slides.pdf|slides]])
 
  |-
 
  |-
  | 1/29  || [[SP20:Lecture 4 Proof techniques|Proof techniques]]  
+
  | 1/29  || [[SP20:Lecture 4 Proof techniques|Proof techniques]] ([[SP20:Lecture 4 prep|prep]], [[Media:sp20-lec04-slides.pdf|slides]])
 
  |-
 
  |-
  |rowspan=8| [[:Category:Functions|Functions]] and [[:Category:Relations|Relations]]
+
  |rowspan=7| [[:Category:Functions|Functions]] and [[:Category:Relations|Relations]]
  | 1/31  || [[SP20:Lecture 5 Function properties|Function properties]]  
+
  | 1/31  || [[SP20:Lecture 5 Functions|Functions]] ([[SP20:Lecture 5 prep|prep]], [[Media:sp20-lec05-slides.pdf|slides]])
 
  |-
 
  |-
  | 2/3  || [[SP20:Lecture 6 Injectivity and left inverses|Injectivity and left inverses]]  
+
  | 2/3  || [[SP20:Lecture 6 Quantifiers|Quantifiers]] ([[SP20:Lecture 6 prep|prep]], [[Media:sp20-lec06-slides.pdf|slides]])
 
  |-
 
  |-
  | 2/5  || [[SP20:Lecture 7 Surjectivity and Bijectivity|Surjectivity and Bijectivity]]  
+
  | 2/5  || [[SP20:Lecture 7 'Jectivity and inverse functions|'Jectivity and inverse functions]] ([[SP20:Lecture 7 prep|prep]], [[Media:sp20-lec07-slides.pdf|slides]])
 
  |-
 
  |-
  | 2/7  || [[SP20:Lecture 8 Cardinality|Cardinality]]  
+
  | 2/7  || [[SP20:Lecture 8 Cardinality|Cardinality]] ([[SP20:Lecture 8 prep|prep]], [[Media:sp20-lec08-slides.pdf|slides]])
 
  |-
 
  |-
  | 2/10  || [[SP20:Lecture 9 Diagonalization|Diagonalization]]  
+
  | 2/10  || [[SP20:Lecture 9 Diagonalization|Diagonalization]] ([[SP20:Lecture 9 prep|prep]], [[Media:sp20-lec09-slides.pdf|slides]])
 
  |-
 
  |-
  | 2/12  || [[SP20:Lecture 10 Proof techniques review|Proof techniques review]]  
+
  | 2/12  || [[SP20:Lecture 10 Relations|Relations]] ([[SP20:Lecture 10 prep|prep]], [[Media:sp20-lec10-slides.pdf|slides]])
 
  |-
 
  |-
  | 2/14  || [[SP20:Lecture 11 Relations|Relations]]  
+
  | 2/14  || [[SP20:Lecture 11 Equivalence classes|Equivalence classes]] ([[SP20:Lecture 11 prep|prep]], [[Media:sp20-lec11-slides.pdf|slides]])
 
  |-
 
  |-
  | 2/17  || [[SP20:Lecture 12 Equivalence classes|Equivalence classes]]  
+
|rowspan=3| [[:Category:Number theory|Number theory]]
 +
  | 2/17  || [[SP20:Lecture 12 Induction|Induction]] ([[SP20:Lecture 12 prep|prep]], [[Media:sp20-lec12-slides.pdf|slides]])
 
  |-
 
  |-
  |rowspan=2| [[:Category:Number theory|Number theory]]
+
  | 2/19  || [[SP20:Lecture 13 Strong induction and Euclidean division|Strong induction and Euclidean division]] ([[SP20:Lecture 13 prep|prep]], [[Media:sp20-lec13-slides.pdf|slides]])
| 2/19  || [[SP20:Lecture 13 Induction|Induction]]  
 
 
  |-
 
  |-
  | 2/21  || [[SP20:Lecture 14 Strong induction and Euclidean division|Strong induction and Euclidean division]]  
+
  | 2/21  || [[SP20:Lecture 14 Base b representation|Base b representation]] ([[SP20:Lecture 14 prep|prep]], [[Media:sp20-lec14-slides.pdf|slides]])
 
  |-
 
  |-
 
  |rowspan=1|  
 
  |rowspan=1|  
Line 53: Line 54:
 
  |-
 
  |-
 
  |rowspan=4| [[:Category:Number theory|Number theory]]
 
  |rowspan=4| [[:Category:Number theory|Number theory]]
  | 2/26  || [[SP20:Lecture 15 Base b representation|Base b representation]]  
+
  | 2/26  || [[SP20:Lecture 15 GCD algorithm|GCD algorithm]] ([[SP20:Lecture 15 prep|prep]], [[Media:sp20-lec15-slides.pdf|slides]])
 
  |-
 
  |-
  | 2/28  || [[SP20:Lecture 16 GCD algorithm|GCD algorithm]]  
+
  | 2/28  || [[SP20:Lecture 16 Bézout coefficients|Bézout coefficients]] ([[SP20:Lecture 16 prep|prep]], [[Media:sp20-lec16-slides.pdf|slides]])
 
  |-
 
  |-
  | 3/2  || [[SP20:Lecture 17 Modular numbers|Modular numbers]]  
+
  | 3/2  || [[SP20:Lecture 17 Modular numbers|Modular numbers]] ([[SP20:Lecture 17 prep|prep]], [[Media:sp20-lec17-slides.pdf|slides]])
 
  |-
 
  |-
  | 3/4  || [[SP20:Lecture 18 Modular division and exponentiation|Modular division and exponentiation]]  
+
  | 3/4  || [[SP20:Lecture 18 Modular division and exponentiation|Modular division and exponentiation]] ([[SP20:Lecture 18 prep|prep]], [[Media:sp20-lec18-slides.pdf|slides]])
 
  |-
 
  |-
 
  |rowspan=1|  
 
  |rowspan=1|  
  | 3/5  ||class="exam"| Prelim 1
+
  | 3/5  ||class="exam"| Prelim 1 ([[SP20:Prelim 1 guide|study guide]])
 
  |-
 
  |-
 
  |rowspan=3| [[:Category:Number theory|Number theory]]
 
  |rowspan=3| [[:Category:Number theory|Number theory]]
  | 3/6  || [[SP20:Lecture 19 Euler’s theorem|Euler’s theorem]]  
+
  | 3/6  || [[SP20:Lecture 19 Euler’s theorem|Euler’s theorem]] ([[SP20:Lecture 19 prep|prep]], [[Media:sp20-lec19-slides.pdf|slides]])
 
  |-
 
  |-
  | 3/9  || [[SP20:Lecture 20 Public key cryptography|Public key cryptography]]  
+
  | 3/9  || [[SP20:Lecture 20 Public key cryptography|Public key cryptography]] ([[SP20:Lecture 20 prep|prep]], [[Media:sp20-lec20-slides.pdf|slides]])
 
  |-
 
  |-
  | 3/11  || [[SP20:Lecture 21 RSA|RSA]]  
+
  | 3/11  || [[SP20:Lecture 21 RSA|RSA]] ([[SP20:Lecture 21 prep|prep]], [[Media:sp20-lec21-slides.pdf|slides]])
 
  |-
 
  |-
  |rowspan=7| [[:Category:Automata]]
+
  |rowspan=8| [[:Category:Automata]]
  | 3/13  || [[SP20:Lecture 22 Inductively defined sets|Inductively defined sets]]  
+
  | 3/13  || [[SP20:Lecture 22 Inductively defined sets|Inductively defined sets]] ([[SP20:Lecture 22 prep|prep]], [[Media:sp20-lec22-slides.pdf|slides]])
 
  |-
 
  |-
  | 3/16  || [[SP20:Lecture 23 Structural induction|Structural induction]]  
+
  | 4/|| [[SP20:Lecture 23 Structural induction|Structural induction]] ([[SP20:Lecture 23 prep|prep]], [[Media:sp20-lec23-slides.pdf|slides]])
 
  |-
 
  |-
  | 3/18  || [[SP20:Lecture 24 Deterministic Finite Automata|Deterministic Finite Automata]]  
+
  | 4/|| [[SP20:Lecture 24 Deterministic Finite Automata|Deterministic Finite Automata]] ([[SP20:Lecture 24 prep|prep]], [[Media:sp20-lec24-slides.pdf|slides]])
 
  |-
 
  |-
  | 3/20 || [[SP20:Lecture 25 Automata constructions|Automata constructions]]  
+
  | 4/10 || [[SP20:Lecture 25 Automata constructions|Automata constructions]] ([[SP20:Lecture 25 prep|prep]], [[Media:sp20-lec25-slides.pdf|slides]])
 
  |-
 
  |-
  | 3/23 || [[SP20:Lecture 26 Unrecognizable languages|Unrecognizable languages]]  
+
  | 4/13 || [[SP20:Lecture 26 Unrecognizable languages|Unrecognizable languages]] ([[SP20:Lecture 26 prep|prep]], [[Media:sp20-lec26-slides.pdf|slides]])
 
  |-
 
  |-
  | 3/25 || [[SP20:Lecture 27 Non-determinism|Non-determinism]]  
+
  | 4/15 || [[SP20:Lecture 27 Non-determinism|Non-determinism]] ([[SP20:Lecture 27 prep|prep]], [[Media:sp20-lec27-slides.pdf|slides]])
 
  |-
 
  |-
  | 3/27 || [[SP20:Lecture 28 Regular expressions|Regular expressions]]  
+
  | 4/17 || [[SP20:Lecture 28 Regular expressions|Regular expressions]] ([[SP20:Lecture 28 prep|prep]], [[Media:sp20-lec28-slides.pdf|slides]])
 
  |-
 
  |-
  |rowspan=3|  
+
  | 4/20  || [[SP20:Lecture 29 Kleene's theorem|Kleene's theorem]] ([[SP20:Lecture 29 prep|prep]], [[Media:sp20-lec29-slides.pdf|slides]])
| 3/30  ||class="break"| No class; Spring break
 
 
  |-
 
  |-
  | 4/||class="break"| No class; Spring break
+
|rowspan=3| [[:Category:Combinatorics]]
 +
  | 4/22  || [[SP20:Lecture 30 Sum and product rule|Sum and product rule]] ([[SP20:Lecture 30 prep|prep]], [[Media:sp20-lec30-slides.pdf|slides]])
 
  |-
 
  |-
  | 4/||class="break"| No class; Spring break
+
  | 4/24  || [[SP20:Lecture 31 Permutations and combinations|Permutations and combinations]] ([[SP20:Lecture 31 prep|prep]], [[Media:sp20-lec31-slides.pdf|slides]])
 
  |-
 
  |-
  |rowspan=1| [[:Category:Automata]]
+
  | 4/27  || [[SP20:Lecture 32 Combinatorial proofs|Combinatorial proofs]] ([[SP20:Lecture 32 prep|prep]], [[Media:sp20-lec32-slides.pdf|slides]])
| 4/6  || [[SP20:Lecture 29 Kleene's theorem|Kleene's theorem]]  
 
 
  |-
 
  |-
  |rowspan=1| [[:Category:Combinatorics]]
+
  |rowspan=1| [[:Category:Probability]]
  | 4/|| [[SP20:Lecture 30 Sum and product rule|Sum and product rule]]  
+
  | 4/29  || [[SP20:Lecture 33 Probability spaces|Probability spaces]] ([[SP20:Lecture 33 prep|prep]], [[Media:sp20-lec33-slides.pdf|slides]])
 
  |-
 
  |-
 
  |rowspan=1|  
 
  |rowspan=1|  
  | 4/||class="exam"| Prelim 2
+
  | 4/30  ||class="exam"| Prelim 2 ([[SP20:Prelim 2 guide|study guide]])
|-
 
|rowspan=2| [[:Category:Combinatorics]]
 
| 4/10  || [[SP20:Lecture 31 Permutations and combinations|Permutations and combinations]]
 
|-
 
| 4/13  || [[SP20:Lecture 32 Combinatorial proofs|Combinatorial proofs]]
 
|-
 
|rowspan=6| [[:Category:Probability]]
 
| 4/15  || [[SP20:Lecture 33 Probability spaces|Probability spaces]]
 
|-
 
| 4/17  || [[SP20:Lecture 34 Conditional probability|Conditional probability]]
 
|-
 
| 4/20  || [[SP20:Lecture 35 Random variables|Random variables]]
 
|-
 
| 4/22  || [[SP20:Lecture 36 Expectation|Expectation]]  
 
 
  |-
 
  |-
  | 4/24  || [[SP20:Lecture 37 Independent RVs|Independent RVs]]  
+
  |rowspan=5| [[:Category:Probability]]
 +
| 5/1  || [[SP20:Lecture 34 Conditional probability|Conditional probability]] ([[SP20:Lecture 34 prep|prep]], [[Media:sp20-lec34-slides.pdf|slides]])
 
  |-
 
  |-
  | 4/27  || [[SP20:Lecture 38 Markov's/Chebychev's/Weak law|Markov's/Chebychev's/Weak law]]  
+
  | 5/4   || [[SP20:Lecture 35 Random variables|Random variables]] ([[SP20:Lecture 35 prep|prep]], [[Media:sp20-lec35-slides.pdf|slides]])
 
  |-
 
  |-
  |rowspan=3| [[:Category:Metalogic]]
+
  | 5/6  || [[SP20:Lecture 36 Expectation|Expectation]] ([[SP20:Lecture 36 prep|prep]], [[Media:sp20-lec36-slides.pdf|slides]])
| 4/29  || [[SP20:Lecture 39 Truth tables|Truth tables]]  
 
 
  |-
 
  |-
  | 5/1   || [[SP20:Lecture 40 Proof trees|Proof trees]]  
+
  | 5/8   || [[SP20:Lecture 37 Independent RVs|Independent RVs]] ([[SP20:Lecture 37 prep|prep]], [[Media:sp20-lec37-slides.pdf|slides]])
 
  |-
 
  |-
  | 5/|| [[SP20:Lecture 41 Soundness and completeness|Soundness and completeness]]  
+
  | 5/11  || [[SP20:Lecture 38 Markov's/Chebychev's/Weak law|Markov's/Chebychev's/Weak law]] ([[SP20:Lecture 38 prep|prep]], [[Media:sp20-lec38-slides.pdf|slides]])
 
  |-
 
  |-
 
  |rowspan=1|  
 
  |rowspan=1|  
  | TBD  ||class="exam"|  
+
  | 5/22  ||class="exam"| Final exam ([[SP20:Final study guide|study guide]])
 
  |}
 
  |}
  

Latest revision as of 09:50, 15 May 2020

This is the course website for CS 2800, Spring 2020.

  • Instructor: Michael George. Office hours Wednesday 3-5 in Ward B01.
  • Class meets Monday, Wednesday, Friday, 10:10-11:00am in Statler 185
  • Please read the syllabus
  • Please enroll in Piazza for all course announcements and discussion
  • Homework is posted on Piazza
  • Be sure to frequently refer to the list of Useful pages

Schedule

You are responsible for learning the material in the "prep" page before the corresponding lecture. The prep page will also contain a link to the previous semester's notes. If you want to look ahead to lectures where I haven't yet posted the prep page, you can visit the CS 2800 Fall 2019 page.

Topic Date Lecture Topic
Sets and Proof techniques 1/22 Introduction (prep, slides)
1/24 Set definitions (prep, slides)
1/27 Set constructions (prep, slides)
1/29 Proof techniques (prep, slides)
Functions and Relations 1/31 Functions (prep, slides)
2/3 Quantifiers (prep, slides)
2/5 'Jectivity and inverse functions (prep, slides)
2/7 Cardinality (prep, slides)
2/10 Diagonalization (prep, slides)
2/12 Relations (prep, slides)
2/14 Equivalence classes (prep, slides)
Number theory 2/17 Induction (prep, slides)
2/19 Strong induction and Euclidean division (prep, slides)
2/21 Base b representation (prep, slides)
2/24 No class; February break
Number theory 2/26 GCD algorithm (prep, slides)
2/28 Bézout coefficients (prep, slides)
3/2 Modular numbers (prep, slides)
3/4 Modular division and exponentiation (prep, slides)
3/5 Prelim 1 (study guide)
Number theory 3/6 Euler’s theorem (prep, slides)
3/9 Public key cryptography (prep, slides)
3/11 RSA (prep, slides)
Category:Automata 3/13 Inductively defined sets (prep, slides)
4/6 Structural induction (prep, slides)
4/8 Deterministic Finite Automata (prep, slides)
4/10 Automata constructions (prep, slides)
4/13 Unrecognizable languages (prep, slides)
4/15 Non-determinism (prep, slides)
4/17 Regular expressions (prep, slides)
4/20 Kleene's theorem (prep, slides)
Category:Combinatorics 4/22 Sum and product rule (prep, slides)
4/24 Permutations and combinations (prep, slides)
4/27 Combinatorial proofs (prep, slides)
Category:Probability 4/29 Probability spaces (prep, slides)
4/30 Prelim 2 (study guide)
Category:Probability 5/1 Conditional probability (prep, slides)
5/4 Random variables (prep, slides)
5/6 Expectation (prep, slides)
5/8 Independent RVs (prep, slides)
5/11 Markov's/Chebychev's/Weak law (prep, slides)
5/22 Final exam (study guide)

Office hours schedule

(Click for location)