COMP116

Analytic Techniques for Computer Science

Aims

  1. To equip students with an awareness of the range of methodologies that have been brought to bear in the treatment of computational issues.
  2. To provide practical experience in how various formal approaches can be used to address such issues.

Syllabus

  1. 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)
  2. 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)
  3. Beyond traditional notions of number:
    Definition of complex number, representation forms (coordinate, polar), properties of complex numbers: conjugates, modulus, standard arithmetic operations. (3 lectures)
  4. Computational approaches for hard calculations:
    Experimental analysis; the distinction between probability and statistics; providing support for experimental claims. (3-4 lectures)
  5. 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)
  6. 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.