Description

ALGORITHMS AND DATA STRUCTURES (CH08-320201)
Prof. Dr. Michael Sedlmair
Computer Science & Electrical Engineering
Submission Format
Please respect the submission format we are giving you in this homework exercise. Grading will be done on an automated basis (except for proofs which we will inspect manually). If you do not respect the submission format, your homework will be graded with 0%. You will be asked to submit a zip file on Moodle. This zip file should contain the following file structure (no subfolders and respect the exact filenames):
submission.zip
– problem1.pdf
– problem2.py | problem2.cpp
– bonus.pdf
5- problem3.py | problem3.cpp
– problem4.py | problem4.cpp & problem4.h
– problem4.pdf
Problem 1: Shortest Path Algorithm (3 points) Your friend (who hasn’t taken this course) asks you for help on implementing an algorithm for finding the shortest path between two nodes u and v in a directed graph (possibly containing negative edge weights). She proposes the following algorithm:
1. Add a large constant to each edge weight such that all weights become positive.
2. Run Dijkstra’s algorithm for the shortest path from u to v.
Prove or disprove the correctness of this algorithm to find the shortest path (note that in order to disprove, you only need to give a counterexample).
Problem 2: Optimal Meeting Point (7 points)
You are given a graph G with nodes V = {0,…,n −1} that represent the cities and edges E that represent streets connecting the cities directly. The edges are with the distance d(e), which is the time needed to travel from between two cities. You are given your own city p and your friend’s city q with p,q ∈{0,..,n −1}.
Implement an algorithm that finds the target city m in which you and your friend should meet in order to minimize travel time for both of you (you drive towards your meeting city simultaneously so if you travel for x minutes and your friend travels for y minutes, then you will want to minimize max(x,y)). The graph is given to you with an adjacency matrix, where each entry xij represents the time (in minutes) that it takes to travel from city i to city j. Naturally, the indices are the nodes. The algorithm should return the target city m ∈{0,.,n −1}. int find_meetup_city(int[][] adj_matrix, int your_city, int friend_city);
Problem 3: A Picking Order (3*+4 points)
(a) BONUS Prove that any set of n students can be arranged in a line such that every student picks on the student immediately to its right.
int[] picking_order(bool[][] adj_matrix);
Problem 4: Number Maze (2+4+4 = 8 points)
(a) Represent the problem as a graph problem. Formalize it by determining what is represented as the nodes and as the edges.
(b) Implement the class PuzzleBoard, as shown below.
(c) Implement an algorithm that returns the minimum number of moves required to solve this problem. If there is no solution, your algorithm should say so.
class PuzzleBoard { private:
// up to you. public:
5// Problem 1b)
PuzzleBoard(int boardSize, int[][] fields = null); // constructor should create the graph (as you defined it in 1a) with the values from fields. If fields is null, then initialize the fields of the board with random values between 1 and boardSize-1.
Bool makeMove(int direction); // makes the move (if valid), direction is 0 for up, 1 for right, 2 for down, 3 for left. Returns true if the move was valid, false otherwise.
Bool getResult(); // Returns false if game is not over yet, true if puzzle was solved std::ostream &operator<<(std::ostream &os, PuzzleBoard const &m); // in python, this is the __str__ method.
10
// Problem 1c)
int solve(); // returns the minimum number of moves needed to solve the puzzle, and -1 if it’s not solvable.
}
Listing 1: Methods and classes to implement for the PuzzleBoard class.
2
Remarks
• You need to upload the files specified in the problem statements. The PDF file solution detailed.pdf can contain the solutions for your entire homework. Programming assignments need to be handed in as Python code (if you want to use C++ please talk to the TAs). Please write your own code. It is ok to take snippets from online resources, but they need to be clearly marked.
• Exercises marked with a * are bonus problems. These count towards your number of points for this homework. The maximum number of official points can not be exceeded.
3