Current students

COMP102P - Theory I

This database contains 2016-17 versions of the syllabuses. For current versions please see here.

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%)
Robin Hirsch (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:

T. Cormen, S.Clifford, C. Leisserson, and R. Rivest, Introduction to Algorithms, MIT Press, 2001

W. Hodges, Logic: an introduction to elementary logic, Penguin, 1977.

R. Sedgewick, Algorithms, Addison-Wesley, 1998.

R. Sedgewick, Algorithms in C++, Addison-Wesley, 1992.

J. Truss, Discrete mathematics for computer scientists, Addison-Wesley, 2nd edition, 1999.