Difference between revisions of "CS 2800 Spring 2020"

From CS2800 wiki
(Schedule)
(Schedule)
Line 19: Line 19:
 
  |-
 
  |-
 
  |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]] ([[SP20:Lecture 1 prep|prep]], [[Media:sp20-lec01-slides.pdf|slides]])
+
  | 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]] ([[SP20:Lecture 2 prep|prep]], [[Media:sp20-lec02-slides.pdf|slides]])
+
  | 1/24  || [[SP20:Lecture 2 Set and function definitions|Set and function definitions]] ([[SP20:Lecture 2 prep|prep]], [[Media:sp20-lec02-slides.pdf|slides]])
 
  |-
 
  |-
  | 1/27  || [[SP20:Lecture 3 Set constructions|Set constructions]]  ([[SP20:Lecture 3 prep|prep]])
+
  | 1/27  || Set constructions ([[SP20:Lecture 3 prep|prep]])
 
  |-
 
  |-
  | 1/29  || [[SP20:Lecture 4 Proof techniques|Proof techniques]]  ([[SP20:Lecture 4 prep|prep]])
+
  | 1/29  || Proof techniques ([[SP20:Lecture 4 prep|prep]])
 
  |-
 
  |-
 
  |rowspan=8| [[:Category:Functions|Functions]] and [[:Category:Relations|Relations]]
 
  |rowspan=8| [[:Category:Functions|Functions]] and [[:Category:Relations|Relations]]
  | 1/31  || [[SP20:Lecture 5 Function properties|Function properties]]  ([[SP20:Lecture 5 prep|prep]])
+
  | 1/31  || Function properties ([[SP20:Lecture 5 prep|prep]])
 
  |-
 
  |-
  | 2/3  || [[SP20:Lecture 6 Injectivity and left inverses|Injectivity and left inverses]]  ([[SP20:Lecture 6 prep|prep]])
+
  | 2/3  || Injectivity and left inverses ([[SP20:Lecture 6 prep|prep]])
 
  |-
 
  |-
  | 2/5  || [[SP20:Lecture 7 Surjectivity and Bijectivity|Surjectivity and Bijectivity]]  ([[SP20:Lecture 7 prep|prep]])
+
  | 2/5  || Surjectivity and Bijectivity ([[SP20:Lecture 7 prep|prep]])
 
  |-
 
  |-
  | 2/7  || [[SP20:Lecture 8 Cardinality|Cardinality]]  ([[SP20:Lecture 8 prep|prep]])
+
  | 2/7  || Cardinality ([[SP20:Lecture 8 prep|prep]])
 
  |-
 
  |-
  | 2/10  || [[SP20:Lecture 9 Diagonalization|Diagonalization]]  ([[SP20:Lecture 9 prep|prep]])
+
  | 2/10  || Diagonalization ([[SP20:Lecture 9 prep|prep]])
 
  |-
 
  |-
  | 2/12  || [[SP20:Lecture 10 Proof techniques review|Proof techniques review]]  ([[SP20:Lecture 10 prep|prep]])
+
  | 2/12  || Proof techniques review ([[SP20:Lecture 10 prep|prep]])
 
  |-
 
  |-
  | 2/14  || [[SP20:Lecture 11 Relations|Relations]]  ([[SP20:Lecture 11 prep|prep]])
+
  | 2/14  || Relations ([[SP20:Lecture 11 prep|prep]])
 
  |-
 
  |-
  | 2/17  || [[SP20:Lecture 12 Equivalence classes|Equivalence classes]]  ([[SP20:Lecture 12 prep|prep]])
+
  | 2/17  || Equivalence classes ([[SP20:Lecture 12 prep|prep]])
 
  |-
 
  |-
 
  |rowspan=2| [[:Category:Number theory|Number theory]]
 
  |rowspan=2| [[:Category:Number theory|Number theory]]
  | 2/19  || [[SP20:Lecture 13 Induction|Induction]]  ([[SP20:Lecture 13 prep|prep]])
+
  | 2/19  || Induction ([[SP20:Lecture 13 prep|prep]])
 
  |-
 
  |-
  | 2/21  || [[SP20:Lecture 14 Strong induction and Euclidean division|Strong induction and Euclidean division]]  ([[SP20:Lecture 14 prep|prep]])
+
  | 2/21  || Strong induction and Euclidean division ([[SP20:Lecture 14 prep|prep]])
 
  |-
 
  |-
 
  |rowspan=1|  
 
  |rowspan=1|  
Line 53: Line 53:
 
  |-
 
  |-
 
  |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]]  ([[SP20:Lecture 15 prep|prep]])
+
  | 2/26  || Base b representation ([[SP20:Lecture 15 prep|prep]])
 
  |-
 
  |-
  | 2/28  || [[SP20:Lecture 16 GCD algorithm|GCD algorithm]]  ([[SP20:Lecture 16 prep|prep]])
+
  | 2/28  || GCD algorithm ([[SP20:Lecture 16 prep|prep]])
 
  |-
 
  |-
  | 3/2  || [[SP20:Lecture 17 Modular numbers|Modular numbers]]  ([[SP20:Lecture 17 prep|prep]])
+
  | 3/2  || Modular numbers ([[SP20:Lecture 17 prep|prep]])
 
  |-
 
  |-
  | 3/4  || [[SP20:Lecture 18 Modular division and exponentiation|Modular division and exponentiation]]  ([[SP20:Lecture 18 prep|prep]])
+
  | 3/4  || Modular division and exponentiation ([[SP20:Lecture 18 prep|prep]])
 
  |-
 
  |-
 
  |rowspan=1|  
 
  |rowspan=1|  
Line 65: Line 65:
 
  |-
 
  |-
 
  |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]]  ([[SP20:Lecture 19 prep|prep]])
+
  | 3/6  || Euler’s theorem ([[SP20:Lecture 19 prep|prep]])
 
  |-
 
  |-
  | 3/9  || [[SP20:Lecture 20 Public key cryptography|Public key cryptography]]  ([[SP20:Lecture 20 prep|prep]])
+
  | 3/9  || Public key cryptography ([[SP20:Lecture 20 prep|prep]])
 
  |-
 
  |-
  | 3/11  || [[SP20:Lecture 21 RSA|RSA]]  ([[SP20:Lecture 21 prep|prep]])
+
  | 3/11  || RSA ([[SP20:Lecture 21 prep|prep]])
 
  |-
 
  |-
 
  |rowspan=7| [[:Category:Automata]]
 
  |rowspan=7| [[:Category:Automata]]
  | 3/13  || [[SP20:Lecture 22 Inductively defined sets|Inductively defined sets]]  ([[SP20:Lecture 22 prep|prep]])
+
  | 3/13  || Inductively defined sets ([[SP20:Lecture 22 prep|prep]])
 
  |-
 
  |-
  | 3/16  || [[SP20:Lecture 23 Structural induction|Structural induction]]  ([[SP20:Lecture 23 prep|prep]])
+
  | 3/16  || Structural induction ([[SP20:Lecture 23 prep|prep]])
 
  |-
 
  |-
  | 3/18  || [[SP20:Lecture 24 Deterministic Finite Automata|Deterministic Finite Automata]]  ([[SP20:Lecture 24 prep|prep]])
+
  | 3/18  || Deterministic Finite Automata ([[SP20:Lecture 24 prep|prep]])
 
  |-
 
  |-
  | 3/20  || [[SP20:Lecture 25 Automata constructions|Automata constructions]]  ([[SP20:Lecture 25 prep|prep]])
+
  | 3/20  || Automata constructions ([[SP20:Lecture 25 prep|prep]])
 
  |-
 
  |-
  | 3/23  || [[SP20:Lecture 26 Unrecognizable languages|Unrecognizable languages]]  ([[SP20:Lecture 26 prep|prep]])
+
  | 3/23  || Unrecognizable languages ([[SP20:Lecture 26 prep|prep]])
 
  |-
 
  |-
  | 3/25  || [[SP20:Lecture 27 Non-determinism|Non-determinism]]  ([[SP20:Lecture 27 prep|prep]])
+
  | 3/25  || Non-determinism ([[SP20:Lecture 27 prep|prep]])
 
  |-
 
  |-
  | 3/27  || [[SP20:Lecture 28 Regular expressions|Regular expressions]]  ([[SP20:Lecture 28 prep|prep]])
+
  | 3/27  || Regular expressions ([[SP20:Lecture 28 prep|prep]])
 
  |-
 
  |-
 
  |rowspan=3|  
 
  |rowspan=3|  
Line 94: Line 94:
 
  |-
 
  |-
 
  |rowspan=1| [[:Category:Automata]]
 
  |rowspan=1| [[:Category:Automata]]
  | 4/6  || [[SP20:Lecture 29 Kleene's theorem|Kleene's theorem]]  ([[SP20:Lecture 29 prep|prep]])
+
  | 4/6  || Kleene's theorem ([[SP20:Lecture 29 prep|prep]])
 
  |-
 
  |-
 
  |rowspan=1| [[:Category:Combinatorics]]
 
  |rowspan=1| [[:Category:Combinatorics]]
  | 4/8  || [[SP20:Lecture 30 Sum and product rule|Sum and product rule]]  ([[SP20:Lecture 30 prep|prep]])
+
  | 4/8  || Sum and product rule ([[SP20:Lecture 30 prep|prep]])
 
  |-
 
  |-
 
  |rowspan=1|  
 
  |rowspan=1|  
Line 103: Line 103:
 
  |-
 
  |-
 
  |rowspan=2| [[:Category:Combinatorics]]
 
  |rowspan=2| [[:Category:Combinatorics]]
  | 4/10  || [[SP20:Lecture 31 Permutations and combinations|Permutations and combinations]]  ([[SP20:Lecture 31 prep|prep]])
+
  | 4/10  || Permutations and combinations ([[SP20:Lecture 31 prep|prep]])
 
  |-
 
  |-
  | 4/13  || [[SP20:Lecture 32 Combinatorial proofs|Combinatorial proofs]]  ([[SP20:Lecture 32 prep|prep]])
+
  | 4/13  || Combinatorial proofs ([[SP20:Lecture 32 prep|prep]])
 
  |-
 
  |-
 
  |rowspan=6| [[:Category:Probability]]
 
  |rowspan=6| [[:Category:Probability]]
  | 4/15  || [[SP20:Lecture 33 Probability spaces|Probability spaces]]  ([[SP20:Lecture 33 prep|prep]])
+
  | 4/15  || Probability spaces ([[SP20:Lecture 33 prep|prep]])
 
  |-
 
  |-
  | 4/17  || [[SP20:Lecture 34 Conditional probability|Conditional probability]]  ([[SP20:Lecture 34 prep|prep]])
+
  | 4/17  || Conditional probability ([[SP20:Lecture 34 prep|prep]])
 
  |-
 
  |-
  | 4/20  || [[SP20:Lecture 35 Random variables|Random variables]]  ([[SP20:Lecture 35 prep|prep]])
+
  | 4/20  || Random variables ([[SP20:Lecture 35 prep|prep]])
 
  |-
 
  |-
  | 4/22  || [[SP20:Lecture 36 Expectation|Expectation]]  ([[SP20:Lecture 36 prep|prep]])
+
  | 4/22  || Expectation ([[SP20:Lecture 36 prep|prep]])
 
  |-
 
  |-
  | 4/24  || [[SP20:Lecture 37 Independent RVs|Independent RVs]]  ([[SP20:Lecture 37 prep|prep]])
+
  | 4/24  || Independent RVs ([[SP20:Lecture 37 prep|prep]])
 
  |-
 
  |-
  | 4/27  || [[SP20:Lecture 38 Markov's/Chebychev's/Weak law|Markov's/Chebychev's/Weak law]]  ([[SP20:Lecture 38 prep|prep]])
+
  | 4/27  || Markov's/Chebychev's/Weak law ([[SP20:Lecture 38 prep|prep]])
 
  |-
 
  |-
 
  |rowspan=3| [[:Category:Metalogic]]
 
  |rowspan=3| [[:Category:Metalogic]]
  | 4/29  || [[SP20:Lecture 39 Truth tables|Truth tables]]  ([[SP20:Lecture 39 prep|prep]])
+
  | 4/29  || Truth tables ([[SP20:Lecture 39 prep|prep]])
 
  |-
 
  |-
  | 5/1  || [[SP20:Lecture 40 Proof trees|Proof trees]]  ([[SP20:Lecture 40 prep|prep]])
+
  | 5/1  || Proof trees ([[SP20:Lecture 40 prep|prep]])
 
  |-
 
  |-
  | 5/4  || [[SP20:Lecture 41 Soundness and completeness|Soundness and completeness]]  ([[SP20:Lecture 41 prep|prep]])
+
  | 5/4  || Soundness and completeness ([[SP20:Lecture 41 prep|prep]])
 
  |-
 
  |-
 
  |rowspan=1|  
 
  |rowspan=1|  

Revision as of 13:33, 24 January 2020

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

  • 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

Topic Date Lecture Topic
Sets and Proof techniques 1/22 Introduction (prep, slides)
1/24 Set and function definitions (prep, slides)
1/27 Set constructions (prep)
1/29 Proof techniques (prep)
Functions and Relations 1/31 Function properties (prep)
2/3 Injectivity and left inverses (prep)
2/5 Surjectivity and Bijectivity (prep)
2/7 Cardinality (prep)
2/10 Diagonalization (prep)
2/12 Proof techniques review (prep)
2/14 Relations (prep)
2/17 Equivalence classes (prep)
Number theory 2/19 Induction (prep)
2/21 Strong induction and Euclidean division (prep)
2/24 No class; February break
Number theory 2/26 Base b representation (prep)
2/28 GCD algorithm (prep)
3/2 Modular numbers (prep)
3/4 Modular division and exponentiation (prep)
3/5 Prelim 1
Number theory 3/6 Euler’s theorem (prep)
3/9 Public key cryptography (prep)
3/11 RSA (prep)
Category:Automata 3/13 Inductively defined sets (prep)
3/16 Structural induction (prep)
3/18 Deterministic Finite Automata (prep)
3/20 Automata constructions (prep)
3/23 Unrecognizable languages (prep)
3/25 Non-determinism (prep)
3/27 Regular expressions (prep)
3/30 No class; Spring break
4/1 No class; Spring break
4/3 No class; Spring break
Category:Automata 4/6 Kleene's theorem (prep)
Category:Combinatorics 4/8 Sum and product rule (prep)
4/9 Prelim 2
Category:Combinatorics 4/10 Permutations and combinations (prep)
4/13 Combinatorial proofs (prep)
Category:Probability 4/15 Probability spaces (prep)
4/17 Conditional probability (prep)
4/20 Random variables (prep)
4/22 Expectation (prep)
4/24 Independent RVs (prep)
4/27 Markov's/Chebychev's/Weak law (prep)
Category:Metalogic 4/29 Truth tables (prep)
5/1 Proof trees (prep)
5/4 Soundness and completeness (prep)
TBD Final exam

Office hours schedule

(Click for location)