COMP1002 - Theory INote: Whilst every effort is made to keep the syllabus and assessment records correct, the precise details must be checked with the lecturer(s).
- A-level Mathematics
- Taught By
- Juan Navarro Perez (50%)
Anthony Hunter (50%)
- 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
- Greedy algorithms
- What are greedy algorithms?
Minimum spanning trees
- Divide and conquer algorithms
- What are divide and conquer algorithms?
- Dynamic programming
- 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 sections combined
The examination rubric is:
Answer all three questions. The questions carry equal marks.
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.