This is a data structures assignment that uses java. The description and the needed files attached, This needs to be unique/original.
Description and files needed/dijkstra2.txt 7 0 1 10 0 4 1 1 2 0 1 3 5 2 3 2 3 0 3 3 4 17 3 6 7 4 5 7 6 5 2 Description and files needed/HeapSortOutput.txt *** Integer Heap Sort *** Original array: [360, 448, 29, 447, 15, 53, 491, 261, 219, 354] After sorting: [15, 29, 53, 219, 261, 354, 360, 447, 448, 491] *** String Heap Sort *** Original array: [abc, def, abcd, bce, abx, acfe, bfr, xyz, de, tyu, ab, abcd, xy, zxy, abx, def] After sorting: [ab, abc, abcd, abcd, abx, abx, acfe, bce, bfr, de, def, def, tyu, xy, xyz, zxy] *** Student Heap Sort *** Original Order: [(B, 88), (I, 77), (K, 77), (D, 87), (E, 83), (J, 88), (F, 78), (G, 93), (H, 91), (C, 77), (A, 78)] After Sorting: [(C, 77), (I, 77), (K, 77), (A, 78), (F, 78), (E, 83), (D, 87), (B, 88), (J, 88), (H, 91), (G, 93)] Description and files needed/UnionFind.java Description and files needed/UnionFind.java import java.util.ArrayList; public class UnionFind { private ArrayList<>
> representatives; public UnionFind(int initialNumSets) { // complete this constructor } public void makeSet(int x) { // complete this method } public ArrayList find(int x) { // complete this method } private void append(ArrayList arg1, ArrayList arg2) { // complete this method } public void doUnion(int x, int y) { // complete this method } } Description and files needed/GenericHeapSort.java Description and files needed/GenericHeapSort.java import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; public class GenericHeapSort { public static void sort(int[] arr, int len) { // creates a priority queue using the PriorityQueueComparator PriorityQueue heap = new PriorityQueue<>(new PriorityQueuePairComparator()); for (int i = 0; i < len; i++) heap.add(new priorityqueuepair(arr[i], arr[i])); // for plain heap sort, item and priority is the same;="" int i =" 0;" while (heap.size() =""> 0) { // as long as the heap is not empty PriorityQueuePair ele = heap.peek(); // get the topmost item heap.remove(); // remove the topmost item arr[i++] = ele.item; // could also use ele.priority } } public static void sort(String[] arr, int len) { // creates a priority queue using the StringComparator PriorityQueue heap = new PriorityQueue<>(new StringComparator()); for (int i = 0; i < len; i++) heap.add(arr[i]);="" int i =" 0;" while (heap.size() =""> 0) { // as long as the heap is not empty String ele = heap.peek(); // get the topmost item heap.remove(); // remove the topmost item arr[i++] = ele; } } private static void sortStudents() throws FileNotFoundException { System.out.println("\n*** Student Heap Sort ***\n"); ArrayList students = IOHelper.readStudents("students.txt"); System.out.println("Original Order: " + students); // creates a priority queue using the StudentComparator PriorityQueue heap = new PriorityQueue<>(new StudentComparator()); for (int i = 0; i < students.size(); i++) heap.add(students.get(i));=""> sortedStudents = new ArrayList<>(); while (heap.size() > 0) { // as long as the heap is not empty Student ele = heap.peek(); // get the topmost item heap.remove(); // remove the topmost item sortedStudents.add(ele); } System.out.println("After Sorting: " + sortedStudents); } static void stringSort() { System.out.println("\n*** String Heap Sort ***\n"); String arr[] = { "abc", "def", "abcd", "bce", "abx", "acfe", "bfr", "xyz", "de", "tyu", "ab", "abcd", "xy", "zxy", "abx", "def" }; System.out.println("Original array: " + Arrays.toString(arr)); sort(arr, arr.length); System.out.println("After sorting: " + Arrays.toString(arr)); } static void integerSort() { System.out.println("*** Integer Heap Sort ***\n"); int[] arr = {360, 448, 29, 447, 15, 53, 491, 261, 219, 354}; System.out.println("Original array: " + Arrays.toString(arr)); sort(arr, arr.length); System.out.println("After sorting: " + Arrays.toString(arr)); } public static void main(String[] args) throws FileNotFoundException { integerSort(); stringSort(); sortStudents(); } } Description and files needed/GenericSelectionSortOutput.txt *** String Selection Sort *** Original Order: abc def abcd bce abx acfe bfr xyz de tyu ab abcd xy zxy abx def After Sorting: ab abc abcd abcd abx abx acfe bce bfr de def def tyu xy xyz zxy *** Student Selection Sort *** Original Order: (B, 88) (I, 77) (K, 77) (D, 87) (E, 83) (J, 88) (F, 78) (G, 93) (H, 91) (C, 77) (A, 78) After Sorting: (C, 77) (I, 77) (K, 77) (A, 78) (F, 78) (E, 83) (D, 87) (B, 88) (J, 88) (H, 91) (G, 93) Description and files needed/PriorityQueueApplications.java Description and files needed/PriorityQueueApplications.java import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; public class PriorityQueueApplications { public static ArrayList topK(ArrayList students, int k) { // complete this method } public static ArrayList kWayMerge(ArrayList<>> lists) { // complete this method } } Description and files needed/PriorityQueuePairComparator.java Description and files needed/PriorityQueuePairComparator.java import java.util.Comparator; public class PriorityQueuePairComparator implements Comparator { @Override public int compare(PriorityQueuePair o1, PriorityQueuePair o2) { return o1.priority - o2.priority; } } Description and files needed/StudentComparator.java Description and files needed/StudentComparator.java import java.util.Comparator; public class StudentComparator implements Comparator { // complete this class } Description and files needed/dijkstra1.txt 7 0 1 10 0 3 3 0 4 7 1 2 0 1 3 5 2 0 17 3 2 17 3 4 2 3 6 7 5 4 3 5 6 2 Description and files needed/GenericSelectionSort.java Description and files needed/GenericSelectionSort.java import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Comparator; public class GenericSelectionSort { // A generic class for selection sorting comparable objects Comparator comparator; // This is used to compare the objects of the class GenericSelectionSort(Comparator comparator) { // Constructor will set the comparator for the specific class this.comparator = comparator; } public void sort(ArrayList content) { for (int i = 0; i < content.size() - 1; i++) { int minindex =" i;" for (int j ="">< content.size(); j++) { t minvalue =" content.get(minIndex); // get the reference to the object at minIndex" t currentvalue =" content.get(j); // get the reference to the object at j">< 0) { this checks if currentvalue is smaller than minvalue="">< 0 implies currentvalue is smaller than minvalue // =" 0 means they are the same" // =""> 0 means currentValue is larger than minValue minIndex = j; } } // swap contents T temp = content.get(minIndex); content.set(minIndex, content.get(i)); content.set(i, temp); } } private static void stringSort() { System.out.println("*** String Selection Sort ***\n"); String arr[] = { "abc", "def", "abcd", "bce", "abx", "acfe", "bfr", "xyz", "de", "tyu", "ab", "abcd", "xy", "zxy", "abx", "def" }; ArrayList strings = new ArrayList(); for (String str : arr) strings.add(str); GenericSelectionSort stringSelectionSort = new GenericSelectionSort<>(new StringComparator()); System.out.print("Original Order: "); for (String str : strings) System.out.print(str + " "); stringSelectionSort.sort(strings); System.out.print("\nAfter Sorting: "); for (String str : strings) System.out.print(str + " "); System.out.println("\n"); } private static void studentSort() throws FileNotFoundException { System.out.println("*** Student Selection Sort ***\n"); ArrayList students = IOHelper.readStudents("students.txt"); System.out.print("Original Order: "); for (Student student : students) System.out.print(student.toString() + " "); // Create selection sort instance for sorting Students using the StudentComparator GenericSelectionSort studentSelectionSort = new GenericSelectionSort<>(new StudentComparator()); studentSelectionSort.sort(students); System.out.print("\nAfter Sorting: "); for (Student student : students) System.out.print(student.toString() + " "); } public static void main(String[] args) throws FileNotFoundException { stringSort(); studentSort(); // this will work only if the StudentComparator and readStudents methods are complete. } } Description and files needed/StringComparator.java Description and files needed/StringComparator.java import java.util.Comparator; public class StringComparator implements Comparator { @Override public int compare(String arg1, String arg2) { return arg1.compareTo(arg2); } } Description and files needed/IOHelper.java Description and files needed/IOHelper.java import java.io.FileReader; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Scanner; public class IOHelper { public static ArrayList readStudents(String filePath) throws FileNotFoundException { // complete this method } public static Graph readWeightedGraph(String filePath) throws FileNotFoundException { // complete this method } } Description and files needed/PriorityQueuePair.java Description and files needed/PriorityQueuePair.java public class PriorityQueuePair { public int item; public int priority; public PriorityQueuePair(int item, int priority) { this.item = item; this.priority = priority; } } Description and files needed/TestCorrectness.java Description and files needed/TestCorrectness.java import java.util.ArrayList; import java.util.Arrays; public class TestCorrectness { static final String DIJKSTRA1 = "dijkstra1.txt"; static final String DIJKSTRA2 = "dijkstra2.txt"; static final String STUDENT = "students.txt"; private static ArrayList<>> arraysToLists(int[][] arrays, int arrayLengths[], int n) { ArrayList<>> lists = new ArrayList<>>(n); for (int i = 0; i < n; i++) {> list = new ArrayList(arrayLengths[i]); for (int j = 0; j < arraylengths[i]; j++) list.add(arrays[i][j]);="" lists.add(list);="" }="" return lists;="" }="" private static void testtopkelements() throws exception {="" system.out.println("*** test top-k ***\n");=""> students = IOHelper.readStudents(STUDENT); System.out.printf("Original Array: %s%n", students); ArrayList top3 = PriorityQueueApplications.topK(students, 3); ArrayList top7 = PriorityQueueApplications.topK(students, 7); ArrayList all = PriorityQueueApplications.topK(students, students.size()); System.out.print("Highest 3 students: " + top3); System.out.println(); System.out.print("Highest 7 students: " + top7); System.out.println(); System.out.printf("All students: " + all); } private static void testKSortedMerge() { System.out.println("\n\n*** Test Merging k Sorted Arrays ***\n"); int list0[] = { 1, 5, 9, 18 }; int list1[] = { -10, 5, 18, 67, 100 }; int list2[] = { -12, -9, -6, 0, 1, }; int list3[] = { -65, -32, 10, }; int list4[] = { 1, 19, 45, 67 }; int lists[][] = { list0, list1, list2, list3, list4 }; int k = lists.length; int eachListLength[] = new int[k]; for (int i = 0; i < k; i++) eachlistlength[i] =" lists[i].length;"> mergedList = PriorityQueueApplications.kWayMerge(arraysToLists(lists, eachListLength, k)); System.out.println("Original sorted arrays"); for (int i = 0; i < k; i++) system.out.println(arrays.tostring(lists[i]));="" system.out.println("\nfinal merged array: " + mergedlist + "\n");="" k =" 4;" eachlistlength =" new int[k];" for (int i ="">< k; i++) eachlistlength[i] =" lists[i].length;" mergedlist =" PriorityQueueApplications.kWayMerge(arraysToLists(lists, eachListLength, k));" system.out.println("original sorted arrays");="" for (int i ="">< k; i++) system.out.println(arrays.tostring(lists[i]));="" system.out.println("\nfinal merged array: " + mergedlist + "\n");="" k =" 2;" eachlistlength =" new int[k];" for (int i ="">< k; i++) eachlistlength[i] =" lists[i].length;" mergedlist =" PriorityQueueApplications.kWayMerge(arraysToLists(lists, eachListLength, k));" system.out.println("original sorted arrays");="" for (int i ="">< k; i++) system.out.println(arrays.tostring(lists[i]));="" system.out.println("\nfinal merged array: " + mergedlist + "\n");="" k =" 1;" eachlistlength =" new int[k];" for (int i ="">< k; i++) eachlistlength[i] =" lists[i].length;" mergedlist =" PriorityQueueApplications.kWayMerge(arraysToLists(lists, eachListLength, k));" system.out.println("original sorted arrays");="" for (int i ="">< k; i++) system.out.println(arrays.tostring(lists[i]));="" system.out.println("\nfinal merged array: " + mergedlist);="" }="" private static void testdijkstra() throws exception {="" string filepaths[] =" { DIJKSTRA1, DIJKSTRA2 };" for (int j ="">< filepaths.length; j++) { system.out.println("\n*** test dijkstra (" + filepaths[j] + ") ***");="" dijkstra dijk =" new Dijkstra(filePaths[j]);" for (int i ="">< dijk.numvertices; i++) { dijk.execute(i);="" system.out.println("\ndistance array (from v" + i + "): "="" + arrays.tostring(dijk.distance).replaceall("" + integer.max_value, "infty"));="" system.out.println("parent array (from v" + i + "): "="" + arrays.tostring(dijk.parent).replaceall("" + integer.max_value, "infty"));="" }="" }="" }="" private static void testunionfind() {="" system.out.println("\n****************** union find ******************\n");="" unionfind uf =" new UnionFind(16);" system.out.println("initial sets are 0-15\n");="" for (int i ="">< 15; i += 4) { system.out.printf("union(%d,%d)%n", i, i + 1);="" uf.dounion(i, i + 1);="" }="" system.out.println();="" for (int i ="">< 16; i++) { system.out.printf("list containing %2d: %s%n", i, uf.find(i));="" }="" system.out.println("\nunion(0,5)");="" system.out.println("union(10,12)");="" system.out.println("union(0,10)\n");="" uf.dounion(0, 5);="" uf.dounion(10, 12);="" uf.dounion(0, 10);="" for (int i ="">< 16; i++) { system.out.printf("list containing %2d: %s%n", i, uf.find(i));="" }="" system.out.println("\nunion(6,8)");="" system.out.println("union(8,5)\n");="" uf.dounion(6, 8);="" uf.dounion(8, 5);="" for (int i ="">< 16; i++) { system.out.printf("list containing %2d: %s%n", i, uf.find(i)); } } public static void main(string[] args) throws exception { testtopkelements(); testksortedmerge(); testdijkstra(); testunionfind(); } } description and files needed/edge.java description and files needed/edge.java public class edge { int src, dest, weight; public edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } public string tostring() { return string.format("<%d, %d, %d>", src, dest, weight); } } description and files needed/graph.java description and files needed/graph.java import java.util.arraylist; import java.util.list; public class graph { public int numvertices; public list> adjlist; } description and files needed/student.java description and files needed/student.java public class student { public string name; public int grade; public student(string name, int grade) { this.name = name; this.grade = grade; } public string tostring() { return string.format("(%s, %d)", name, grade); } } description and files needed/students.txt b 88 i 77 k 77 d 87 e 83 j 88 f 78 g 93 h 91 c 77 a 78 description and files needed/(2) expectedoutput.pdf *** test top-k *** original array: [(b, 88), (i, 77), (k, 77), (d, 87), (e, 83), (j, 88), (f, 78), (g, 93), (h, 91), (c, 77), (a, 78)] highest 3 students: [(j, 88), (h, 91), (g, 93)] highest 7 students: [(f, 78), (e, 83), (d, 87), (b, 88), (j, 88), (h, 91), (g, 93)] all students: [(c, 77), (i, 77), (k, 77), (a, 78), (f, 78), (e, 83), (d, 87), (b, 88), (j, 88), (h, 91), (g, 93)] *** test merging k sorted arrays *** original sorted arrays [1, 5, 9, 18] [-10, 5, 18, 67, 100] [-12, -9, -6, 0, 1] [-65, -32, 10] [1, 19, 45, 67] final merged array: [-65, -32, -12, -10, -9, -6, 0, 1, 1, 1, 5, 5, 9, 10, 18, 18, 19, 45, 67, 67, 100] original sorted arrays [1, 5, 9, 18] [-10, 5, 18, 67, 100] [-12, -9, -6, 0, 1] [-65, -32, 10] final merged array: [-65, -32, -12, -10, -9, -6, 0, 1, 1, 5, 5, 9, 10, 18, 18, 67, 100] original sorted arrays [1, 5, 9, 18] [-10, 5, 18, 67, 100] final merged array: [-10, 1, 5, 5, 9, 18, 18, 67, 100] original sorted arrays [1, 5, 9, 18] final merged array: [1, 5, 9, 18] *** test dijkstra (dijkstra1.txt) *** distance array (from v0): [0, 10, 10, 3, 5, infty, 10] parent array (from v0): [-1, 0, 1, 0, 3, -1, 3] distance array (from v1): [17, 0, 0, 5, 7, infty, 12] parent array (from v1): [2, -1, 1, 1, 3, -1, 3] distance array (from v2): [17, 27, 0, 20, 22, infty, 27] parent array (from v2): [2, 0, -1, 0, 3, -1, 3] distance array (from v3): [34, 44, 17, 0, 2, infty, 7] parent array (from v3): [2, 0, 3, -1, 3, -1, 3] distance array (from v4): [infty, infty, infty, infty, 0, infty, infty] parent array (from v4): [-1, -1, -1, -1, -1, -1, -1] distance array (from v5): [infty, infty, infty, infty, 3, 0, 2] parent array (from v5): [-1, -1, -1, -1, 5, -1, 5] distance array (from v6): [infty, infty, infty, infty, infty, infty, 0] parent array (from v6): [-1, -1, -1, -1, -1, -1, -1] *** test dijkstra (dijkstra2.txt) *** distance array (from v0): [0, 10, 10, 12, 1, 8, 19] parent array (from v0): [-1, 0, 1, 2, 0, 4, 3] distance array (from v1): [5, 0, 0, 2, 6, 11, 9] parent array (from v1): [3, -1, 1, 2 system.out.printf("list containing %2d: %s%n", i, uf.find(i));="" }="" }="" public static void main(string[] args) throws exception {="" testtopkelements();="" testksortedmerge();="" testdijkstra();="" testunionfind();="" }="" }="" description="" and="" files="" needed/edge.java="" description="" and="" files="" needed/edge.java="" public class edge {="" int src, dest, weight;="" public edge(int src, int dest, int weight) {="" this.src =" src;" this.dest =" dest;" this.weight =" weight;" }="" public string tostring() {="">", src, dest, weight); } } description and files needed/graph.java description and files needed/graph.java import java.util.arraylist; import java.util.list; public class graph { public int numvertices; public list> adjlist; } description and files needed/student.java description and files needed/student.java public class student { public string name; public int grade; public student(string name, int grade) { this.name = name; this.grade = grade; } public string tostring() { return string.format("(%s, %d)", name, grade); } } description and files needed/students.txt b 88 i 77 k 77 d 87 e 83 j 88 f 78 g 93 h 91 c 77 a 78 description and files needed/(2) expectedoutput.pdf *** test top-k *** original array: [(b, 88), (i, 77), (k, 77), (d, 87), (e, 83), (j, 88), (f, 78), (g, 93), (h, 91), (c, 77), (a, 78)] highest 3 students: [(j, 88), (h, 91), (g, 93)] highest 7 students: [(f, 78), (e, 83), (d, 87), (b, 88), (j, 88), (h, 91), (g, 93)] all students: [(c, 77), (i, 77), (k, 77), (a, 78), (f, 78), (e, 83), (d, 87), (b, 88), (j, 88), (h, 91), (g, 93)] *** test merging k sorted arrays *** original sorted arrays [1, 5, 9, 18] [-10, 5, 18, 67, 100] [-12, -9, -6, 0, 1] [-65, -32, 10] [1, 19, 45, 67] final merged array: [-65, -32, -12, -10, -9, -6, 0, 1, 1, 1, 5, 5, 9, 10, 18, 18, 19, 45, 67, 67, 100] original sorted arrays [1, 5, 9, 18] [-10, 5, 18, 67, 100] [-12, -9, -6, 0, 1] [-65, -32, 10] final merged array: [-65, -32, -12, -10, -9, -6, 0, 1, 1, 5, 5, 9, 10, 18, 18, 67, 100] original sorted arrays [1, 5, 9, 18] [-10, 5, 18, 67, 100] final merged array: [-10, 1, 5, 5, 9, 18, 18, 67, 100] original sorted arrays [1, 5, 9, 18] final merged array: [1, 5, 9, 18] *** test dijkstra (dijkstra1.txt) *** distance array (from v0): [0, 10, 10, 3, 5, infty, 10] parent array (from v0): [-1, 0, 1, 0, 3, -1, 3] distance array (from v1): [17, 0, 0, 5, 7, infty, 12] parent array (from v1): [2, -1, 1, 1, 3, -1, 3] distance array (from v2): [17, 27, 0, 20, 22, infty, 27] parent array (from v2): [2, 0, -1, 0, 3, -1, 3] distance array (from v3): [34, 44, 17, 0, 2, infty, 7] parent array (from v3): [2, 0, 3, -1, 3, -1, 3] distance array (from v4): [infty, infty, infty, infty, 0, infty, infty] parent array (from v4): [-1, -1, -1, -1, -1, -1, -1] distance array (from v5): [infty, infty, infty, infty, 3, 0, 2] parent array (from v5): [-1, -1, -1, -1, 5, -1, 5] distance array (from v6): [infty, infty, infty, infty, infty, infty, 0] parent array (from v6): [-1, -1, -1, -1, -1, -1, -1] *** test dijkstra (dijkstra2.txt) *** distance array (from v0): [0, 10, 10, 12, 1, 8, 19] parent array (from v0): [-1, 0, 1, 2, 0, 4, 3] distance array (from v1): [5, 0, 0, 2, 6, 11, 9] parent array (from v1): [3, -1, 1, 2>