Teaching & Learning

COMP104P - Theory II

This database contains the 2016-17 versions of syllabuses. Syllabuses from the 2015-16 session are available here.

Note: Whilst every effort is made to keep the syllabus and assessment records correct, the precise details must be checked with the lecturer(s).

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.