Algorithmic Problem Solving: Search and Dynamic Programming

Aim

The goal of the course is to develop the ability to solve algorithmic problems by utilizing knowledge of algorithms, data structures and complexity theory with a focus on search and dynamic programming. To solve this type of problem, it is important to be able to analyze the problem, choose or design an algorithm, determine how much resources (time and memory) the algorithm requires and to implement and test the algorithm quickly and correctly.

Intended learning outcomes:

• Knowledge of common algorithms and data structures related to search and dynamic programming.
• The ability of implementing algorithms and data structures related to search and dynamic programming.
• The ability of solving algorithmic problems related to search and dynamic programming.
• The ability of analysing the efficiency of different approaches to solving a problem, with a focus on search and dynamic programming, to determine which approaches will be efficient enough in a given situation.

Content

Successful problem solving in computer science requires a solid theoretical foundation as well as ability to apply the theory to practical problem solving. The aim of this course is to develop your ability to solve complex algorithmic problems by applying knowledge of algorithms, data structures, and complexity theory. As a professional software developer, it is essential to being able to analyse a problem, chose or design an algorithm, judge the efficiency of a proposed algorithm, and to implement and test it quickly and correctly. In this course you will practice this by solving well defined algorithmic problems with a focus on search and dynamic programming.

The purpose is that the students should be able to use programming and algorithms, with a focus on search and dynamic programming, as an effective tool for problem solving, and should get opportunity to apply theoretical knowledge from other courses to solve practical problems.

The course covers search and dynamic programming, two general approaches to solving algorithmic problems. Many optimisation and string algorithms are based on dynamic programming such as the knapsack problem and string matching. Search methods that are covered includes binary search, depth first search, breadth first search, A* search, and heuristic search.