Overview

In this project, you will implement a content-aware image resizing algorithm. You are only required to implement DijkstraShortestPathFinder and DijkstraSeamFinder.

File Description

In this project, you will implement a) a graph algorithm, b) a graph representation of a non-graph problem, and c) optionally, a dynamic programming algorithm for seam carving.

  • DijkstraShortestPathFinder finds the shortest path by using Dijkstra’s Algorithm. Your task is to implement the Dijkstra’s Algorithm learned in class.
  • DijkstraSeamFinder finds the seam to remove by using a reduction of the shortest path problem. You’ll be able to resize an image by seam carving after completing DijkstraSeamFinder!
  • DynamicProgrammingSeamFinder is an optimized way to find the seam to remove by using dynamic programming. This is optional and worth a minor amonunt of extra credit if completed.

Note

  • We recommend you to work on the DijkstraShortestPathFinder before moving to the DijkstraSeamFinder and try implementing DynamicProgrammingSeamFinder only if time permits.
  • Once you complete the DijkstraShortestPathFinder, you may run through some (hidden) tests via GradeScope to make sure that your DijkstraShortestPathFinder works as intended!

Objectives

By the end, you will be able to:

  • Solve a real-world graph problem via reduction.
  • Represent problem solutions as states in a graph.
  • Apply graph augmentation as a strategy for solving a new class of graph problems

Getting Started

Task

Grab your partner(s) and set off on a new journey together!

If you are working in a group, consider scheduling a time to go over the spec together and discuss how to collaborate on the project. If you are working with a new partner, follow the instructions from the Deques assignment to add your partner into your group and pull the assignment from the public skeleton.

Subpages

  1. Background - Familiarize yourself with Seam Carving and the assignment.
  2. Shortest Path Finder - Implement Dijkstra’s Algorithm to find the shortest path.
  3. Seam Finding - Implement the logic behind seam carving using two different techniques.
  4. Dynamic Programming Implementation