# COMP1004 - Theory II

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
COMP1004
Year
1
Prerequisites
COMP1002
Term
2
Taught By
Denise Gorse (50%)
Anthony Hunter (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.

# 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 sections combined

The examination rubric is:
Answer 3 questions; at least 1 (out of 3) from Part I and 1 (out of 3) from Part II. All questions carry equal marks.

# Resources:

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