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

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

Office hours schedule

(Click for location)