# COMP104P - Theory II

**This database contains 2016-17 versions of the syllabuses.** For current versions please see here.

Code | COMP104P IEP Year 1 Discipline specific module |
---|---|

Year | 1 |

Prerequisites | COMP102P |

Term | 2 |

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. |

# Content:

**Searching and sorting algorithms**

Elementary searching - comparing sequential, binary and interpolation search.

Binary search trees.

Balanced trees.

B-trees.

Hashing

**Graph algorithms**

Depth-first search of undirected and directed graphs.

Articulation points.

Strongly connected components.

Topological sorting of acyclic graphs.

Breadth-first search of directed and undirected graphs.

Network flow.

Ford-Fulkerson method.

Euler circuits.

**Text algorithms**

String searching.

File compression including Huffman coding.

Cryptology including public key cryptosystems.

**Analysis of algorithms**

Empirical versus theoretical analysis.

Algorithmic complexity.

O notation.

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**

Nested loops.

Gaussian elimination.

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

Binary search.

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.

# Assessment:

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.

# Resources:

T. Cormen, S.Clifford C. Leisserson, and R. Rivest, Introduction to Algorithms, MIT Press/McGraw-Hill, 2001

R. Sedgewick, Algorithms, Addison-Wesley, 1998.