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.

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.

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

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

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