Hide menu

AAPS Advanced Algorithmic Problem Solving

Exercises


Exercises

There are six homework exercises in the course, each consisting of a number of problems that should be solved individually. Besides solving the problems, each student should also write a short report for each exercise discussing the following aspects of the problems:

  • Difficulty: What is the relative difficulty of the problems? Did your initial estimation of the difficulty turn out to be correct? Why are the easy problems easy and why are the hard problems hard? What would make them easier/harder?
  • Efficiency: How efficient does a solution have to be to be accepted? Are there more efficient solutions? Are there alternative solutions with the same efficiency? What changes to the problem would lead to different solutions?
  • Problem solving techniques: How did you solve the problem? What problem solving techniques did you use? Did you choose the right technique from the beginning? Could other problem solving techniques be used instead? What did you learn from solving the problems?
  • Testing and debugging techniques: How did you test your programs? Did you have to debug them? If you did, how did you debug them? Did you use some testing or debugging strategy? What did you learn from testing and debugging your programs?
It is recommended to discuss these questions for each problem separately, but it is not required. Each report (one per round of exercises) gives up to 3 points towards the grade on UPPG1. Each discussed problem usually gives at most 0.5 points. The report may be handed in after the deadline for the exercises.

The purpose of the exercises is to:

  • 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.
  • Analyze the efficiency of different approaches to solving a problem to determine which approaches will be reasonably efficient in a given situation.
  • Quickly and correctly implement algorithms and data structures.
  • Effectively test and debug algorithms and data structures.

Problems solved before the deadline gives 1 point and problems solved after the deadline gives 0.5 points towards the grade on UPPG1. Problems marked with (*) are considered to be more difficult and to get an A on the course it is necessary to solve at least one of these for each round of exercises (this is a necessary but not a sufficient condition). Solutions to the problems will be discussed at the practice session right after the deadline. Students should be prepared to present their solutions and answers to the exercise questions at the practice sessions.

The exercises will be published on this page as the course progresses. The automatic judge Kattis is used to manage the exercises.

Exercise 1: Data structures

Deadline 2014-02-03 kl 15:00

Exercise 2: Greedy Problems and Dynamic Programming

Deadline 2014-02-17 kl 15:00

Exercise 3: Graph Algorithms

Deadline 2014-03-10 kl 15:00

Exercise 4: Search

New deadline 2013-04-07 kl 15:00 (old deadline 2013-03-24 kl 15:00)

Exercise 5: Math-related Problems

Deadline 2014-04-07 kl 15:00

Exercise 6: Computational Geometry

Deadline 2014-05-05 kl 15:00


Page responsible: Fredrik Heintz
Last updated: 2014-03-25