COMP1004 - Theory IINote: Whilst every effort is made to keep the syllabus and assessment records correct, the precise details must be checked with the lecturer(s).
- Taught By
- Denise Gorse (50%)
Anthony Hunter (50%)
- 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
Binary search trees.
- Graph algorithms
- Depth-first search of undirected and directed graphs.
Strongly connected components.
Topological sorting of acyclic graphs.
Breadth-first search of directed and undirected graphs.
- Text algorithms
- String searching.
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
- Nested 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.
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 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.