Official course description:
Full info last published 15/11-22

Algorithmic Problem Solving, MSc

Course info
Language:
English
ECTS points:
7.5
Course code:
KSALPRS1KU
Participants max:
20
Offered to guest students:
yes
Offered to exchange students:
yes
Offered as a single subject:
yes
Price for EU/EEA citizens (Single Subject):
10625 DKK
Programme
Level:
MSc. Master
Programme:
MSc in Data Science
Staff
Course manager
Associate Professor
Course semester
Semester
Forår 2023
Start
30 January 2023
End
25 August 2023
Exam
Exam type
ordinær
Internal/External
ekstern censur
Grade Scale
7-trinsskala
Exam Language
GB
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.
  3. 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
    Learning activities

    - Learning about problem solving techniques in a lecture-like style 
    - Application of algorithmic techniques to a given computation problem 
    - Creating of a software product, as described in the problem statement, which is discussed in a report

    Mandatory activities
    The course has 10 mandatory assignments (one each week), all of which must be completed and approved before the student can take the examination. If the submission for a mandatory assignment is late or considered to be insufficient, it is not approved. However, make-up opportunities are available in these cases. Detailed descriptions of the mandatory activities are available on the course website. The student will receive the grade NA (not approved) at the ordinary exam, if the mandatory activities are not approved and the student will use an exam attempt.

    The didactical reasoning for the use of the mandatory activities is to provide the students with exercises where the practical application of the theory is present. During these mandatory activities, the students will have an opportunity to train the ILO’s of the course as well as receive feedback from either Kattis, the teacher, or the teaching assistants, in order to scaffold their level of understanding.

    The student will receive the grade NA (not approved) at the ordinary exam, if the mandatory activities are not approved and the student will use an exam attempt.

    Course literature
    Antti Laaksonen, "Competitive Programmer’s Handbook", available online at https://cses.fi/book/book.pdf.

    Student Activity Budget
    Estimated distribution of learning activities for the typical student
    • Preparation for lectures and exercises: 15%
    • Lectures: 15%
    • Exercises: 15%
    • Assignments: 20%
    • Project work, supervision included: 20%
    • Exam with preparation: 10%
    • Other: 5%
    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.
    Exam submisson description:
    Students submit a report in which they both
    1. Create one or multiple well-defined programming exercises, including test cases for automatic solution checking.
    2. Solve a subset of a pre-defined selection of programming exercises. They report on their choice of algorithmic techniques.
    Group submission:
    Group
    • 1-3
    Exam duration per student for the oral exam:
    20 minutes
    Group exam form:
    Mixed exam 2 : Joint student presentation followed by an individual dialogue. The group makes their presentations together and afterwards the students participate in the dialogue individually while the rest of the group is outside the room.


    reexam
    Exam type:
    D: Submission of written work with following oral, External (7-point scale)

    Time and date
    Ordinary Exam - submission Fri, 26 May 2023, 08:00 - 14:00
    Ordinary Exam Mon, 12 Jun 2023, 09:00 - 21:00
    Ordinary Exam Tue, 13 Jun 2023, 09:00 - 21:00
    Ordinary Exam Wed, 14 Jun 2023, 09:00 - 21:00
    Ordinary Exam Thu, 15 Jun 2023, 09:00 - 21:00
    Reexam - submission Wed, 26 Jul 2023, 08:00 - 14:00
    Reexam Fri, 18 Aug 2023, 09:00 - 21:00