# TDDD95 Algorithmic Problem Solving

### Exercises

# Exercises

There are 14 homework exercises in the course, one for each week. Each consists of 4 problems that should be solved individually.

The purpose of the exercises is to:

- Use algorithm design techniques such as greedy algorithms, dynamic programming, divide and conquer, and combinatorial search to construct algorithms to solve given problems.
- 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 a 5 on the course it is necessary to solve at least half of the marked problems (before or after deadline), i.e. at least 7 in total. Solutions to the problems will be discussed at the seminar right after the deadline. Students should be prepared to present their solutions and answers to the exercise questions at the practice sessions. To pass the course at least one exercise from each week has to be solved (before or after deadline).

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

## Exercise 1: Greedy Problems and Dynamic Programming I

**Deadline 2021-01-22 kl 10:00**

## Exercise 2: Data structures

**Deadline 2021-01-29 kl 10:00**

## Exercise 3: Arithmetic

**Deadline 2021-02-05 kl 10:00**

## Exercise 4: Greedy Problems and Dynamic Programming II

**Deadline 2021-02-12 kl 10:00**

- Cudak
- Funny Games (*)
- Square Fields (Hard) (Even though the problem name includes "hard" this problem is not marked with a *.)
- The Uxuhul Voting System

## Exercise 5: Graphs I

**Deadline 2021-02-19 kl 10:00**

## Exercise 6: Graphs II

**Deadline 2021-02-26 kl 10:00**

## Exercise 7: Graphs III

**Deadline 2021-03-05 kl 10:00**

## Exercise 8: Mixed

**Deadline 2021-03-31 kl 08:00**

## Exercise 9: Strings I

**Deadline 2021-04-09 kl 13:00**

## Exercise 10: Strings II

**Deadline 2021-04-16 kl 13:00**

## Exercise 11: Search

**Deadline 2021-04-23 kl 13:00**

## Exercise 12: Math-related Problems

**Deadline 2021-04-28 kl 08:00**

## Exercise 13: Computational Geometry

**Deadline 2021-05-07 kl 13:00**

## Exercise 14: Combinatorics and Probability Theory

**Deadline 2021-05-12 kl 08:00**

Page responsible: Fredrik Heintz

Last updated: 2021-01-21