Comp 251: Assignment 2
Answers must be submitted online by October 24rd 11:55:00 pm, 2019.
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 October 24rd 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 three components. The programming component, worth 60 points, will be submitted in the HW2Programming submission folder. The long answer component, worth 50 points including a bonus, will be submitted in the HW2Long 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.
In exceptional circumstances, we can grant a small extension of the deadline e.g. 24h for medical reasons only. However, such request must be submitted before the deadline, and justified by a medical note from a doctor, which must also be submitted to the McGill administration.
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 during office hours, by email at cs251cs.mcgill.ca or on the discussion board on Reddit recommended. Please, note that we reserve the right to make specifictargeted announcements affectingextending these rules in class andor on the website. It is your responsibility to monitor the course website and MyCourses for announcements.
1
The course staff will answer questions about the assignment during office hours or in the online forum. We urge you to ask your questions as early as possible. We cannot guarantee that questions asked less than 24h before the submission deadline will be answered in time. In particular, we will not answer individual emails about the assignment that are sent sent the day of the deadline.
Programming component
You are provided some starter code that you should fill in as requested. Add your code only where you are instructed to do so. You can add some helper methods. 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. The format that you see on the provided code is the only format accepted for programming questions. 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. Even if your code passes those tests, it may still contain some errors. 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 doublecheck your zip file.
In order to receive a grade for the programming part of the assignment, you must submit all com
ponents of the programming assignments. Doing only one of the three questions would be met
with a grade of zero.
Do not submit individual files. Include all your files into a .zip file and, when appropriate, answer
the complementary quiz online on MyCourses.
You will automatically get 0 if the files you submitted on MyCourses do not compile.
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. Unformatted equa tions like 3x553x4 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 inkeraser 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.
2
Exercise 1 Disjoint sets 15 points We want to implement a disjoint set data structure with union and find operations. The template for this program is available on the course website and named DisjointSets.java.
In this question, we model a partition of n elements with distinct integers ranging from 0 to n1 i.e. each element is represented by an integer in 0, ,n1, and each integer in 0, ,n1 represent one element. We choose to represent the disjoint sets with trees, and to implement the forest of trees with an array named par. More precisely, the value stored in pari is parent of the element i, and parii when i is the root of the tree and thus the representative of the disjoint set.
You will implement union by rank and the path compression technique seen in class. The rank is an integer associated with each node. Initially i.e. when the set contains one single object its value is 0. Union operations link the root of the tree with smaller rank to the root of the tree with larger rank. In the case where the rank of both trees is the same, the rank of the new root increases by 1. You can implement the rank with a specific array called rank that has been added to the template, or use the array par this is tricky. Note that path compression does not change the rank of a node.
Download the file DisjointSets.java, and complete the methods findint i as well as unionint i, int j. The constructor takes one argument n a strictly positive integer that indicates the number of elements in the partition, and initializes it by assigning a separate set to each element.
The method findint i will return the representative of the disjoint set that contains i do not forget to implement path compression here!. The method unionint i, int j will merge the set with smaller rank for instance i in the disjoint set with larger rank in that case j. In that case, the root of the tree containing i will become a child of the root of the tree containing j, and return the representative as an integer of the new merged set. Do not forget to update the ranks. In the case where the ranks are identical, you will merge i into j.
Once completed, compile and run the file DisjointSets.java. It should produce the output avail able in the file unionfind.txt available on the course website.
Note: You will need to complete this question to implement Question 2.
Exercise 2 Minimum Spanning trees 25 points We will implement the Kruskal algorithm to cal culate the minimum spanning tree MST of an undirected weighted graph. Here you will use the file DisjointSets.java completed in the previous question and two other files: WGraph.java and Kruskal.java available on the course website. You will need the classes DisjointSets and WGraph to execute Kruskal.java. Your role will be to complete two methods in the template Kruskal.java.
The file WGraph.java implements two classes WGraph and Edge. An Edge object stores all infor mations about edges i.e. the two vertices and the weight of the edge, which are used to build graphs. The class WGraph has two constructors WGraph and WGraphString file. The first one creates an empty graph and the second uses a file to initialize a graph. Graphs are encoded using the following format. The first line of this file is a single integer n that indicates the number of nodes in the graph. Each vertex is labelled with an number in 0, ,n1, and each integer in 0, ,n1 represents one and only one vertex. The following lines respect the syntax n1 n2 w, where n1 and n2 are integers representing the nodes connected by an edge, and w the weight of this edge. n1, n2, and w must be separated by spaces. An example of such file can be found on the course website with the file g1.txt. These files will be used as an input in the program Kruskal.java to initialize the graphs. Thus,anexampleofacommandlineisjava Kruskal g1.txt.
The class WGraph also provide a method addEdgeEdge e that adds an edge to a graph i.e. an object of this class. Another method listOfEdgesSorted allows you to access the list of edges
3
of a graph in the increasing order of their weight.
You task will be to complete the two static methods isSafeDisjointSets p, Edge e and kruskalWGraph g in Kruskal.java. The method isSafe considers a partition of the nodes p and an edge e, and should return True if it is safe to add the edge e to the MST, and False otherwise. The method kruskal will take a graph object of the class WGraph as an input, and return another WGraph object which will be the MST of the input graph.
Once completed, compile all the java files and run the command line java Kruskal g1.txt. An example of the expected output is available in the file mst1.txt. You are invited to run other examples of your own to verify that your program is correct.
Exercise3Greedyalgorithms20points Inthisexercise,youwillplanyourhomeworkwithagreedy algorithm. The input is a list of homeworks defined by two arrays: deadlines and weights the rela tive importance of the homework towards your final grade. These arrays have the same size and they contain integers between 1 and 100. The index of each entry in the arrays represents a single home work,forexample,Homework 2isdefinedasahomeworkwithdeadlinedeadlines2andweight weights2. Each homework takes exactly one hour to complete.
Your task is to output a homeworkPlan: an array of length equal to the last deadline. Each entry in the array represents a onehour timeslot, starting at 0 and ending at last deadline1. For each time slot, homeworkPlan indicates the homework which you plan to do during that slot. You can only complete a single homework in one 1hour slot. The homeworks are due at the beginning of a time slot, in other wordsifanassignmentsdeadlineisx,thenthelasttimeslotwhenyoucandoitisx1.Forexample, if the homework is due at t14, then you can complete it before or during the slot t13. If your solution planstodoHomework 2first,thenyoushouldhavehomeworkPlan02intheoutput.Notethat sometimes you will be given too much homework to complete in time, and that is okay.
Your homework plan should maximize the sum of the weights of completed assignments.
To organize your schedule, we give you a class HWSched.java, which defines an Assignment object, with a number its index in the input array, a weight and a deadline. In addition, we provide you the file GreedyTester.java that demonstrates how to use this class to initialize an ArrayList of homework objects of the appropriate size.
The input arrays are unsorted. As part of the greedy algorithm, the template we provide sorts the homeworks using Javas Collections.sort. This sort function uses Javas compare method, which takes two objects as input, compares them, and outputs the order they should appear in. The template will ask you to override this compare method, which will alter the way in which Assignments will be ordered. You have to determine what comparison criterion you want to use. Given two assignments A1 and A2, the method should output:
0, if the two items are equivalent
1, if a1 should appear after a2 in the sorted list1, if a2 should appear after a1 in the sorted list
The compare method called by Collections.sort should be the only tool you use to re organize lists and arrays in this problem. You will then implement the rest of the SelectAssignments method.
Submit all the Java files you modified in this assignment, in a single zip file, on the HW2Programming Folder on MyCourses.
4
Exercise 4 ChangeMaking Problem 50 points In this problem, we give a formal look at the prob lem of returning a given amount of money using the minimum number of coins including bills, for a given coin system.
For example, the best way to give someone 7 dollars is to add up a 5 dollars bill and a 2 dollars coin. For simplicity, we will consider all denominations to be coins.
First, let us define the problem: a coin system is a mtuple cc1,c2,,cm such that c1c2cm1. For a given coin system c and a positive integer x representing the amount of money we want to gather, we want to find a solution a mtuple of nonnegative integers kk1, k2, . . . , km such that xmi1 kici so as to minimize mi1 ki.
There exists a greedy algorithm to find the optimal solution for certain coin systems: for a given x, we select the largest coin cix. Then, we repeat this step for xci, and continue repeating it until x becomes 0. For instance, with the coin system 10, 5, 2, 1, the algorithm decomposes x27 into 10, 10, 5, and 2.
We describe a coin system as canonical if and only if the solution given by the greedy algorithm described above is optimal for any positive integer x. For example, all systems a, 1 with a1 are canonical. For any positive integer x, we can express such a change system in the form of Euclidean division: xaqr with ra. The greedy solution for x is then the tuple gq, r. To prove that the solution is optimal, we can proceed as follows:
Lets consider gq, r different than g such that xaqr. Because q is already at its highest value under x and cannot be above x, we have qq, otherwise qq causes gg. Since qrqrqxaqqxaqa1qq0,g wouldsumuptomorecoins than the initial solution g, for any g satisfying the problem definition. Thus, the solution g is optimal, and the system a, 1 is canonical.
4.1 15 points Design a noncanonical system of 3tuple cc1,c2,c3 and prove your system is noncanonical.
4.2 25 points Let q and n be two integers2. Prove that the system cqn,qn1,,q,1 is canonical.
4.3 10 bonus points Prove that the Euro system c200, 100, 50, 20, 10, 5, 2, 1 is canonical. There will be no partial credit for this question.
5
Reviews
There are no reviews yet.