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
|Prerequisites||A-level Mathematics. Students will be required to implement a program in C, so some programming experience is desirable.|
|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.|
- What is logic?
- What is a rational argument?
- What are common fallacies?
- Normal forms.
- Connections with hardware design and programming.
- Logic gates and circuits.
- Simple arithmetic induction.
- Weak and strong induction.
- Structured induction.
- 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?
- 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.
- 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.
- What is dynamic programming?
- Calculating binomial coefficients.
- Floyd's algorithm.
- Warsall's algorithm
Method of Instruction
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 components combined;
- Obtain a minimum mark of 30% in each component worth ≥ 30% of the module as a whole.
Reading list available via the UCL Library catalogue.