CM1000 Discrete mathematics 8.0 credits

The course contents are divided into mandatory topics and deepening topics. The mandatory topics are all necessary for a passed grade whereas the study of deepening topics can give higher grades. Throughout the course an emphasis on sound mathematical arguments and methods of proof will be present. This means that each area of the course will be a training in sound reasoning applied to the particular subject matter of that area. For example, the study of sets will involve the study of how to prove set formulas.

The mandatory topics are:

* Elementary logic, involving basic logical connectives and the study of sound arguments and methods of proof.

* Introductory set theory, involving basic set operations.

* Functions, in particular used for the articulations of isomorphisms of graphs.

* Basic number theory (divisibility, congruences, prime numbers etc.)

* Graph theory, the isomorphism concept, trees, directed graphs, matrix representations, Eulerian circuits and paths and related properties. The usage of graphs to model properties worth reasoning about and computing possibly involving applications like finding the minimal spanning tree or the shortest path between two nodes in a weighted graph.

* Basic combinatorics including the study of the principle of multiplication, the principle of inclusion and exclusion, the binomial theorem, combinations and permutations.

The deepening topics are:

* Relations including partial orders and equivalence relations, with applications and examples from number theory including the congruence relation.

* More advanced number theory with methods of proof such as mathematical induction possibly with applications in cryptography or similar areas of interest.

* Basic discrete probability theory, event space, conditional events, and independent events.

After passing the course, the student should be able to

·     formulate basic theorems and definitions of important concepts within discrete mathematics and discuss a selections of proofs and resulting applications.

·     apply theorems and methods within discrete mathematics.

After the course it is expected that the student will have a theoretic foundation that will support further studies in software development.

Knowledge corresponding to elementary linear algebra and the calculus of one real variable.

If the course is discontinued, students may request to be examined during the following two academic years.

• RED1 - Oral examination, 3.0 credits, grading scale: P, F
• TEN1 - Written exam, 5.0 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.

Johnny Panrike

• 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.