Datalogiens Matematiske Grundlag

Teacher: Leif Kjær Jørgensen

Textbook:  Kenneth Rosen, Discrete Mathematics and its Applications, 5th edition, McGraw-Hill 2003.
You can buy this book in the university bookshop on December 2.


Schedule  (details will be added later):

Thursday, December 2,  11.15-16.00
Lecture:  Sections 1.1, 1.2, 1.3, and 1.4 in Rosens book. This is an introduction to logic.
Exercises in section 1.1: 1, 3, 4, 10, 13, 23
Exercises in section 1.2: 1, 5, 7, 9, 17, 41

Friday, December 3, 8.30-13.45
Lecture: Sections 1.5, 2.1, and 2.2. Some examples of mathematical proof and algorithms. Big-O notation - a way to say fast functions are growing.
Exercises in section 1.3: 1, 5, 13, 19, 33
Exercises in section 1.4: 1, 3, 27, 33, 37, 45
Exercises in section 1.1: 40

Monday, December 6, 8.30-13.45
Lecture: Sections  2.3, 2.4, 2.5.  Complexity of algorithms and integers.
Exercises in section 1.5:  1, 5, 9, 13, 33, 69
Exercises in section 2.1:  33, 53, 57
Exercises in section 2.2:  3, 5, 9, 15, 19

Tuesday, December 7, 8.30-13.45
Lecture: Sections 2.6, 3.1, 3.2.  Public key cryptography, the Halting problem, sequences and sums.
Exercises in section 2.3:  7, 9, 26, 27
Exercises in section 2.4:  9, 11, 17, 29, 37, 51
Exercises in section 2.5:  1, 3, 19, 21

Wednesday, December 8, 8.30-13.45
Lecture:  Sections 3.3, 3.4.  Induction proofs and recursion.
Exercises in section 2.6:  1 (a-d), 3, 7, 19, 27, 46, 47
Exercises in section 3.1:  49, 51
Exercises in section 3.2:  1, 13, 23, 41, 42, 43

Thursday, December 9, 8.30-13.45
Lecture: Sections 3.6, 4.1, 4.2, 4.3.  Loop invariants and  counting.
Exercises in section 3.3:  3, 7, 9, 39, 51, 76
Exercises in section 3.4:  1, 7, 13, 32, 34, 35, 43, 51,

Friday, December 10, 8.30-13.45
Lecture: Sections 4.4, 6.1, 6.3.  Binomial coefficients,  recurrence relations and divide-and-conquer.
Exercises in section 3.6:  7, 8
Exercises in section 4.1:  1, 10, 11, 19, 32, 33
Exercises in section 4.2:  3, 5, 12, 40
Exercises in section 4.3:  1, 3, 11, 17, 27

Monday, December 13, 8.30-13.45
Lecture:  Sections 8.1, 8.2, 8.3 (except Isomorphism of Graphs), 8.4 (except Paths and Isomorphism and Counting paths...), 8.5.  A introduction to graphs. Eulerian and Hamiltonian graphs.
Exercises in section 4.4:  1, 3, 9, 12
Exercises in section 6.1:  1, 3, 9, 17
Exercises in section 6.3:  1, 3, 8

Tuesday, December 14, 8.30-13.45
Lecture: Sections 8.5, 8.6, 9.1. Eulerian graphs, shortest paths, trees.
Exercises in section 8.1:  3-9, 11
Exercises in section 8.2:  3, 5, 19, 20, 21
Exercises in section 8.3:  1, 5, 11
Exercises in section 8.4:  1, 3, 4, 5,
Exercises in section 8.5:  1, 9, 13, 30, 31, 32

Wednesday, December 15, 8.30-13.45
Lecture: Sections 9.2, 9.4, 9.5. Decision trees, spanning tree, minimum weigth spanning trees.
Exercises in section 8.5:  7
Exercises in section 8.6:  1, 3, 17, 21, 23
Exercises in section 9.1:  1, 3, 21, 45

Thursday, December 16, 8.30-13.45
Lecture: Sections 11.1, 11.3, 11.4. Languages and recognition of languages.
Exercises in section 9.4:  7, 15, 16 (with graph from exercise 15)
Exercises in section 9.5:  1, 3, 7, 19, 32

Friday, December 17, 8.30-13.45
Lecture:  "Understanding the Complxity of Algorithms" in Section 2.3. A short introduction to P and NP.
Exercises in section 11.1:  1, 3, 13
Exercises in section 11.3:  9, 10, 13, 17, 22
Exercises in section 11.4:  1, 3