KBS_Icon_questionmark link-ico

Foundations Of Computing 2 (Module)

Module description

Aims
To introduce the basic concepts of computational mathematics which are needed in other modules.

Learning Outcomes
After studying this module, the students will be able to work with integers, matrices, recurrences, graphs and probabilities; model and solve practical problems by using the taught methods and design efficient algorithms for graph, matrix and number theoretic problems in computer science.

Provisional Syllabus
Graph theory
Trees: Search trees, minimum weight spanning trees, encodings of trees
Shortest path algorithms
Colouring graphs, and applications to scheduling problems
Travelling salesman and Euler tour problems
Huffman trees and prefix codes
Recurrence Relations
Analysis of recursive algorithms
Solving recurrences
Counting binary trees
Number theory
Euclids algorithm for greatest common divisors
Primality testing, integer factorisation
RSA cryptosystem
Algebra
Matrix multiplication
Applications to systems of linear equations and matrix inverses
Probability and statistics:
Basic definitions and examples
Conditional probability and independence
Random variables, mean and variance, standard deviation
N-grams in language processing

Staff information

Not applicable

Teaching pattern

Not applicable

Module assessment - more information

Not applicable

Key information

Module code 5CCS2FC2

Credit level 5

Assessment

Credit value 15

Semester Semester 2 (spring)

Study abroad module Yes