Formal Algorithm Analysis for Premaster

URL study guide

Description

Objectives

In this course, you will develop basic skills and knowledge to create and reason about efficient algorithms to solve computational problems.
We first introduce asymptotic notation to formally analyze the running time of an algorithm. After briefly discussing algorithmic complexity (NP-hardness), we discuss basic algorithm design techniques and how to formally prove an algorithm’s correctness.

Students will upon completing the course be able to

• reason about the efficiency and correctness of both given and self-created algorithms by applying formal proving methods, such as the Master Theorem, proof by substitution, or proof by loop invariant.

• select and apply suitable data structures for frequently appearing problems, depending on the given input data.

• apply basic algorithm design techniques to solve variations of frequently appearing problems, such as sorting values or searching for a specific value in a data set.

• create efficient algorithms to solve basic computational problems by modifying known algorithms and data structures.

• recognize and apply different proving techniques for formal textual proofs, such as direct proof, indirect proof, case distinction, and proof by induction.

• recognize computationally hard problems by relating a given problem to common examples of NP-hard problems.

Method of Assessment