Exam curriculum
Below is a list of topics that will be covered on the final exam together with the corresponding sections of the textbook and indications of additional course notes (when a topic is not covered in the book). All textbook material that is on the exam is also covered in the PDF course notes if you do not have a copy of Aigner.
Please get in touch if there is anything you are wondering about or if you need help finding the relevant notes for a specific topic.
PART I Counting
Fundamentals and counting coefficients
Binomial coefficients, k-permutations, partitions, compositions, permutations
(Text book sections: 1.1, 1.2, 1.3, 1.4)
Generating functions
Definitions & examples solving recurrences, partial fraction decomposition, generating functions of partitions, exponential generating functions
Text book sections: 3.1, 3.2, 3.3 plus PDF notes for generating functions of partitions
Other counting methods
Inversion formulae, inclusion-exclusion, asymptotic analysis
Text book sections: 2.1, 2.3, 2.4, 5.1
PART II Graph theory
Intro to graph theory
Definitions, adjacency and incidence matrices, subgraphs, (see PDF notes), paths and circuits,
directed graphs and linear algebra
Textbook sections: 6.1, 6.2, 6.3, 6.4
Trees
Kruskal's greedy algorithm, matroids, Dijkstra's algorithm,
Textbook sections: 7.1, 7.2, 7.3, 7.4
Matchings and networks
Matching number, Hall's matching theorem, optimal matchings, Hungarian algorithm, Eulerian graphs, Hamiltonian graphs and the traveling salesman problem
Textbook sections: 8.1, 8.2, 8.4, 8.5
PART III Algebraic systems
Modular arithmetic
Congruences, finite fields, latin squares, combinatorial designs
Textbook sections: 12.1, 12.2, 12.3, 12.4
Coding
Error detection and corrections, linear codes, cyclic codes
13.3, 13.4, 13.5
(background philosophy 13.1*, 13.2*)
Cryptography
RSA and Diffie-Hellman public key cryptosystems
(elliptic curve cryptography will not appear on the exam)
Textbook sections: 14.1, 14.3 plus course notes on Diffie-Hellman key exchange from 13.05.2024