# TDDD95 Algorithmic Problem Solving

### Exercises

# Exercises

There are 13 homework exercises in the course, approximately 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.

- A (20 problems): Problems that can be solved using direct application of concepts from the corresponding seminars and lab assignment, or have relatively simple ad-hoc solutions.
- B (19 problems): More challenging problems involving the concepts from the corresponding seminars and lab assignment. They may require that you make alterations to the core algorithm, or that you model the problem in a non-obvious way.
- C (13 problems): Very challenging problems with varying characteristics. Some require that you combine several different concepts from the course, or that you make domain-specific optimizations to the core algorithm. Many of these problems require that you identify concepts or implement algorithms that we allude to in the seminars but aren't implemented as part of the lab assignments.

Problems solved before the deadline gives 1 point in the corresponding difficulty class, while problems solved after the deadline gives 0.5 points. See the examination page for more information on grading. Solutions to the problems will be discussed at the seminar right after the deadline. Students should be prepared to present their solutions at the seminars.

## Exercise 1: Greedy Problems and Dynamic Programming I

**Deadline 2024-01-26 kl 10:00**

- A: Help!
- A: Ljutnja
- B: Spiderman's Workout
- C: Aspen Avenue

## Exercise 2: Data Structures

**Deadline 2024-02-02 kl 10:00**

- A: Chopping Wood
- B: Turbo
- B: Introspective Caching
- C: The SetStack Computer

## Exercise 3: Arithmetic

**Deadline 2024-02-09 kl 10:00**

## Exercise 4: Greedy Problems and Dynamic Programming II

**Deadline 2024-02-16 kl 10:00**

- A: Cudak
- A: The Uxuhul Voting System
- B: Whac-A-Mole
- C: Funny Games

## Exercise 5: Graphs I

**Deadline 2024-02-23 kl 10:00**

## Exercise 6: Graphs II

**Deadline 2024-03-01 kl 10:00**

- A: Full Tank?
- A: Island Hopping
- B: George
- C: Councilling

## Exercise 7: Graphs III

**Deadline 2024-03-08 kl 10:00**

- A: Get Shorty
- A: Hiding Places
- B: XYZZY
- C: Risk

## Exercise 8: Strings I

**Deadline 2024-03-27 kl 08:00**

## Exercise 9: Strings II

**Deadline 2024-04-03 kl 08:00**

## Exercise 10: Number Theory

**Deadline 2024-04-12 kl 13:00**

## Exercise 11: Search

**Deadline 2024-04-19 kl 13:00**

## Exercise 12: Computational Geometry

**Deadline 2024-04-26 kl 13:00**

## Exercise 13: Mixed

**Deadline 2024-05-03 kl 13:00**

Page responsible: Fredrik Heintz

Last updated: 2024-01-16