Comp 251: Assignment 3
Instructor: Jérôme Waldispühl Due on November 20th at 11:55:00 pm
General instructions (Read carefully!)
• Your solution must be submitted electronically on MyCourses.
• To some extent, collaborations are allowed. These collaborations should not go as far as sharing code or giving away the answer. You must indicate on your assignments (i.e. as a comment at the beginning of your java source file) the names of the people with whom you collaborated or discussed your assignments (including members of the course staff). If you did not collaborate with anyone, you write “No collaborators”. If asked, you should be able to orally explain your solution to a member of the course staff.
• This assignment is due on November 20th at 11h55:00 pm. It is your responsibility to guarantee that your assignment is submitted on time. We do not cover technical issues or unexpected difficulties you may encounter. Last minute submissions are at your own risk.
• This assignment will be submitted in two components. The programming component, worth 50 points, will be submitted in the HW3 – Programming submission folder. The long answer component, worth 50 points, will be submitted in the HW3 – Long Answer submission folder. Make sure you submit in the right folder.
• Multiple submissions are allowed before the deadline. We will only grade the last submitted file. Therefore, we encourage you to submit as early as possible a preliminary version of your solution to avoid any last minute issue.
• Late submissions can be submitted for 24 hours after the deadline, and will receive a flat penalty of 20%. We will not accept any submission more than 24 hours after the deadline. The submission site will be closed, and there will be no exceptions, except medical.
• Violation of any of the rules above may result in penalties or even absence of grading. If anything is unclear, it is up to you to clarify it by asking either directly the course staff
1
during office hours, by email at (cs251@cs.mcgill.ca) or on the discussion board on Reddit (recommended). Please, note that we reserve the right to make specific/targeted announcements affecting/extending these rules in class and/or on the website. It is your responsibility to monitor the course website and MyCourses for announcements.
Programming component
• Add your code only where you are instructed to do so. You can add some helper methods in the classes you are asked to modify. Do not modify the code in any other way and in particular, do not change the methods or constructors that are already given to you, do not import extra code and do not touch the method headers. Any failure to comply with these rules will result in an automatic 0.
• The starter code includes a tester class. If your code fails those tests, it means that there is a mistake somewhere. We will grade your code with a more challenging set of examples. We therefore highly encourage you to modify that tester class, expand it and share it with other students on the discussion board. Do not include it in your submission.
• Your code should be properly commented and indented.
• Do not change or alter the name of the files you must submit. Files with
the wrong name will not be graded. Make sure you are not changing file names by duplicating them. For example, main (2).java will not be graded. Make sure to double- check your zip file.
• In order to receive a grade for the programming part of the assignment, you must submit all components of the programming assignments. Doing only one of the three questions would be met with a grade of zero.
Long Answer component
• The long answer is divided into several components. Please clearly separate the sections in your solution. Presentation points will be granted to full solutions that are correctly presented. A solution is considered correctly presented when it is:
1. Written with a text editing software with equation formatting like LATEX. Unfor- matted equations like (3(x+5)+5)/(3x+4) will not be graded.
2. If written by hand, scanned with a correctly functioning scanner with sufficient contrast to be easily readable. Pictures of assignments will not be graded.
3. Clean looking, with no crossed out regions or ink/eraser smearing.
• Be brief and to the point in the solution to the long answer questions. You will be provided with the maximum number of words (not including equations) your solution should contain. You can skip all the information that is already provided in the task description and start immediately with the first step of your solution. Show your work.
COMP 251 – HW3 Page 2 of 5 Fall 2019
1. (25 points) Ford-Fulkerson
We will implement the Ford-Fulkerson algorithm to calculate the Maximum Flow of a di- rected weighted graph. Here, you will use the files WGraph.java and FordFulkerson.java, which are available on the course website. Your role will be to complete two methods in
the template FordFulkerson.java.
The file WGraph.java is similar to the file that you used in your previous assignment to
build graphs. The only differences are the addition of setter and getter methods for the Edges and the addition of the parameters “source” and “destination”. There is also an additional constructor that will allow the creation of a graph cloning a WGraph object. Graphs are encoded using a similar format than the one used in the previous assignment.
The only difference is that now the first line corresponds to two integers, separated by
one space, that represent the “source” and the “destination” nodes. An example of such
file can be found on the course website in the file ff2.txt. These files will be used
as an input in the program FordFulkerson.java to initialize the graphs. This graph corresponds to the same graph depicted in [CLRS2009] page 727.
Your task will be to complete the two static methods fordfulkerson(Integer source, Integer destination, WGraph graph, String filePath)andpathDFS(Integer source, Integer destination, WGraph graph). The second method pathDFS finds a path
via Depth First Search (DFS) between the nodes “source” and “destination” in the “graph”. You must return an ArrayList of Integers with the list of unique nodes be- longing to the path found by the DFS. The first element in the list must correspond to
the “source” node, the second element in the list must be the second node in the path,
and so on until the last element (i.e., the “destination” node) is stored. The method fordfulkerson must compute an integer corresponding to the max flow of the “graph”,
as well as the graph encoding the assignment associated with this max flow. The method fordfulkerson has a variable called myMcGillID, which must be initialized with your McGill ID number.
Oncecompleted,compileallthejavafilesandrunthecommandlinejava FordFulkerson ff2.txt. Your program must use the function writeAnswer to save your output in a file.
An example of the expected output file is available in the file ff226000000.txt. This output keeps the same format than the file used to build the graph; the only difference
is that the first line now represents the maximum flow (instead of the “source” and “des- tination” nodes). The other lines represent the same graph with the weights updated
to the values that allow the maximum flow. The file ff226000000.txt represents the answer to the example showed in [CLRS2009] Page 727. You are invited to run other examples of your own to verify that your program is correct.
2. (25 points) Bellman-Ford
We want to implement the Bellman-Ford algorithm for finding the shortest path in a graph where edges can have negative weights. Once again, you will use the object WGraph. Your task is to complete the method BellmanFord(WGraph g, int source) and shortestPath(int destination) in the file BellmanFord.java.
The method BellmanFord takes an object WGraph named g as an input and an integer
COMP 251 – HW3 Page 3 of 5 Fall 2019
that indicates the source of the paths. If the input graph g contains a negative cycle, then the method should throw an exception (see template). Otherwise, it will return an object BellmanFord that contains the shortest path estimates (the private array of integers distances), and for each node, its predecessor in the shortest path from the source (the private array of integers predecessors).
The method shortestPath will return the list of nodes as an array of integers along the shortest path from the source to the destination. If this path does not exists, the method should throw an exception (see template).
Input graphs are available on the course webpage to test your program. Nonetheless, we invite you to also make your own graphs to test your program.
3. (50 points) Knapsack Problem
We have seen in class the Knapsack problem and a dynamic programming algorithm. One could define the Knapsack problem as following:
Definition. Let n > 0 be the number of distinct items and W > 0 be the knapsack capacity. For each item i, wi > 0 denotes the item weight and vi > 0 denotes its value. The goal is to maximize the total value
while
where xi ∈ {0,1} for i ∈ {1,…,n}.
n vixi i=1
n
wixi ≤W i=1
Algorithm. We recall the recursive form of the dynamic programming algorithm. Let OPT(i,w) be the maximum profit subset of items 1,…,i with weight limit w. If OP T does not select the item i, then OP T selects among items {1, . . . , i−1} with weight limit w. Otherwise, OP T selects among items {1, . . . , i − 1} with weight limit w. We could formalize as
0 OPT(i,w)=OPT(i−1,w)
max{OPT(i−1,w),vi +OPT(i−1,w−wi)}
if i = 0 ifwi >w otherwise
COMP 251 – HW3 Page 4 of 5
Fall 2019
Correctness of dynamic programming algorithm (30)
Usually, a dynamic programming algorithm can be seen as a recursion and proof by induction is one of the easiest way to show its correctness. The structure of a proof by strong induction for one variable, say n, contains three parts. First, we define the Proposition P(n) that we want to prove for the variable n. Next, we show that the proposition holds for Base case(s), such as n = 0, 1, . . . etc. Finally, in the Inductive step, we assume that P(n) holds for any value of n strictly smaller than n′, then we prove that P(n′) also holds.
Use the proof by strong induction properly to show that the algorithm of the Knapsack problem above is correct.
Bounded Knapsack Problem (20)
Let us consider a similar problem, in which each item i has ci > 0 copies (ci is an integer). Thus, xi is no longer a binary value, but a non-negative integer at most equal to ci, 0 ≤ xi ≤ ci. Modify the dynamic programming algorithm seen at class for this problem.
Note: One could consider a new set, in which item i has ci occurrences. Then, the algorithm seen as class can be applied. However, this could be costly since ci might be large. Therefore, the algorithm you propose should be different than this one.
Unbounded Knapsack Problem (10-bonus)
In this question, we consider the case where the quantity of each item is unlimited. Thus, xi could be any non-negative integer. Provide a dynamic programming algorithm for this problem.
COMP 251 – HW3 Page 5 of 5 Fall 2019