Swedish web site
Advanced Algorithmic Problem Solving2022VT
|
|
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 essential 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 2021
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 strongly recommended 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 is almost the same as the Master's Level course TDDD95 Algorithmic
Problem Solving. It will be given in Block 1 in VT1 and in Block 4 in VT2.
The course consists of a weekly lecture/seminar and a weekly lab session. The
lectures/seminars are used to go discuss home work exercises, algorithms and
algorithmic problem solving. There will also be contest sessions 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 4hp, individually solving lab assignments and actively participating in at
least 3 problem solving sessions (called contest sessions in the schedule).
UPPG1 2hp, individually solving home work exercises.
The course will be graded and the grade depends on the performance in the
problem solving sessions and the number of exercises completed.
It is possible to get up to 3 extra credits for developing a well structured
and reusable code library or realizing an individual algorithmic project.
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
6+3 hp
Comments
If you have questions, please contact fredrik.heintz@liu.se.
Page responsible: Director of Graduate Studies
