Advanced Algorithmic Problem Solving 2013VT Status Archive School Computer and Information Science (CIS) Division AIICS Owner Fredrik Heintz Homepage http://www.ida.liu.se/~frehe/aaps

Log in

---

Course plan

Introduction

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 and as a researcher it is useful to be able to analyze a problem, chose or design an algorithm, judge the efficiency of proposed algorithms, and to implement and test them quickly and correctly. In this course you will practice this by solving a large number of homework assignments and working under time constraints during problem solving sessions. The course will also contain a competitive element where individuals and teams should solve algorithmic problems with time and resource constraints.

Goals

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

The goals of the course are that the student should be able to

• analyze the efficiency of different approaches to solving a problem to determine which approaches will be reasonably efficient in a given situation,


• compare different problems in terms of their difficulty,


• use algorithm design techniques such as greedy algorithms, dynamic programming, divide and conquer, and combinatorial search to construct algorithms to solve given problems,


• strategies for testing and debugging algorithms and data structures,


• quickly and correctly implement a given specification of an algorithm or data structure,


• communicate and cooperate with other students during problem solving in groups.

The course was last given

New course.

Recommended for

The course is recommended for everyone who is interested in solving advanced problems which require some form of algorithms. It is especially interesting for those that want to be able to quickly and correctly develop working implemented solutions involving algorithms.

Prerequisites

Knowledge of data structures, algorithms and programming. It is good but not required to take the course in Construction and Analysis of Algorithms (TDDD20)/Computation II. Some algorithms and techniques are covered in both courses, however, the focus in this course is much more practical including how to implement and use the algorithms.

Organization

The course consists of six practice sessions and six contest sessions. A practice session is a 3 hour seminar where we discuss the previous set of exercises, prepare for the next set of exercises and discuss algorithmic problem solving in general. Practice sessions are to large degree student driven. A contest session is a 5 hour problem solving session where students should solve as many algorithmic problems as possible from a given problem set using their own computers.

Examination

The examination consists of two parts:
LAB1 6hp, individually solving lab assignments, creating a well structured and reusable code library, and actively participating in at least 4 problem solving sessions (called contest sessions in the schedule).
UPPG1 3hp, individually solving home work exercises.

The course will be graded and the grade depends on the quality of the code library, the performance in the problem solving sessions, and the number of exercises completed.

Literature

There is no required literature for this course. The books below are suggested literature that can help you in completing the course.

Competitive Programming 2
Steven and Felix Halim.
https://sites.google.com/site/stevenhalim/
- A very practical book dedicated to the type of algorithmic problem solving covered in the course.

Introduction to Algorithms, Third Edition
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
- The definitive reference when it comes to algorithms.

Algorithmic Problem Solving
R. Backhouse
http://algorithmicproblemsolving.org/
- A good book about algorithmically solving mathematically oriented problems, describes several useful techniques such as finding invariants and using induction.

How to Solve It
G. Polya
- Describes a general method for solving problems, especially mathematical problems.

Examiner

Fredrik Heintz

Credit

9 hp

Comments

If you have questions, please contact fredrik.heintz@liu.se.

Page responsible: Anne Moe