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
|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%) |
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.|
What is logic?
What is a rational argument?
What are common fallacies?
- Boolean algebra
Connections with hardware design and programming.
Logic gates and circuits.
Simple arithmetic induction.
Weak and strong 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.
Examples of maths algorithms.
Recurrence and recursion.
Example: Insertion sort.
Introduction to data structures
Lists, arrays, linked lists, stacks, queues.
Graphs and trees.
What are greedy algorithms?
Minimum spanning trees.
Divide and conquer algorithms
What are divide and conquer algorithms?
What is dynamic programming?
Calculating binomial coefficients.
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.
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.