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 well-ordering property (Page 335-336). |
|
9 |
3.2 3.3 |
Miniproject |
10 |
5.2: Strong induction (Page 328-333) 5.3: Recursive definitions (Page 339-346) |
|
11 |
5.3: Structural induction (Page 347-351) 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 367-369) 10.1: Graphs and graph models 10.2: Graph terminology and special types of graphs (Page 627-631 and page 639-640) 10.3: Representing graphs (Page 643-646line 23) 10.4: Connectivity (Page 652-656) |
|
14 |
10.5: Euler and Hamilton paths 10.6: Shortest path problems |
|
15 |
11.1: Introduction to trees 11.4: Page 753-755 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 - 501line 8) Solving linear recurrence relations |
|
19 |
8.3: Divide-and-conquer algorithms and recurrence relations (Example 4 is part of miniproject 4) 9.1: Relations and their properties |
|
20 |
2.6: Zero-one matrices (Page 184-186) 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 597-598) |
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.