Algorithmic Problem Solving, BSc (Spring 2024)

Abstract

Algorithmic problem solving is the art of designing algorithms to solve challenging programming problems. This requires extensive practice in classifying problems, choosing the right data structures, and identifying suitable algorithms. This is very different to a standard algorithm and data structure course, where the focus is on understanding the tools at hand, but not on using them to solve problems. This course bridges the gap between theoretical knowledge and practical solutions to computational problems.

Description

This course fills the gap between theoretical knowledge and practical solutions to computational problems. In the first ten weeks, we cover different problem solving techniques such as dynamic programming and greedy algorithms. These techniques are applied to solve computational problems on the kattis programming platform. As part of the curriculum, we discuss the design of programming problems both from a conceptual as well as technical perspective. In the final weeks, students in groups carry out a project that aims to

1. create one or multiple well-defined programming exercises, including test cases for automatic solution checking. This includes (i) defining an algorithmic problem, (ii) writing a problem description, and (iii) generating intended solutions and test cases.
2. solve one or multiple programming exercises from a pre-defined selection. These exercises will be selected in coordination with the supervisor.

This work is documented in a report that forms the basis of the exam.

Formal prerequisites

Open to all students who have completed an introductory course in programming (Python or Java are fine) and an introductory course in algorithms and data structures (such as ADS at ITU).

Intended learning outcomes

After the course, the student should be able to:

• Explain, choose and make use of a wide range of algorithmic problem solving techniques
• Implement an algorithmic solution to a computational problem
• Design a computational problem, including a problem description, implemented accepted and wrong solutions, and design of test cases
• Test the correctness and empirical running time of an implementation by generating appropriate test cases

Ordinary exam

Exam type:
D: Submission of written work with following oral, External (7-point scale)
Exam variation:
D2G: Submission for groups with following oral exam supplemented by the submission. Shared responsibility for the report.