F17SO - Discrete Mathematics

Course leader(s):

Syllabus

1. Set Theory and Combinatorics (1.1 Set algebra, Functions and Relations, Mathematical Induction, Elementary counting methods, Permutations and Combinations, The Inclusion-Exclusion Principle.)

2. Probability Theory (2.1 Probability Space, Conditional Probability, Independence and Bayes’ Theorem)

3. Recurrence Relations (3.1 Solving problems by iteration, First and second order recurrence relations, Recurrences in Algorithms)

4. Graph Theory (4.1 Introduction to graphs, Basic graph terminology, Adjacency Matrices, Paths and connectivity, Connected components, Shortest path problems in weighted graphs, Dijkstra’s Algorithm. Trees and spanning trees, Breadth-first search, Kruskal’s and Prim’s Algorithms for a minimal spanning tree, Euler and Hamilton paths, Fleury’s Algorithm for constructing Euler circuits, Estimates for Hamilton circuits)

5. Matrices and Linear Transformations (5.1 Linear equations and elementary row operations, Elementary matrices and Gaussian elimination, Echelon matrices, Eigenvectors and eigenvalues)

Learning outcomes

By the end of the course, students should be able to do the following:

• apply the theory of sets, functions, or relations to solve various problems
• use elementary combinatoric formulas to solve counting problems
• use probability theory to calculate probabilities in a variety of contexts
• use general solutions of standard recurrence relations to solve various problems
• apply graph algorithms to solve a variety of problems
• apply Gauss elimination method to find the solutions of systems of linear equations
• use the characteristic polynomial of a matrix to find its eigenvalues and eigenvectors
• question the validity of naive intuition in favour of careful, quantitative reasoning in analysing problems related to computer science

Further details

Curriculum explorer: Click here

SCQF Level: 7

Credits: 15