# 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.