Advanced Algorithmic Problem Solving2014VT


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
VT 2013
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 3
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: Director of Graduate Studies
Last updated: 20120503