Institut for Matematik og Datalogi Odense Universitet January 12, 1996

JFB

DM11 – F96 – Syllabus

The following is my current expectation as to what will be covered in DM11. The numbers to the left of the topics are my first rough guesses as to which lectures will be spent on those topics, and the section numbers refer to sections in the textbook.

1 — Logic and sets — sections 1.1–1.5

Introduction to course, Boolean logic, predicates, quantifiers, sets, power sets, Cartesian products, operations on sets.

2 - Functions, sequences and summations, growth of functions — sections 1.6–1.7

Includes countable and uncountable.

3-4 — Number theory — sections 2.3–2.5

Greatest common divisors, least common multiples, Euclidean algorithm, solving linear congruences, the Chinese Remainder Theorem, RSA (as an example).

5 — Mathematical proofs — sections 3.1–3.2

Includes proof by contradictions and induction (which uses the sum of a geometric progression as an example).

6 — Recursive definitions — section 3.3

At this point I will do some examples of structural induction, too, and I will at least add something to the weekly notes on it.

7-9 — Counting — sections 4.1–4.7, 5.4–5.5

Inclusion-exclusion, pigeonhole principle, permutations and combinations, binomial coefficients, probability.

10-11 — Recurrence relations — sections 5.1–5.3, Appendix 3

Linear homogeneous recurrence relations of degree k, recurrence relations of the form f(n) = af(n/b) + cn^{d}, generating functions and how to use them to solve recurrence relations.

12-13 — Relations — sections 6.1–6.6

Transitive closure (Warshall’s algorithm), equivalence relations, partial orderings. Not much is done on lattices, so I may or may not decide to mention them. Topological sorting is covered in DM02, so I will skip it.

13\frac{1}{2} – Huffman coding

I will write something brief about this.

14-15 — Algebra

This isn’t done in the textbook, so I will have to write some notes on it. It will not cover more than some group theory, getting up to the point where they learn that the size of a subgroup divides the order of the group and the fact that the integers modulo n only form a field when n is prime. There may be extra time here. If so, I will cover sections 9.1 and 9.2 on Boolean algebra.