COMP1002 - Theory I

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
COMP1002
Year
1
Prerequisites
A-level Mathematics
Term
1
Taught By
Juan Navarro Perez (50%)
Anthony Hunter (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 sections combined

The examination rubric is:
Answer all three questions. The questions carry equal marks.

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.