Lale Özkahyaozkahyaathacettepe.edu.tr203 +90 312 780 7551 
Week  Date  Topic  Reading (Lehman and Leighton (LL), and Victor Adamchik (VA)) and Exercises 

1  Sept 2529  Logic: propositional logic, logical equivalence, predicates & quantifiers, and logical reasoning. [slides] 
Reading: Logic Sheet,
Chapter 1 (LL), Chapter 1.11.5 (Rosen) Problems: Set 1 
2  Oct 26  Proof Techniques [slides] 
Reading: Chapter 1.61.7, 4.14.2 (Rosen),
Chapter 1 (LL) Top ten proof techniques not allowed in BBM205 (from LL) Problems: Set 2 
3  Oct 913  Method of Induction [slides] 
Reading:
(VA) 1,
2,
(
Jeff Erickson) 3
Chapter 1.61.7, 4.14.2 (Rosen), Chapter 2 (LL), Chapter 3 (LL) Reading for fun (VA): Induction ('ctd) Problems: Set 3 
4  Oct 1620  Counting: Basic Rules, Pigeonhole principle, permutations and combinations [slides] 
Reading:
Sets, Functions,
Chapter 5 (Rosen),
Chapters 14,
15,
16 (LL) Reading for fun (VA): Binomial Coefficients Problems: Set 4a, Set 4b 
5  Oct 2327  Review and the first midterm exam  
6  Oct 30Nov 3  Arithmetic Modulo m, Primes and Greatest Common Divisors [slides] 
Reading
(VA): Congruences, Divisibility:
1,
2,
3
Chapter 3.43.7 (Rosen), Chapter 4 (LL), Chapter 5 (LL) Problems: Set 5 
7  Nov 610  Recursion: Definitions, Solving recursive equations [slides] 
Reading: (VA)
1,
3,
4,
5,
Jeff Erickson's notes,
Chapter 7.17.3 (Rosen), Chapter 12 (LL),
Chapter 13 (LL)
Reading for fun: Recursion: 2 Problems: Set 6 
8  Nov 1317  Graph Terminology and Graph Isomorphism [slides] 
Reading: (VA) Graphs:
1,
2,
Chapter 9.19.3 (Rosen),
Chapter 6 (LL) Problems: Set 7 
9  Nov 2024  Connectivity, Euler and Hamilton Paths, Planar Graphs, Graph Coloring [slides] 
Reading: (VA) Graphs ('ctd):
3,
4,
Chapter 9.49.5, 9.79.8 (Rosen),
Chapter 7 (LL) Problems: Problems: Set 8 
10  Nov 27  Dec 1  Review and the second midterm exam  
11  Dec 48  Introduction to Discrete Probability
[slides] Events, Conditional Probability, Independence, Bayes' Rule [slides] 
Reading:
Two nice applications of discrete probability Chapter 6.16.2 (Rosen), Chapters 18, 19, 20 (LL) An alternative summary Problems: Set 9 
12  Dec 1115  Special Topics: Random Variables Expectation and Important Distributions 

13  Dec 1822  Special Topics: Maximum Matchings in Graphs Stable Matchings in Graphs 
Reading: (VA) Graphs ('ctd): 5 
14  Dec 2529  Special Topics: Computational Complexity 
Midterm exams  60% 
Final exam  40% 
© 2017 Hacettepe University