Algorithms Design and Complexity

Objectives

Calculate the complexity of an algorithm and estimate the time needed to complete it

Produce an algorithm in Python

Improve algorithms in terms of complexity

Understand commonly used data structures

Learn the notion of complexity classes

Course outline

The first part of the course focuses on calculating the complexity of an algorithm, first in the non-recursive case and then in the recursive case. While the non-recursive case is simply a matter of counting the number of operations and requires only a knowledge of simple arithmetic, the recursive case is more complex and has its own tools, such as the general theorem. We also look at the notion of complexity classes and NP-hardness.

We then look at different data formats and their complexity for different elementary operations. Finally, we’ll look at how dynamic programming can be used to reduce the complexity of an algorithm.

Prerequisites

Rudiment in imperative programming