CS130 Mathematics for Computer Scientists I

CS130 15 CATS (7.5 ECTS) Term 1

Availability

Core - CS and CSBS. Option - CSE

To provide students with sufficient mathematical knowledge to enable them to understand the foundations of their subject for both study purposes and later career development.
To bridge the gap in style and content between A-level and university mathematics and to introduce students to the language and methods of professional mathematics.

By the end of the module the students should be able to:

Understand and use basic mathematical terminology.
Understand the role of formal definitions and proofs and be able to apply them in problem solving.
Understand the basics of propositional and predicate logic.
Understand the basics of elementary set theory.
Understand the basics of mathematical relations and functions.
Understand the basics of graph theory.
Understand the basics of probability.

The axiomatic method: Basic concepts, axioms, definitions, theorems, finite and infinte sets, natural numbers, induction.
Logic: Statements, truth values, Boolean operators, laws of propositional logic, predicates, quantifiers, laws of predicate logic.
Sets: Connection between sets and predicates, operations on sets, laws of set operations.
Relations: Relation composition and inverse, properties of relations, equivalence relations, equivalence classes, quotient sets, partial orders.
Functions: Properties of functions, equinumerous sets, countable and uncountable sets.
Graphs: Graph isomorphism, graph connectivity, Eulerian and Hamiltonian graphs.
Probability: Definitions, conditional probability, Bayes' theorem, expectation, variance, standard deviation.

Ross KA and Wright CRB, Discrete Mathematics (5th ed), Prentice-Hall, 2003.
Rosen KH, Discrete Mathematics and Its Applications (6th ed), McGraw-Hill, 2006.
Truss JK, Discrete Mathematics for Computer Scientists (2nd ed), Addison-Wesley, 1999.

Three-hour examination (80%) and problem sheets (20%)

30 lectures and 9 seminars