Hide menu

Advanced Algorithmic Problem Solving

2022VT

Status Running - no longer open for registrations
School IDA-gemensam (IDA)
Division AIICS
Owner Fredrik Heintz
Homepage http://www.ida.liu.se/~TDDD95/

  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 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