Answer To: I want you to fix this code. I'm having a problem with the output. It's supposed to be similar to...
Rushendra answered on Jul 03 2021
Description and files needed/(1) Description.pdf
1
(Priority Queue, Dijkstra’s Algorithm, and Union-Find)
1: Overview
We are going to:
● Use Priority Queue to solve a couple of problems
● Implement Dijkstra’s algorithm
● Implement a list-based Union-Find data structure
To this end, your task is to complete the following:
● complete the class in StudentComparator.java
● readStudents and readWeightedGraph methods in IOHelper class
● topK and kWayMerge methods in PriorityQueueApplications class
● the constructor and execute methods in Dijkstra class
● the constructor, makeSet, find, append, and doUnion methods in UnionFind class
The project also contains additional files (which you do not need to modify).
Use TestCorrectness.java to test your code.
Output is provided separately in the ExpectedOutput file. Should you want, you can use
www.diffchecker.com to tally the output.
2: Operations on Strings
Use str1.compareTo(str2) in Java to get the relative lexicographic (dictionary) rank of two strings
str1 and str2. If the function returns a negative value, then str1 is lexicographically smaller than
str2. If the function returns a positive value, then str1 is lexicographically larger than str2. If the
function returns 0, then str1 equals str2.
2
3: Dynamic Arrays
Here, you will use their Java implementations of dynamic arrays, which is named ArrayList.
Typically, we employ generics, whereby you can create arrays of
any type (and not just integer). I will describe integer dynamic arrays here; the syntax is
self-explanatory on how to extend to other types (such as char, string, or even objects of a
class).
• In Java, the syntax to create is ArrayList name = new ArrayList<>().
To obtain the size of the list, the syntax is name.size().
To add a number (say 15) at the end of the array list, the syntax is name.add(15).
To remove the last number, the syntax is name.remove(name.size() - 1).
To access the number at an index (say 4), the syntax is name.get(4).
To change the content of a particular index (say 4) to −99, the syntax is name.set(4, -99).
4: Generics & Comparators
In this assignment, you are going to use a priority queue to order comparable items. To this end,
you are going to use Java’s priority queue coupled with an appropriate comparator. The idea is
that you can create a priority queue of items of any sort (and not just integers), where an item
can be compared against another using a comparator. In one example, we will order integers in
the priority queue. In another example, we will order students, each having a name and a grade.
Students will be ordered first based on their grades, and in case of a tie, based on their names.
Thus, for the price of one priority queue, you can create two (and in fact, infinitely many by
just using an appropriate comparator). Question is how we use generics and comparators.
I’ll sketch the idea using Selection Sort; check the given GenericSelectionSort file. You need
to understand that to implement the priority queue by using pretty much the same concept; the
code has been reasonably commented to help you understand.
• The GenericSelectionSort class can sort any collection of items as long as they are
comparable. The class accepts the type of items that you want to sort as arguments, as
well as a comparator using which you will sort the items.
• To see how the comparator works, check StringComparator class. This method simply
returns a boolean an integer (in Java) obtained by comparing two strings – a negative
number (in Java) is returned if arg2 is lexicographically larger than arg1, else a
non-negative number (in Java) is returned.
• We compare the two objects using comparator.compare(currentValue, minValue) in JAVA.
This will return a negative number (in Java) if currentValue is smaller, else it will return us a
non-negative number (in Java). Notice the obliviousness of the selection sort method about
how the objects are compared. All it cares is that the objects are comparable, and
presumes that the comparator is correct.
3
5: Priority Queue
You will use the in-built PriorityQueue class in Java. The priority queue contains objects of a
class, which has been equipped with a comparator. I am going to use Element class as an
example. Thus, the priority queue will contain objects of the Element class. To use the priority
queue, we need to provide it with a comparator using which we can compare two objects of the
Element class in the priority queue. Here, I will use the ElementComparator as an example. Let’s
now look at some of the syntaxes:
Java
• To create: PriorityQueue pq = new PriorityQueue<>(new ElementComparator());
• To get the size: pq.size();
• To insert an object ele of the Element class: pq.add(ele);
• To read the topmost/minimum element: Element ele = heap.peek();
To remove the topmost/minimum element: heap.remove();
For usages, check the GenericHeapSort class that sorts an array of integers using a priority
queue. The code has been lightly commented to aid you. Over here, our Element class is the
PriorityQueuePair class, which has two members: an item and a priority; the constructor first
accepts an item and then its priority.1 Notice how we create an object of the PriorityQueuePair
class and then insert the object into the priority queue.2 Since we only care about sorting
integers, both item and priority are the numbers in the array itself. The comparison is being
carried out by the PriorityQueuePairComparator; since we just compare two integers, we return a
negative number (in Java) only when the second number is larger.
Similarly, we demonstrate how to sort strings and students using StringComparator and
StudentComparator. Notice the way priority queues are created, the choice of comparators, and
how the various operations are used. You’ll need them in the next few problems.
4
6: Finding k-most important items
In many scenarios, we are interested to find the top-k numbers (i.e., the k highest numbers) from
a given set of numbers. This is has numerous applications related to web searching (such as
the 10
__________________________________________
1 Although ideally one would use a generic item and possibly a generic priority as well, since it will suffice our
purposes, to keep things simple, both items and priorities are integers in the implementation here.
2 We don’t need to sort integers using another class, but this structure will make it easier for other problems.
most relevant websites for a Google search, or the 20 most popular items for an Amazon
search). The obvious way to do this would be to first sort the array, and then report the last k
numbers in the sorted array. This, however, has a complexity of O(n log n), where the length of
the array is n. Typically, k is much smaller than n; hence, we want to design an algorithm that is
faster for smaller values of k (such as when k is a constant), but no slower than sorting for larger
values of k (such as when k approaches n).
Specifically, our goal is to design an algorithm that can find the k largest items in an array of n
items, where each item can be compared to another based on some criteria. Our algorithm will
achieve a complexity of O(n log k) time, assuming any two items can be compared in O(1) time (if
that’s not the case, we have to multiply the time needed to compare two items).
The main idea is as follows. Note that we need the k largest items, and the complexity has a
log k factor; so, immediately, you can guess that the size of the priority queue should not exceed
k. So, we insert the first k items in the array into the priority queue. Now, think of the next item in
the array; if it is larger than the smallest in the priority queue, then the smallest in the priority
queue cannot be one of the k largest items. On the other hand, if the next item is smaller than
the smallest in the priority queue, then the next item cannot be one of the k largest items.
Therefore, either way we can discard one of them – in the first case, remove the minimum and
insert the next one, whereas in the second case, ignore the next one. Keep doing this for the
remaining items in the array. At the end, the items left in the priority queue form the k largest.
Use the following pseudo-code and complete the topK method of the
PriorityQueueApplications.java file, which finds the k-largest items and returns them in an array.
Note that you must achieve the claimed complexity (OR ELSE I WILL GET A REFUND) . Here, the
items are objects of the Student class, and they will be compared using the StudentComparator. Our
first task is to read the students into a dynamic array.
Read Students
Complete the readStudents method in the IOHelper class. This method will read the
student at the given filepath into a dynamic array (ArrayList in Java) of type Student.
Then it will return the dynamic array.
The students.txt file has a student record in each line. Each record contains the
student’s name followed by the student’s grade, separated by a space.
5
Our next task is to compare students first based on their grades, and in case of a tie, based
on their names. You’ll complete the StudentComparator class as follows (do not deviate from the
structure given in StringComparator; usage of comparators needs the format given there):
Student Comparator in Java
Here’s how you compare Student arg1 and arg2:
• If arg1’s grade does not equal arg2’s grade, return arg1’s grade – arg2’s
grade
• Otherwise, return the value obtained by comparing arg1’s name to arg2’s
name
At this point, if these two methods are correctly written, you should be able to run all the
methods in the GenericSelectionSort and GenericHeapSort classes. It should give you the
output in the GenericSelectionSortOutput and GenericHeapSortOutput text files. If your output
matches, then you have likely written the methods correctly. So, it is recommended that this
works before you proceed further.
topK
● If k is more than the size of students, then set k to the size of students
● Create a Student priority queue; use the StudentComparator in this case.
● Use a loop to insert the first k students into the priority queue.
● Create a StudentComparator object.
● for (i = k to i < size of students), do the following:
○ Let min be the topmost student in the priority queue (this is the student with the
minimum grade, ties broken by names)
○ Let current be the student at index i of students
○ Use the student comparator object to compare min and current.
Refer to the GenericSelectionSort class method sort for usage.
○ Using the comparator, if (min is smaller than current), then:
■ current has a higher grade than min; so, extract the topmost student
■ insert current into the heap
● Create a Student dynamic array (ArrayList in Java).
● At this point, the priority queue contains the top-k students. Extract the students in the
priority queue one by one, and add them into the dynamic array.
● Return the dynamic array.
6
7: Merge k-sorted Arrays
This method takes the following as arguments: k sorted arrays as a jagged array lists (i.e., each
row in the jagged array is a sorted dynamic array and there are k rows). The task is to return a
single merged sorted array – it contains all the numbers from all the rows in a sorted order. By
using a priority queue, we will solve this problem in O(N log k) time, where N is the total length of
all the rows together.
Since each array is sorted, note that the smallest is definitely one of the elements in cell 0 of
one of the arrays, say this array is A. The next smallest is either element at cell 1 of array A or
one of the elements in cell 0 of one of the arrays other than A. Thus, at each instance we are
required to find the smallest from one of the k arrays leaving out the elements that have already
been processed. We’ll see how a priority queue can be used to this end. Caution: Your code
must use a priority queue and it must attain the complexity mentioned here (OR ELSE I WILL
GET A FULL REFUND).
7
8: Dijkstra’s Algorithm
To test the correctness, I have included two sample files (dijkstra1.txt and dijkstra2.txt). Each .txt
file has the following format. First line is the number of vertices and edges respectively. Second
line onwards are the edges in the graph; in particular, each line contains three entries: the source
vertex, the destination vertex, and the weight of the edge.
The vertices in the graph are numbered 0 through n − 1, where n is the number of vertices.
We use a two-dimensional jagged array adjList (called adjacency list) to represent the graph.
Specifically, row index i in the array corresponds to the vertex vi, i.e., row 0 corresponds to v0,
row 1 corresponds to v1, and so on. Each cell in row i stores an outgoing edge of the vertex vi.
Each edge has 3 properties – src, dest, and weight, which are respectively the vertex from which
the edge originates, the vertex where the edge leads to, and the edge weight.
In a nutshell, Edge is a class which has three integer variables – src, dest, and weight. The
adjacency list, therefore, is a jagged array, whose type is Edge. In Java, we implement adjList as
an ArrayList of Edge ArrayLists.
8
Your first task is to read the files and create the graph as an adjacency list. Use the following
to complete the readWeightedGraph method in IOHelper.java file.
Reading weighted graph file
● Java: Create a Scanner object fileReader on filePath.
● Create a Graph object named graph
● Read the number of vertices into the class-variable numVertices of the graph
object.
Allocate numVertices rows for the adjList class-variable of the graph object.
Moving forward whenever we talk about numVertices and adjList, we are referring to
these variables in the graph object.
● for (i = 0 to i < numVertices), do the following:
○ add a blank row to adjList.
● Read remaining lines of the file one at a time, and do the following:
○ declare three integer variables src, dest, and weight
○ use fileReader to read from the file into these 3 variables respectively
○ create an edge e by calling the Edge constructor with arguments src, dest,
and weight respectively
○ add the edge e to the row at index src in adjList
● After the loop, close fileReader.
● Return the graph object.
You have already seen Dijkstra’s algorithm in lecture notes – the core idea is to pick an open
vertex with the minimum distance label and relax its outgoing edges and close the vertex. So,
the main questions is how to keep track of open vertices, and how to find an open vertex with
minimum distance label....