U Chicago CS Dept Logo

CSPP 50102: Discrete Mathematics for Computer Science
Summer 2012


announcements | general information | organization | homework

Announcements

Homework 10 "Do" exercises are posted

Final exam is on Tuesday September 4 from 5:30 to 8:30 pm

Please subscribe to the course mailing list: 50102 mailing list

Textbook:
Discrete Mathematics and its Applications. 7e. (McGraw-Hill) by Kenneth H. Rosen (ISBN 978-0073383095) = Rosen
Discrete Mathematics and its Applications. 6e. (McGraw-Hill, 2007) by Kenneth H. Rosen (ISBN 978-0073229720)
Both editions will be supported in this course.

The course grade will be determined using the following weights:
  (5%) Assignments
(20%) Quizzes: Wednesday July 18, Wednesday July 25, Wednesday August 22, Wednesday August 29
(25%) Midterm: Wednesday August 1
(50%) Final exam: Tuesday September 4

Schedule of lectures

June 19
Lecture 1: Logic and proof: propositional logic, quantified propositions; direct proof, proof by contraposition
5:30–8:30 pm in Ryerson 276
Reading assignment: Rosen 7e, chapter 1, sections 1.1, 1.3–1.5, 1.7–1.8.
(Rosen 6e, 1.1–1.4, 1.6–1.7)
June 20
Lecture/Discussion: proof by contradiction, proof by cases
5:30–7:15 pm in Ryerson 276
June 25 (makeup for July 3)
Lecture 2: Mathematical induction
5:30–8:30 pm in Ryerson 251
Reading assignment: Rosen 7e, chapter 5, sections 5.1–5.2.
(Rosen 6e, 4.1–4.2)
June 26
Lecture 3: Strong induction; sets and functions
5:30–8:30 pm in Ryerson 276
Reading assignment: Rosen 7e, chapter 5, sections 5.1–5.2; chapter 2, sections 2.1–2.3.
(Rosen 6e, 4.1–4.2; 2.1–2.3)
June 27
Lecture/Discussion: Cardinality of sets and countability
5:30–7:15 pm in Ryerson 276
Reading assignment: Rosen 7e, chapter 2, section 2.5
(Rosen 6e, 2.4)
July 3
No class due to Independence Day holiday
July 4
No class due to Independence Day holiday
July 6 (makeup for July 4)
Lecture/Discussion: Sequences and summations
5:30–7:15 pm in Ryerson 276
Reading assignment: Rosen 7e, chapter 2, section 2.4 (omit recurrences subsection)
(Rosen 6e, 2.4)
July 10
Lecture 4: Asymptotic notation
5:30–8:30 pm in Ryerson 276
Reading assignment: Rosen 7e, chapter 3, sections 3.1–3.3.
(Rosen 6e, 3.1–3.3; 2.3)
July 11
Lecture/Discussion: complexity of basic algorithms
5:30–7:15 pm in Ryerson 276
July 17
Lecture 5: Counting
5:30–8:30 pm in Ryerson 276
Reading assignment: Rosen 7e, chapter 6, sections 6.1–6.5.
(Rosen 6e, 5.1–5.5)
July 18
Quiz 1
Lecture/Discussion: binomial theorem, generalized permutations and combinations
5:30–7:15 pm in Ryerson 276
July 24
Lecture 6: Recurrences and methods of solving recurrences
5:30–8:30 pm in Ryerson 276
Reading assignment: Rosen 7e, chapter 2, section 2.4 (recurrences subsection); chapter 8, sections 8.1–8.3
(Rosen 6e, 7.1–7.3)
July 25
Quiz 2
Lecture/Discussion: applications of recurrences to divide and conquer algorithms
5:30–7:15 pm
July 31
Lecture 7: Graphs: special graphs; bipartite graphs; isomorphism, subgraphs
5:30–8:30 pm
Reading assignment: Rosen 7e, chapter 10, sections 10.1–10.4
(Rosen 6e, 9.1–9.4)
August 1
Midterm
5:30–7:15 pm in Ryerson 276
August 7
Lecture 8: Graphs: paths and connectedness, Eulerian and Hamiltonian graphs
5:30–8:30 pm in Ryerson 276
Reading assignment: Rosen 7e, chapter 10, sections 10.4–10.5
(Rosen 6e, 9.4–9.5)
August 8
Lecture/Discussion: trees
5:30–7:15 pm in Ryerson 276
Reading assignment: Rosen 7e, chapter 11, section 11.1
(Rosen 6e, 10.1)
August 14
Lecture 9: Probability: Probability distribution, conditional probability, independence
5:30–8:30 pm in Ryerson 276
Reading assignment: Rosen 7e, chapter 7, sections 7.1–7.3
(Rosen 6e, 6.1–6.3)
August 15
Lecture/Discussion: Bayes' theorem and applications
5:30–7:15 pm in Ryerson 276
August 21
Lecture 10: Random variables, expectation, and variance
5:30–8:30 pm in Ryerson 276
Reading assignment: Rosen 7e, chapter 7, section 7.4.
(Rosen 6e, 6.4)
August 22
Quiz 3
Lecture/Discussion: Geometric distribution; variance
5:30–7:15 pm in Ryerson 276
August 28
Lecture 11: Number theory and cryptography
5:30–8:30 pm in Ryerson 276
Reading assignment: Rosen 7e, chapter 4
(Rosen 6e, 3.4–3.7)
August 29
Quiz 4
Lecture/Discussion: Fermat's little theorem; modular exponentiation
5:30–7:15 pm in Ryerson 276
September 4
Final examination
5:30–8:30 pm in Ryerson 276

Organization

Staff

Lectures

Problem Sessions

brady at cs dot uchicago dot edu