# COMP102P - Theory I

**This database contains the 2017-18 versions of syllabuses.**

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