DM549: Discrete Methods for Computer Science

Participants should learn basic techniques for working with mathematical concepts important to computer science. This is an essential prerequisite for describing, analyzing, and solving problems in computer science.

The course lays a foundation for all courses on the second semester of the computer science education.

In relation to the competence profile of the degree it is the explicit focus of the course to:

• communicate knowledge of several proof methods
• give the competence of analyzing and generalizing problems and algorithms in computer science
• give the skill of formulating ones knowledge in a clear and precise manner
• develop the skills of describing, analyzing, and solving problems in computer science using modeling formalisms from the core areas of computer science and their mathematical underpinning.

The learning objectives of the course are that the student demonstrates the ability to:

• express statements as formal logical propositions
• write statements concisely
• use various proof methods such as direct proofs, proofs by contraposition, proofs by contradiction, and proofs by induction
• use concepts, results, and techniques learned in the course for solving concrete problems that may or may not be know from the course

The following main topics are contained in the course:

• Logic
• Sets and cardinality
• Functions
• Proof techniques: direct proof, proof by contraposition, proof by contradiction, and proof by induction
• Number theory, including divisibility, primes, and congruences
• Matrices: addition, multiplication and transposing
• Relations, including various representations, closures, equivalence relations, and partial orders
• Counting techniques, including combinations, permutations, binomial coefficients

• Intro phase (lectures, class lessons) - 42 hours
• Training phase: 42 hours
• Study phase: 20 hours

• Solve assignments
• Read the assigned literature
• Practice to apply the acquired knowledge.