COMP116
Analytic Techniques for Computer Science
Aims
- To equip students with an awareness of the range of methodologies that have been brought to bear in the treatment of computational issues.
- To provide practical experience in how various formal approaches can be used to address such issues.
Syllabus
- Computation as static measurement:
Numbers and types of number: integer, rational, irrational. Structured forms: Vectors and vector operations;. Linear transformations. Applications in video games and robot motion planning. (3 lectures) - Computation as dynamic measurement:
Introduction to calculus; functions and their graphs: geometric interpretation of derivative; standard differentiation formulae and rules; maxima and minima, information obtained from second derivative; basic integral calculus; geometric interpretation of integral; standard integral formulae. (5-6 lectures) - Beyond traditional notions of number:
Definition of complex number, representation forms (coordinate, polar), properties of complex numbers: conjugates, modulus, standard arithmetic operations. (3 lectures) - Computational approaches for hard calculations:
Experimental analysis; the distinction between probability and statistics; providing support for experimental claims. (3-4 lectures) - Computational models of richer structures:
Linear and Matrix algebra; common computational objects described by matrices; weighted directed graphs; properties and operations on matrices: determinant, singularity and invertibility; eigenvalues and eigenvectors; conditions guaranteeing existence of useful forms -- the Perron-Frobenius Theorem: notable applications of the PF-eigenvector: Google page ranking algorithm; ranking of sports leagues. (8-9 lectures) - A bit of information theory:
Shannon''s Fundamental questions: what is information? how is it measured? what limits storage and communication of information? example contexts: MP3 files, CD, streaming video. Shannon''s model of information transmission; probabilistic interpretation of information measure and Shannon''s axioms; the notion of information entropy. (4-6 lectures)
Learning Outcomes
- Students will have a basic understanding of the range of techniques used to analyse and reason about computational settings.
- Students will have the ability to solve problems involving the outcome of matrix-vector products as might arise in standard transformations.
- Students will have the ability to apply basic rules to differentiate and integrate commonly arising functions.
- Students will have a basic understanding of manipulating complex numbers and translating between different representations.
- Students will have a basic understanding of the role of Linear algebra (including eigenvalues and eigenvectors) in computation problems such as web page ranking.