SF1698 Discrete Mathematics 7.5 credits

• Prime numbers, the Fundamental Theorem of Arithmetic, Euclid’s algorithm, and Diophantine equations.
• Modular arithmetic and Fermat’s theorem.
• Sets, functions, relations, infinite sets, and cardinal numbers.
• Boolean algebra and elementary logic.
• Proof by induction and recursion.
• Permutations, cycle notation, and the symmetric group.
• Combinatorics and elementary probability theory: choosing with and without replacement from different alphabets, the binomial and multinomial theorems, Stirling numbers, integer partitions.
• The pigeonhole principle, case analysis, inclusion–exclusion.
• Elementary graph theory, the Handshaking Lemma, Eulerian and Hamiltonian graphs, trees, bipartite graphs, matchings, Hall’s Marriage Theorem.

After the course the student should be able to

• use concepts. theorems and methods to solve and present solutions to problems within the parts of discrete mathematics described by the course content,
• read and comprehend mathematical text.

• TEN1 - Written exam, 7.5 credits, grading scale: A, B, C, D, E, FX, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability. The examiner may apply another examination format when re-examining individual students. If the course is discontinued, students may request to be examined during the following two academic years.

• All members of a group are responsible for the group's work.
• In any assessment, every student shall honestly disclose any help received and sources used.
• In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.