COMP108 - Algorithmic Foundations

Year: 2011-12
Originating department: Computer Science
Faculty: Faculty of Science & Engineering
Semester: Second Semester
Credit level: Level One
Credit value: 15
External examiner: Professor Anthony Hunter
Member of staff with responsibility for the module: Dr P Wong
Board of studies: Board of Studies in Computer Science
Mode of delivery: Lectures/Practical
Contact hours: 36 lectuers (3 per week for 1 semester), 12 tutorials
Pre-requisites: COMP109
Co-requisites: none

Module description

Aims

• To introduce the notation, terminology, and techniques underpinning the study of algorithms.
• To introduce the standard algorithmic design paradigms employed in the development of efficient algorithmic solutions.
• To introduce the mathematical tools needed for the analysis of algorithms in terms of the use of formal models of Time and Space.

Learning outcomes

At the conclusion of the module students should be able to:

• describe standard algorithms such as sorting algorithms, search algorithms, string matching algorithms, graph traversal algorithms;
• apply these algorithms or a given pseudo code algorithm in order to solve a given problem;
• carry out simple asymptotic analyses of algorithms involving sequence, selection, and iteration, and identify and compare simple properties of these algorithms;
• describe the algorithm design principles of divide-and-conquer, greedy method, and dynamic programming and distinguish the differences between these principles;
• apply the studied algorithms that illustrate these design principles;
• apply the studied design principles to produce algorithmic solutions to a given problem;
• explain and illustrate the distinction between different classes of problems, in particular, polynomial time and exponential time solvable problems.

Teaching and learning strategies

Formal Lectures: Students will be expected to attend three hours of formal lectures in a typical week. Formal lectures will be used to introduce students to the concepts and methods covered by the module.
Tutorials: Supporting tutorials are held each week in which students work under staff guidance on problem sets designed to reinforce understanding of the lecture material with the possibility of immediate feedback.
Private study: In a typical week, students will be expected to devote 6 hours of unsupervised time to private study; private study will provide time for reflection and consideration of lecture material and background reading and completion of the assessment tasks.
Assessment: Continuous assessment will be used to test to what extent practical skills have been learnt. A final examination at the end of the module will assess the academic achievement of students.

Syllabus

• Introduction (8 lectures)
  • Definition of an algorithm, counting elementary operations during execution, worst-case analysis of running time and storage requirements - on several examples of simple algorithms. Design of pseudo code algorithms.
• Complexity Issues (6 lectures)
  • Asymptotics and "order of" notation for complexity. Comparison of polynomial time and exponential time complexities and examples of algorithms with such complexities. Brief introduction of the notion of computable and non-computable functions.
• Review of Graphs structures and their representation (3 lectures)
  • Directed and Undirected graphs; Trees; representation by adjacency matrices and incidence lists, graph and tree traversals.
• Algorithm Design Techniques (19 lectures)
  • Review of the standard algorithm design paradigms commonly used in Computer Science together with typical example problems solved by these.
    • Overview: why a range of design methods is needed.
    • Divide-and-Conquer algorithms: general overview of approach; run-time analysis of simple Divide-and-Conquer methods via solution of recurrence relations.
    • Dynamic Programming: differences from Divide-and-Conquer; general overview; necessity for iterative implementation.
    • Greedy Method: concept of optimisation problem and the distinction between 'exact' and 'approximate' solution algorithms.

Recommended texts

Recommended Textbook
Introduction to the Design and Analysis of Algorithms, Anany V. Levitin, Villanova University, 2003, 0-201- 74395-7, Addison-Wesley

Further Reading
Introduction to ALGORITHMS, TH Cormen, CE Leiserson and RL Rivest, MIT Press/McGraw-Hill, 2nd Edition 2001.
Discrete Mathematics, Richard Johnsonbaugh, Prentice-Hall, 2001.

Assessment weightings

20% continuous assessment 80% written examination