CSCI 4041 Algorithms and Data Structures - Spring 2025

Homework 5 - Greedy and Graph Algorithms

Due Date: Friday, May 2, 2025 by 11:59pm.

Instructions: This is an individual homework assignment. You may work together to discuss con- cepts, but the solutions must be your own work.  Submit your answers on Canvas, which is linked to Gradescope (be sure to correctly map the page for each problem).  This assignment is divided into two parts.  Part  A focuses on written problems involving greedy algorithms and graphs.  Part B involves route mapping using a drone visualization.

Part A - Greedy and Graph Algorithms (Written Problems)

Problem H5.1: Greedy Strategy (20 points)

Suppose you are given a set of n x-intervals with distinct lengths w1 , w2,..., wn , and n y-intervals with distinct heights h1 , h2,..., hn.  Matching an x-interval with a y-interval will define a rectangle. For example, matching the ith x-interval and the jth y-interval gives a rectangle of width wi  and height hj . You want to match each x-interval with one of the y-intervals such that the sum of the areas of the resulting rectangles is maximized.  More specifically, suppose you can rearrange both lists however you want. You want to rearrange them so as to maximize Σn i=1 wi hi. Briefly describe a greedy strategy for doing this, and rigorously prove that your strategy works.

Problem H5.2: Matrix-Chain Multiplication (20 points)

Assume you have the following set of matrix multiplications:

A1 A2 A3...An

Where Ai  is a matrix of dimension pi- 1  × pi  defined by the dimension vector p =< p0 , p1 , ..., pn > as detailed in Section 14.2. We want to minimize the number of arithmetic operations by determining a parenthesization for matrix multiplication order.

Prove or disprove each proposed greedy strategy below:

(a)  For each recursive step, find a pair of matrix multiplications that has the smallest number of scalar multiplications (e.g.  Choose Ai Ai+ 1  where pi- 1pipi+ 1  is the smallest).  Multiply these two matrices first, creating the subproblem A1...M...An , where Mpi-1 ×pi+1    = Ai Ai+ 1 .

(b)  For each recursive step, find a pairwise multiplication that has the largest number of scalar multiplications.  Add parenthesis to create a multiplication split between those two matrices. For example, if AkAk + 1  requires the most scalar multiplications, we split A1 A2...AkAk + 1...An into (A1 A2...Ak )(Ak + 1...An ).

Problem H5.3: Fastest Path (20 points)

A graph of a road system is given by the following adjacency matrix of speed limits.

Note:

• If there is no direct route, the speed limit is 0.

•  Some roads are one-way, and even if they are two-way, the speed limits for different directions may differ.

Answer the following questions:

(a)  Draw the graph.

(b)  The chart below describes the distances between points.

Find the fastest path from the“source” node D to every other node in the graph. The fastest path is the path that takes the least amount of time to reach your destination.  Record both the path and the shortest time. Briefly explain your approach and show your work.

Path                                                                     Shortest Time

D to A:

D to B:

D to C:

D to E:

Part B - Graph Algorithms (Programming Problem) Problem H5.4: Route Mapping (40 points + 5 points possible extra credit)

Figure 1 - Route mapping using a drone visualization.

Instructions: You are to implement several graph algorithms and test them on a drone visualization system.

Submission: Submit the search algorithms .py file to the Homework 5 - Part B Grade- scope assignment.

Setup:

• Download the support code from Canvas: hw5-support-code.zip

• Install python dependencies:

— pip3  install  flask

— pip3  install  flask cors

•  Run the application

— Use a terminal to cd to visualization code directory and run the visualization:

* python3  app.py

— Navigate to http://127.0.0.1:5000

Drone Visualization

The drone visualization allows you to move a robot across the UMN. As soon as the robot moves, the drone will attempt to find the robot and move to its location.  Figure 2 shows how to move the robot, Figure 3 shows a control panel where you can choose whether to view the robot or drone. You can also choose the algorithm you would like to use to move towards the robot.

Three simple algorithms already exist to help you get started:

• Point to Point: Moves the drone directly from one point to another.

• Fly: Uses a parabolic arc to fly from one point to another.

• Random Graph: Flies to a random point on the map and then follows a graph to the robot. Figure 3 shows this algorithm in action.

Figure 2 - Click to move the robot and route the drone.

Figure 3 - Interface for choosing the algorithms for the drone to use to find the robot.

Figure 4 - The drone follows a path on a graph to find the robot.

Task / Rubric

The search algorithms .py file has a simple graph implementation and a set of graph al- gorithms for you to implement. You will do all your work in the search algorithms .py file. You should not need to touch the visualization code.  Your task is to implement a subset of the following algorithms to reach 40 points (5 points extra credit possible):

• Breadth First Search

— (10 points) - breadth first(start,  dest) - Breadth First Search.

— (5 points) - breadth first hub(start,  dest) - Every node with 5 or more neigh- bors is considered a hub. Calculate the top three hubs that are closest to both the start and destination using Euclidean distance.   Use the breadth first algorithm to visit each hub before reaching the destination (visit hubs in order of decreasing distance from the destination - furthest to closest).

• Depth First Search

— (10 points) - depth first(start,  dest) - Depth First Search.

— (5 points) - depth first best(start,  dest) - Perform the depth first search, but when choosing an edge to follow, always choose the edge that leads to a node that is closest to the goal (e.g. has the shortest Euclidean Distance).

• Bellman Ford

— (10 points) - bellman ford(start,  dest) - Bellman Ford Algorithm.

— (5 points) - bellman ford negative(start,  dest) (5 points) - When calculating the weights of neighbors, if the neighbor node name ends with a 0, then it has a negative weight. Use Bellman Ford to find the path to the destination. If no path is found, use point to point navigation.

• Dijkstra / A*

— (10 points) - dijkstra(start,  dest) - Dijkstra’s Algorithm.

— (5 points) - astar(start,  dest) - A* algorithm using Euclidean Distance as the heuristic.

• Minimum Spanning Tree

— (10 points) - min spanning tree(start,  dest) - Calculate and follow the path on a minimum spanning tree to the destination.

For each algorithm, you will take in a start point (3D point) and a destination point (3D point) to write an algorithm that returns a path (list of 3D points) on a graph for the drone to follow. You may calculate the weight of each edge using the Euclidian distance between nodes.

Please look at the random graph(start,  dest) function to understand how to use the graph.  You can create a graph with the following line of code:  graph  =  MapGraph(‘graph.json’).  You may add / edit any structure within the search algorithms.py file including the MapGraph class

Note: The  start  and  destination  points  passed  in  are  3D  points,  not  nodes  in the  graph. Therefore, for each search algorithm, you will first need to find the closest start and destination nodes in the graph. You can use the following method: graph.find closest vertex(point).