Difference between revisions of "CS 2800 Spring 2020"

From CS2800 wiki
(Schedule)
(Schedule)
Line 72: Line 72:
 
  | 3/11  || [[SP20:Lecture 21 RSA|RSA]] ([[SP20:Lecture 21 prep|prep]], [[Media:sp20-lec21-slides.pdf|slides]])
 
  | 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]] ([[SP20:Lecture 22 prep|prep]], [[Media:sp20-lec22-slides.pdf|slides]])
 
  | 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]] ([[SP20:Lecture 23 prep|prep]], [[Media:sp20-lec23-slides.pdf|slides]])
+
  | 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]] ([[SP20:Lecture 24 prep|prep]], [[Media:sp20-lec24-slides.pdf|slides]])
+
  | 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]] ([[SP20:Lecture 25 prep|prep]], [[Media:sp20-lec25-slides.pdf|slides]])
+
  | 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]] ([[SP20:Lecture 26 prep|prep]], [[Media:sp20-lec26-slides.pdf|slides]])
+
  | 4/13 || Unrecognizable languages ([[SP20:Lecture 26 prep|prep]])
 
  |-
 
  |-
  | 3/25 || [[SP20:Lecture 27 Non-determinism|Non-determinism]] ([[SP20:Lecture 27 prep|prep]], [[Media:sp20-lec27-slides.pdf|slides]])
+
  | 4/15 || Non-determinism ([[SP20:Lecture 27 prep|prep]])
 
  |-
 
  |-
  | 3/27 || [[SP20:Lecture 28 Regular expressions|Regular expressions]] ([[SP20:Lecture 28 prep|prep]], [[Media:sp20-lec28-slides.pdf|slides]])
+
  | 4/17 || Regular expressions ([[SP20:Lecture 28 prep|prep]])
 
  |-
 
  |-
  |rowspan=3|
+
  | 4/20 || Kleene's theorem ([[SP20:Lecture 29 prep|prep]])
| 3/30 ||class="break"| No class; Spring break
 
 
  |-
 
  |-
  | 4/||class="break"| No class; Spring break
+
|rowspan=3| [[:Category:Combinatorics]]
 +
  | 4/22  || Sum and product rule ([[SP20:Lecture 30 prep|prep]])
 
  |-
 
  |-
  | 4/||class="break"| No class; Spring break
+
  | 4/24  || Permutations and combinations ([[SP20:Lecture 31 prep|prep]])
 
  |-
 
  |-
|rowspan=1| [[:Category:Automata]]
+
  | 4/27  || Combinatorial proofs ([[SP20:Lecture 32 prep|prep]])
  | 4/6  || [[SP20:Lecture 29 Kleene's theorem|Kleene's theorem]] ([[SP20:Lecture 29 prep|prep]], [[Media:sp20-lec29-slides.pdf|slides]])
 
 
  |-
 
  |-
  |rowspan=1| [[:Category:Combinatorics]]
+
  |rowspan=1| [[:Category:Probability]]
  | 4/8  || [[SP20:Lecture 30 Sum and product rule|Sum and product rule]] ([[SP20:Lecture 30 prep|prep]], [[Media:sp20-lec30-slides.pdf|slides]])
+
  | 4/29  || Probability spaces ([[SP20:Lecture 33 prep|prep]])
 
  |-
 
  |-
 
  |rowspan=1|  
 
  |rowspan=1|  
  | 4/||class="exam"| Prelim 2
+
  | 4/30  ||class="exam"| Prelim 2
 
  |-
 
  |-
  |rowspan=2| [[:Category:Combinatorics]]
+
  |rowspan=5| [[:Category:Probability]]
  | 4/10  || [[SP20:Lecture 31 Permutations and combinations|Permutations and combinations]] ([[SP20:Lecture 31 prep|prep]], [[Media:sp20-lec31-slides.pdf|slides]])
+
  | 5/|| Conditional probability ([[SP20:Lecture 34 prep|prep]])
 
  |-
 
  |-
  | 4/13  || Combinatorial proofs ([[SP20:Lecture 32 prep|prep]])
+
  | 5/4   || Random variables ([[SP20:Lecture 35 prep|prep]])
 
  |-
 
  |-
  |rowspan=6| [[:Category:Probability]]
+
  | 5/6   || Expectation ([[SP20:Lecture 36 prep|prep]])
| 4/15  || Probability spaces ([[SP20:Lecture 33 prep|prep]])
 
 
  |-
 
  |-
  | 4/17  || Conditional probability ([[SP20:Lecture 34 prep|prep]])
+
  | 5/|| Independent RVs ([[SP20:Lecture 37 prep|prep]])
 
  |-
 
  |-
  | 4/20  || Random variables ([[SP20:Lecture 35 prep|prep]])
+
  | 5/11 || Markov's/Chebychev's/Weak law ([[SP20:Lecture 38 prep|prep]])
|-
 
| 4/22  || Expectation ([[SP20:Lecture 36 prep|prep]])
 
|-
 
| 4/24  || Independent RVs ([[SP20:Lecture 37 prep|prep]])
 
|-
 
| 4/27 || Markov's/Chebychev's/Weak law ([[SP20:Lecture 38 prep|prep]])
 
|-
 
|rowspan=3| [[:Category:Metalogic]]
 
| 4/29  || Truth tables ([[SP20:Lecture 39 prep|prep]])
 
|-
 
| 5/1  || Proof trees ([[SP20:Lecture 40 prep|prep]])
 
|-
 
| 5/4  || Soundness and completeness ([[SP20:Lecture 41 prep|prep]])
 
 
  |-
 
  |-
 
  |rowspan=1|  
 
  |rowspan=1|  
  | 5/15 ||class="exam"| 2:00 Final exam
+
  | 5/22 ||class="exam"| 2:00 Final exam
 
  |}
 
  |}
  

Revision as of 08:44, 10 April 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)
4/15 Non-determinism (prep)
4/17 Regular expressions (prep)
4/20 Kleene's theorem (prep)
Category:Combinatorics 4/22 Sum and product rule (prep)
4/24 Permutations and combinations (prep)
4/27 Combinatorial proofs (prep)
Category:Probability 4/29 Probability spaces (prep)
4/30 Prelim 2
Category:Probability 5/1 Conditional probability (prep)
5/4 Random variables (prep)
5/6 Expectation (prep)
5/8 Independent RVs (prep)
5/11 Markov's/Chebychev's/Weak law (prep)
5/22 2:00 Final exam

Office hours schedule

(Click for location)