Lecture 
New subjects 

1 
1.1: Propositional logic 1.2: Applications of propositional logic 1.3: Propositional equivalences 

2 
1.4: Predicates and quantifiers 1.5: Nested quantifiers 1.6: Rules of inference 

3 
1.8: Introduction to proof 1.9: Proof method and strategy 2.1: Sets 

4 
2.2: Set operations 2.3: Functions 2.4: Sequences and summation Appendix 2: Exponential and logarithmic functions 

5 
(Appendix 3: Pseudocode) 3.1: Algorithms 3.2: The Growth of functions 

6 
3.3: Complexity of algorithms 4.1: Divisibility and modular arithmetic 

7 
4.2: Integer representation and algorithms 4.3: Primes and greatest common divisors 

8 
5.1: Mathematical induction 5.2: Proofs using the wellordering property (Page 335336). 

9 
3.2 3.3 
Miniproject 
10 
5.2: Strong induction (Page 328333) 5.3: Recursive definitions (Page 339346) 

11 
5.3: Structural induction (Page 347351) 5.4: Recursive algorithms 

12 
(4.3: Extended Euclidean algorithm) 4.4: Chinese remainder theorem (4.5: Applications of Congruences). 
Miniproject 
13 
5.5: Loop invariants (Page 367369) 10.1: Graphs and graph models 10.2: Graph terminology and special types of graphs (Page 627631 and page 639640) 10.3: Representing graphs (Page 643646^{line 23}) 10.4: Connectivity (Page 652656) 

14 
10.5: Euler and Hamilton paths 10.6: Shortest path problems 

15 
11.1: Introduction to trees 11.4: Page 753755 11.5: Minimum spanning trees 

16 
2.5: Cardinality of sets 6.1: The basics of counting 6.2: The pigeonhole principle 6.3: Permutations and combinations 

17 
11.2: Applications of trees 11.4: Spanning trees 
Miniproject 
18 
6.4: Binomial coefficients and identities 8.1: Applications of recurrence relations 8.2: (Page 497  501^{line 8}) Solving linear recurrence relations 

19 
8.3: Divideandconquer algorithms and recurrence relations (Example 4 is part of miniproject 4) 9.1: Relations and their properties 

20 
2.6: Zeroone matrices (Page 184186) 9.3: Representing relations 9.4: Closure of relations (9.5) 

21 
4.6: Cryptography 8.3.Example 4: Karatsuba 
Miniproject 
22 
9.5: Equivalence relations 9.6 (Page 597598) 
Lecture 
Exercises 
1 
From Rosen 1.1:

2 
From Rosen 1.3:

3 
From Rosen 1.4

4 
From Rosen 1.8

5 
From Rosen 2.2

6 
From Rosen 3.2

7 
From Rosen 3.3

8 
From Rosen 4.2

9 
Miniproject 1 
10 
From Rosen 5.1:

11 
From Rosen 5.2:

12 
Miniproject 2 
13 
From Rosen 5.3:

14 
From Rosen 5.5:

15 
From Rosen 10.6:

16 
From Rosen 11.1:

17 
Miniproject 3 
18 
From Rosen 6.1:

19 
From Rosen 6.4:

20 
From Rosen 8.3:

21 
Miniproject 4 
22 
From Rosen 2.6:

From 2015 (included), the majority of the problems in the exam will be multiple choice problems. Below, you will find an example of such exam problems.