CS136 12 CATS (6 ECTS) Term 1

Availability

Core - Discrete Mathematics

Academic Aims

To introduce students to language and methods of the area of Discrete Mathematics. The focus of the module is on basic mathematical concepts in discrete mathematics and on applications of discrete mathematics in algortihms and data structures. To show students how discrete mathematics can be used in modern computer science (with the focus on algorithmic applications).

Learning Outcomes

On completion of the module the student should be able to understand:

• The fundamental concepts of discrete mathematics.
• The role of formal definitions, formal and informal mathematical proofs, and underlying algorithmic thinking, and be able to apply them in problem solving.
• The role of discrete mathematics in applications in computer science.

Content

• Foundations: logic, sets, relations, functions.
• The concept of algorithms and algorithmic thinking in problem solving
• Summation techniques: manipulations of sums and multiple sums; finite calculus
• Asymptotics and the big-Oh notation
• Manipulations with the floor and ceiling functions

Books

• Rosen KH, /Discrete Mathematics and Its Applications (6th ed)/, McGraw-Hill, 2007.
• Graham RL, Knuth DE and Patashnik O, /Concrete Mathematics (2nd ed),/ Addison-Wesley, 1994.

Assessment

Two-hour examination (80%), coursework (20%).

Teaching

30 one-hour lectures and 9 seminars