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.

The problems are classified by difficulty:

• 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

• A: Perfect Pth Powers
• A: Three Digits
• B: Ignore the Garbage
• C: Dead Fraction

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

• A: Getting Gold
• B: Frogger
• B: Killing Aliens in a Borg Maze
• C: Proving Equivalences

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

• A: Evil Straw Warts Live
• B: Dictionary Attack
• B: Dominant Strings
• C: Intellectual Property

Exercise 9: Strings II

Deadline 2024-04-03 kl 08:00

• A: Suffix Array Re-construction
• B: Code Theft
• B: Messages from Outer Space
• C: Life Forms

Exercise 10: Number Theory

Deadline 2024-04-12 kl 13:00

• A: Factovisors
• A: Happy Happy Prime Prime
• B: Circular Lock
• C: Rasterized Lines

Exercise 11: Search

Deadline 2024-04-19 kl 13:00

• A: Yet Satisfiability Again!
• B: Gokigen Naname
• B: Square Fields (Hard)
• C: Maximum Loot

Exercise 12: Computational Geometry

Deadline 2024-04-26 kl 13:00

• A: Board Wrapping
• A: Triangle Trilemma
• B: White Water Rafting
• C: Barking Up The Wrong Tree

Exercise 13: Mixed

Deadline 2024-05-03 kl 13:00

• A: How Many 0's?
• B: (un)Fair Play
• B: Bag of Tiles
• C: Towers of Powers 2: Power Harder

Page responsible: Fredrik Heintz
Last updated: 2024-01-16