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?
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
- Copying DNA(*)
- The Mailbox Manufacturers Problem
- Moving Pianos
- Square Fields (Hard) (Even though the problem name includes "hard" this problem is not marked with a *.)
- Whac-a-Mole(*) (This problem has a tricky special case, study the picture in the problem description carefully.)
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