Algorithms, data structures and computability

The aim of this module is to help you become a computational problem solver. You’ll learn techniques to efficiently solve computational problems and apply them using the Python programming language. You’ll also learn about the limitations of computing: which problems can’t be solved algorithmically or for which no efficient solutions are known. This is the module for you if – whatever your field – you need to implement an efficient algorithm or to understand both the power and the limitations of computing. Though the focus is on the underlying ideas, you’ll also work with some mathematical concepts and notation.

What you will study

You’ll learn to take a problem and state it precisely in order that it can be solved with a computer. In other words, you’ll learn to express the problem in a way which allows you to write an algorithm for solving it. However, not all algorithms are equally good solutions. For that reason, you’ll also learn how to analyse the speed and efficiency of algorithms and establish whether an algorithm really does what it is supposed to do. Finally, you’ll delve into the very foundations of computing. You’ll learn which problems cannot be solved with an algorithm. You’ll also learn what the limits are on the speed with which algorithms can solve many important practical problems.

The module comprises three parts:

Part 1
In the first part, you’ll learn about the basic data structures for organising data, like lists, stacks, queues, dictionaries, and sets. You’ll also learn how to analyse the complexity of an algorithm and how to measure its runtime.

 

Part 2
The second part covers two non-linear data structures: trees and graphs. The former can represent hierarchical data and the latter can model social, transport and other kinds of networks. The main focus of the second part are algorithmic techniques like search (brute-force, breadth-first and depth-first), divide and conquer, recursion, greedy algorithms and dynamic programming. These are general-purpose techniques for solving a wide range of problems.

Part 3
In the third part, you’ll further develop your understanding of sets, functions, logic and proofs, using formal mathematical notation. This will be in the context of concrete applications, such as databases. At this point, you’ll also learn about the limitations of computational problem solving (non-computability and the P ≠ NP conjecture).

Entry requirements

To enrol on M269 to start in October, you must either have:

1. passed Object-oriented Java programming (M250) (or be enrolled on it to start in October)
2. passed Introduction to computing and IT 2 (TM112) (or be enrolled on it and have started it in April).

You need an understanding or experience of computing; an understanding and experience of programming; and some knowledge of mathematics – check if you’re ready for M269, with our self-assessed quiz.

If you’re not sure you’re ready, talk to an adviser.

What's included

You’ll have access to a module website, which includes:

• a week-by-week study planner
• course-specific materials
• audio and video content
• assessment details, instructions and guidance
• online tutorial access
• access to student and tutor group forums.

The first two parts of the module are delivered using Jupyter notebooks that include the module’s text and the code for the examples and exercises. The first two parts are also available in PDF and HTML. You'll also be provided with one printed module book, covering the third part of the module.

Computing requirements

A computing device with a browser and broadband internet access is required for this module. Any modern browser will be suitable for most computer activities. Functionality may be limited on mobile devices.

Any additional software will be provided, or is generally freely available. However, some activities may have more specific requirements. For this reason, you will need to be able to install and run additional software on a device that meets the requirements below.

A desktop or laptop computer with either an up-to-date version of Windows or macOS.

The screen of the device must have a resolution of at least 1024 pixels horizontally and 768 pixels vertically.

To join in the spoken conversation in our online rooms we recommend a headset (headphones or earphones with an integrated microphone).

Our Skills for OU study website has further information including computing skills for study, computer security, acquiring a computer and Microsoft software offers for students.

Teaching and assessment

Support from your tutor

Throughout your module studies, you’ll get help and support from your assigned module tutor. They’ll help you by:

• Marking your assignments (TMAs) and providing detailed feedback for you to improve.
• Guiding you to additional learning resources.
• Providing individual guidance, whether that’s for general study skills or specific module content.
• Facilitating online discussions between your fellow students, in the dedicated module and tutor group forums.

Module tutors also run tutorials throughout the module. Where possible, recordings of online tutorials will be made available to students. While these tutorials won’t be compulsory for you to complete the module, you’re strongly encouraged to take part. If you want to participate, you’ll likely need a headset with a microphone.

Assessment

The assessment details for this module can be found in the facts box above.

You must use the online eTMA system to submit your tutor-marked assignments (TMAs).