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.

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

Lecture presentations with associated courseworks.

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.

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.