The aim of this course 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.
The course comprises three parts, each ending with an assignment:
In the first part, you’ll learn about the basic data structures for organizing data, like lists, stacks, queues, dictionaries, and sets. You’ll also learn how to analyze the complexity of an algorithm and how to measure its runtime.
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 and greedy algorithms. These are general-purpose techniques for solving a wide range of problems.
In the third part, you’ll further develop your understanding of graphs and algorithmic techniques (backtracking, dynamic programming). You’ll also learn about the limitations of computational problem solving (non-computability and the P ? NP conjecture). |