# COMP102P - Theory I

This database contains 2017-18 versions of the syllabuses. For current versions please see here.

Code COMP102P (CS alternative to ENGS103P)IEP Year 1 Discipline specific module 1 A-level Mathematics. Students will be required to implement a program in C, so some programming experience is desirable. 1 Mark Herbster (50%) James Brotherston (50%) To introduce formal methods for reasoning about algorithms and, more generally, to formalise the reasoning process. 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.