| 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) |