BSc Computer Science and Mathematics

Year of entry: 2024

Course unit details:
Algorithms and Data Structures

Course unit fact file
Unit code COMP26120
Credit rating 20
Unit level Level 2
Teaching period(s) Full year
Available as a free choice unit? No

Overview

This course unit covers fundamental material in Computer Science concerning algorithms and their correctness and performance. It is a two-semester very practical course, with few lectures, considerable practical experience and tutorial support. The student is expected to seek out material to support work on the course, thus contributing to developing "algorithmic literacy". The implementation of algorithms is illustrated in the widely-used programming language C.

Pre/co-requisites

Unit title Unit code Requirement type Description
Introduction to Programming 1 COMP16321 Pre-Requisite Compulsory
Introduction to Programming 2 COMP16412 Pre-Requisite Compulsory

Alternative equivalent knowledge of Java accepted.

Aims

To make best use of available learning time by encouraging active learning and by transmitting information in the most effective ways.

To make students aware of the importance of algorithmic concerns in real-life Computer Science situations.

To emphasise practical concerns, rather than mathematical analysis.

To become confident with a range of data structures and algorithms and able to apply them in realistic tasks.

Learning outcomes

  • ILO 1 Analyse problems to identify and implement the most appropriate algorithmic solution
  • ILO 2 Define standard notions of asymptotic complexity and use these to reason about the complexity of algorithms
  • ILO 3 Use pseudocode to represent algorithms and informally reason about their correctness 
  • ILO 4 Recall the definitions and representations of basic data structures and the complexity of the operations on them
  • ILO 5 Explain, using examples of real-world applications, standard algorithmic problems coming from sorting and searching on different data structures, operations on graphs, and number theory
  • ILO 6 Identify from a set of taught algorithms, which algorithm should apply in a given situation, explain how it should be applied, and compare the solution to possible alternatives 
  • ILO 7 Explain the algorithmic techniques such as divide-and-conquer, dynamic programming, greedy algorithms, and linear programming, discuss when they are appropriate, and apply them to solve problems
  • ILO 8 Recall and explain the notions of tractability and NP-completeness, with a particular focus on classical NP-complete problems, and apply these to demonstrate NP-completeness of new problems
 

 

Syllabus

Algorithms - what they are and how to express them (in pseudocode and selected programming languages: Java, C or Python).

Practical experience in devising, assessing and using algorithms:

  • considerable practice in algorithmic problem solving for realistic problems
  • examples from a wide range of application areas
  • finding appropriate algorithms and data-structures
  • inventing appropriate algorithms and data-structures

Practical experience in 'algorithmic literacy' - knowing how to use the extensive literature on the subject, recognising what algorithms to use in applications and assessing their utility.

A range of basic data structures: arrays, lists, trees (including ordered and balanced trees and heaps), and various kinds of graphs.  Representations of basic data structures in programming languages.

A range of basic algorithms: searching and sorting algorithms, tree traversal and manipulation algorithms, some basic graph algorithms. Other algorithmic areas will be explored through practical examples.

An introduction to algorithmic performance: space and time requirements, worst-case, average-case and best case estimates. Practical experience and techniques for measuring and predicting performance: Counting operations.

Scaling and some common rates of growth.

Reasoning about algorithms - experience in informally reasoning about algorithms to establish correctness.

Teaching and learning methods

Asynchronous material (directed videos and reading):

44 hours in total, 2 hours of study per week 

Synchronous Q&A Sessions

22 in total, 1 per week

Laboratories

44 hours in total, 22 2-hour sessions, 1 per week

Exainanable content is introduced in both asynchronous material and lab exercises
 
Formative Blackboard quizzes each week provide early feedback on examinable concepts

Employability skills

Analytical skills
Innovation/creativity
Oral communication
Problem solving

Assessment methods

Method Weight
Written exam 50%
Practical skills assessment 50%

Feedback methods

Feedback is via a variety of methods. Immediate feedback is provided in weekly laboratory sessions. There are tutorial sessions based on work in this course unit, with feedback on the exercises. Exam feedback is provided both on a website and on individual scripts.

Recommended reading

COMP26120 reading list can be found on the Department of Computer Science website for current students.

Study hours

Scheduled activity hours
Assessment written exam 4
Lectures 22
Practical classes & workshops 44
Independent study hours
Independent study 130

Teaching staff

Staff member Role
Louise Dennis Unit coordinator

Additional notes

Course unit materials

Links to course unit teaching materials can be found on the School of Computer Science website for current students.

Return to course details