COMP102P - Theory I

This database contains the 2017-18 versions of syllabuses. Syllabuses from the 2016-17 session are available here.

Note: Whilst every effort is made to keep the syllabus and assessment records correct, the precise details must be checked with the lecturer(s).

Code COMP102P (CS alternative to ENGS103P)
IEP Year 1 Discipline specific module
Year 1
Prerequisites A-level Mathematics. Students will be required to implement a program in C, so some programming experience is desirable.
Term 1
Taught By Mark Herbster (50%)
James Brotherston (50%)
Aims To introduce formal methods for reasoning about algorithms and, more generally, to formalise the reasoning process.
Learning Outcomes Students should be familiar with the techniques listed below and should be able to apply them to real problems. They should be able to extract the logical content of a (propositional) argument and prove its validity. They should be able to formalise an algorithm and analyse its efficiency.

Content

Argumention

  • What is logic?
  • What is a rational argument?
  • What are common fallacies?

Boolean algebra

  • Examples.
  • Axiomatisation.
  • Normal forms.
  • Connections with hardware design and programming.
  • Logic gates and circuits.

Induction

  • Simple arithmetic induction.
  • Weak and strong induction.
  • Structured induction.

Language

  • Syntax of propositional logic and predicate logic.
  • Translating English into logical formulas and vice versa.
  • Propositional semantics - truth tables.
  • First 0rder Semantics.
  • Satisfiability, validity, equivalence.
  • Other languages - Kleene Algebra.

Introduction to algorithms

  • What are algorithms?
  • Why study algorithms?
  • Pseudocode.
  • Efficiency of algorithms.
  • Elementary operations.
  • Examples of maths algorithms.
  • Recurrence and recursion.
  • Example: Insertion sort.
  • Optimisation problems.

Introduction to data structures

  • Lists, arrays, linked lists, stacks, queues.
  • Graphs and trees.
  • Tree traversal.
  • Heaps.

Greedy algorithms

  • What are greedy algorithms?
  • Minimum spanning trees.
  • Kruskal's algorithm.
  • Prim's algorithm.
  • Dijkstra's algorithm.
  • Greedy heuristics.

Divide and conquer algorithms

  • What are divide and conquer algorithms?
  • Binary search.
  • Quicksort algorithm.

Dynamic programming

  • What is dynamic programming?
  • Calculating binomial coefficients.
  • Floyd's algorithm.
  • Warsall's algorithm

Method of Instruction

Lecture presentations with associated courseworks.

Assessment

The course has the following assessment components:

  • Written Examination (2.5 hours, 95%);
  • Coursework Section (2 pieces, 5%).

To pass this course, students must:

  • Obtain an overall pass mark of 40% for all components combined;
  • Obtain a minimum mark of 30% in each component worth ≥ 30% of the module as a whole.

Resources

Reading list available via the UCL Library catalogue.