COMP104P - Theory II
This database contains 2016-17 versions of the syllabuses. For current versions please see here.
IEP Year 1 Discipline specific module
|Taught By||Anthony Hunter (50%) |
Ilya Sergey (50%)
|Aims||To develop programming and problem solving skills, to encourage a thoughtful approach to analysis and design problems, to familiarise students with logical and mathematical inference and argumentation.|
|Learning Outcomes||Students should be able to apply this knowledge to specification of algorithms and logic programming.|
Searching and sorting algorithms
Elementary searching - comparing sequential, binary and interpolation search.
Binary search trees.
Depth-first search of undirected and directed graphs.
Strongly connected components.
Topological sorting of acyclic graphs.
Breadth-first search of directed and undirected graphs.
File compression including Huffman coding.
Cryptology including public key cryptosystems.
Analysis of algorithms
Empirical versus theoretical analysis.
Best, worst and average cases.
Classifications of algorithms.
Hierarchies of complexity.
Tractable and intractable problems.
Sums of series.
Simple summation formulae.
Estimating a sum using integration.
Algorithms with loops
Examples in geometric algorithms: Prim's and Kruskal's algorithms
Recursive algorithms and recurrence relations
First-order recurrence relations.
Solving recurrence using the characteristic equation.
Change of variable, conditional asymptotic notation.
Examples of maths algorithms including exponentiation and large multiplication.
Analysis of searching and sorting algorithms
Sequential search in ordered and unordered arrays
Insertion sort, mergesort, quicksort.
Best case for comparison-based sorting.
Reasoning about Programs
Loop and recursion variants and proving termination.
Pre and post-conditions.
Loop variants and proving correctness.
Method of Instruction:
Lecture presentations with associated courseworks.
The course has the following assessment components:
- Written Examination (2.5 hours, 90%);
- Coursework Section (2 pieces, 10%).
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/McGraw-Hill, 2001
R. Sedgewick, Algorithms, Addison-Wesley, 1998.