Answer To: Description and files needed/BinarySearchApplications.java Description and files...
Nithin answered on Jun 01 2021
Description and files needed/out/production/Description and files needed/LinkedList.class
public synchronized class LinkedList {
public ListNode head;
public ListNode tail;
public int size;
public void LinkedList();
public void insertAfter(ListNode, int);
public void deleteAfter(ListNode);
public void selectionSort();
public boolean removeDuplicatesSorted();
public void pushOddIndexesToTheBack();
public void reverse();
ListNode insertAtFront(int);
ListNode insertAtEnd(int);
void deleteHead();
public ListNode getNodeAt(int);
void printList();
public int getSize();
}
Description and files needed/out/production/Description and files needed/BinarySearchApplications.class
public synchronized class BinarySearchApplications {
public void BinarySearchApplications();
public static int minIndexBinarySearch(int[], int, int, int, int);
public static int maxIndexBinarySearch(int[], int, int, int, int);
public static int countNumberOfKeys(int[], int, int);
public static int predecessor(int[], int, int);
public static int findPeak(int[], int);
public static int findPeak(int[], int, int, int);
}
Description and files needed/out/production/Description and files needed/TestCorrectness.class
public synchronized class TestCorrectness {
public void TestCorrectness();
public static void testBinarySearchMethods();
private static LinkedList part1LinkedList();
private static void part2LinkedList(LinkedList);
private static void testLinkedListCorrectness();
private static void testDynamicArrayCorrectness();
public static void main(String[]) throws Exception;
}
Description and files needed/out/production/Description and files needed/(2) ExpectedOutput.rtf
****************** Test Binary Search Applications Correctness ******************
*** Counting the number of occurrences of key ***
Array is [1, 1, 3, 7, 9, 14, 14, 14, 14, 14, 14, 18, 27, 39, 39, 39]
Number of occurrences of 1 is 2
Number of occurrences of 14 is 6
Number of occurrences of 39 is 3
Number of occurrences of 7 is 1
Number of occurrences of 100 is 0
Number of occurrences of -88 is 0
Number of occurrences of 16 is 0
*** Finding Predecessor ***
Array is [1, 1, 3, 7, 9, 14, 14, 14, 14, 14, 14, 18, 27, 39, 39, 39]
Predecessor of 1 is 1
Predecessor of 0 is not defined.
Predecessor of 39 is 39
Predecessor of 47 is 39
Predecessor of 36 is 27
Predecessor of 12 is 9
Predecessor of 6 is 3
*** Peak Finding ***
Array is [15, 18, 21, 25, 29, 31, 35, 23, 14, 9, 1, -1]. Max is at index 6
Array is [31, 35, 23, 14, 9, 1, -1]. Max is at index 1
Array is [31, 35, 37, 39]. Max is at index 3
Array is [36, 35, 32, 29]. Max is at index 0
****************** Test Linked List Correctness ******************
Inserting 5 at front. Current list: [5]
Inserting 32 at end. Current list: [5 -> 32]
Inserting 16 at front. Current list: [16 -> 5 -> 32]
Inserting 61 after position 1. Current list: [16 -> 5 -> 61 -> 32]
Inserting 99 after tail. Current list: [16 -> 5 -> 61 -> 32 -> 99]
Deleting after position 1. Current list: [16 -> 5 -> 32 -> 99]
Deleting after position 2. Current list: [16 -> 5 -> 32]
Trying to delete after position 2: Cannot delete after tail.
Inserting 5 at front. Current list: [5 -> 16 -> 5 -> 32]
Inserting 32 at end. Current list: [5 -> 16 -> 5 -> 32 -> 32]
Inserting 16 at front. Current list: [16 -> 5 -> 16 -> 5 -> 32 -> 32]
Inserting 8 at front. Current list: [8 -> 16 -> 5 -> 16 -> 5 -> 32 -> 32]
Inserting 21 at end. Current list: [8 -> 16 -> 5 -> 16 -> 5 -> 32 -> 32 -> 21]
Inserting 50 at end. Current list: [8 -> 16 -> 5 -> 16 -> 5 -> 32 -> 32 -> 21 -> 50]
Inserting 32 at end. Current list: [8 -> 16 -> 5 -> 16 -> 5 -> 32 -> 32 -> 21 -> 50 -> 32]
Inserting 66 at front. Current list: [66 -> 8 -> 16 -> 5 -> 16 -> 5 -> 32 -> 32 -> 21 -> 50 -> 32]
Inserting 66 at front. Current list: [66 -> 66 -> 8 -> 16 -> 5 -> 16 -> 5 -> 32 -> 32 -> 21 -> 50 -> 32]
Trying to remove duplicates from: Cannot remove duplicates unless sorted!
Sorted List: [5 -> 5 -> 8 -> 16 -> 16 -> 21 -> 32 -> 32 -> 32 -> 50 -> 66 -> 66]
Remove duplicates: [5 -> 8 -> 16 -> 21 -> 32 -> 50 -> 66]
Push odd indexes to the back: [5 -> 16 -> 32 -> 66 -> 8 -> 21 -> 50]
Inserting -12 at front. Current list: [-12 -> 5 -> 16 -> 32 -> 66 -> 8 -> 21 -> 50]
Push odd indexes to the back: [-12 -> 16 -> 66 -> 21 -> 5 -> 32 -> 8 -> 50]
Reversing List: [50 -> 8 -> 32 -> 5 -> 21 -> 66 -> 16 -> -12]
****************** Test Dynamic Array Correctness ******************
[0] Num elements: 1, Length: 1
[0, 5] Num elements: 2, Length: 2
[0, 5, 10] Num elements: 3, Length: 4
[0, 5, 10, 15] Num elements: 4, Length: 4
[0, 5, 10, 15, 20] Num elements: 5, Length: 8
[0, 5, 10, 15, 20, 25] Num elements: 6, Length: 8
[0, 5, 10, 15, 20, 25, 30] Num elements: 7, Length: 8
[0, 5, 10, 15, 20, 25, 30, 35] Num elements: 8, Length: 8
[0, 5, 10, 15, 20, 25, 30, 35, 40] Num elements: 9, Length: 16
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45] Num elements: 10, Length: 16
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] Num elements: 11, Length: 16
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55] Num elements: 12, Length: 16
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60] Num elements: 13, Length: 16
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65] Num elements: 14, Length: 16
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70] Num elements: 15, Length: 16
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75] Num elements: 16, Length: 16
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80] Num elements: 17, Length: 32
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75] Num elements: 16, Length: 32
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70] Num elements: 15, Length: 32
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65] Num elements: 14, Length: 32
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60] Num elements: 13, Length: 32
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55] Num elements: 12, Length: 32
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] Num elements: 11, Length: 32
[0, 5, 10, 15, 20, 25, 30, 35, 40, 45] Num elements: 10, Length: 32
[0, 5, 10, 15, 20, 25, 30, 35, 40] Num elements: 9, Length: 32
[0, 5, 10, 15, 20, 25, 30, 35] Num elements: 8, Length: 16
[0, 5, 10, 15, 20, 25, 30] Num elements: 7, Length: 16
[0, 5, 10, 15, 20, 25] Num elements: 6, Length: 16
[0, 5, 10, 15, 20] Num elements: 5, Length: 16
[0, 5, 10, 15] Num elements: 4, Length: 8
[0, 5, 10] Num elements: 3, Length: 8
[0, 5] Num elements: 2, Length: 4
[0] Num elements: 1, Length: 2
[] Num elements: 0, Length: 1
Description and files needed/out/production/Description and files needed/.idea/.gitignore
# Default ignored files
/shelf/
/workspace.xml
Description and files needed/out/production/Description and files needed/.idea/misc.xml
Description and files needed/out/production/Description and files needed/.idea/modules.xml
Description and files needed/out/production/Description and files needed/.idea/workspace.xml
1622434238059
1622434238059
Description and files needed/out/production/Description and files needed/DynamicArray.class
public synchronized class DynamicArray {
int[] A;
int numElements;
int length;
public void DynamicArray(int);
private int[] copyArray(int[], int, int);
public int access(int);
public void update(int, int);
public void insertAtEnd(int);
public void deleteLast();
public int getSize();
public String toString();
}
Description and files needed/out/production/Description and files needed/ListNode.class
synchronized class ListNode {
public int value;
public ListNode next;
public void ListNode(int);
}
Description and files needed/out/production/Description and files needed/(1) Coding task description.docx
(Applications of Binary Search, Linked List, and Dynamic Arrays)
1: Applications of Binary Search
Complete the functions in the BinarySearchApplications.java file. Details of the functions to be implemented are provided in the following subsections.
1.1: Counting the number of occurrences of key in a sorted array
In certain applications, we are interested in counting the number of times key appears in a sorted array. The technique to solve such problems is to determine:
· minIndex: the minimum index where key appears
· maxIndex: the maximum index where key appears
The number of occurrences is given by (maxIndex − minIndex + 1).
Hence, our task is to find both the minimum and maximum positions where a key occurs. We seek to solve this using Binary Search. To this end, complete the following functions:
· int minIndexBinarySearch(int array[ ], int arrayLength, int key): returns the minimum index where key appears. If key does not appear, then returns −1.
· int maxIndexBinarySearch(int array[ ], int arrayLength, int key): returns the maximum index where key appears. If key does not appear, then returns −1.
· int countNumberOfKeys(int array[ ], int arrayLength, int key): Returns 0 if key is not in the array, else it returns the number of occurrences of key.
Caution: Your code should have complexity O(log n), where n = arrayLength. If your code ends up scanning the entire array (has a complexity O(n)), you have done something incorrectly and must fix..
Algorithm for finding the minimum index
Algorithm for finding the minimum index
· The main idea is to use binary search with a slight modification. Declare a variable called minIndex along with left and right. Initially, minIndex = −1.
· Now, when you find key at index mid, do not return mid, but set minIndex = mid, right = mid − 1, and continue.
· Finally, after the while loop expires return minIndex (instead of −1).
Use a variable maxIndex (instead of minIndex). Algorithm remains the same as above, just that when you find key at mid, we set maxIndex = mid and left = mid + 1. Finally, return maxIndex.
Algorithm for finding the maximum index
Algorithm to count number of occurrences of key
Use the above two algorithms to get minIndex and maxIndex. Then, use the formula to count and return the number of occurrences.
1.2: The Predecessor Problem
Given a set of numbers, the predecessor of a number x is the highest number in the set that is less than or equal to x. Thus, if I have the set {6, 9, 10, 13, 22, 31, 34, 88}, then the predecessor of 31 is 31 itself, whereas the predecessor of 30 is 22, and the predecessor of 5 is not defined.
The predecessor problem has remarkable applications in network routing, where we send information from one computer to another, making email and other uses of the internet possible. Another application is nearest-neighbor search, akin to locating restaurants on Google Maps, where it returns the closest match to a cuisine of your choice.
Our task is to find the predecessor of a number in an array using a Binary Search approach. To this end, complete the following function:
· int predecessor(int array[ ], int arrayLen, int key): returns a position in the array where the predecessor of key lies. Needless to say that the array is sorted in ascending order. If the predecessor of key is not defined, return −1.
Caution: You MUST use a binary search approach. Thus, the complexity should be O(log n). If your code ends up scanning the entire array (has a complexity O(n)), you will be awarded partial credit, even if your code is correct.
Algorithm for finding the predecessor index
• The main idea is to use binary search with a slight modification. Declare a variable called predIndex along with left and right. Initially, predIndex = −1.
• Now, when A[mid] < key, then mid is a better estimate of your predecessor index; so, set pred = mid, left = mid + 1, and continue. Rest remains unchanged within the while loop.
• Finally, after the while loop expires return predIndex (instead of −1).
1.3: Peak Finding
Consider an array A of n unique integers, i.e., all numbers are distinct. The array increases until a number (which is the maximum), and then decreases. For example, if the array is A[ ] = {2, 5, 7, 9, 13, 10, 8, 1}, then the maximum is 13. Our task is to return the index containing the maximum value; in this case, we have to return 4. To this end, fill up the following function:
· int findPeak(int twoToneArray[ ], int arrayLen): returns an index in the array that contains the maximum. The array contains unique values. It increases until a point and then decreases.
Obviously one can scan the entire array. The other approach is to scan the array and stop whenever we reach a number such that the next one is smaller. The complexity, in either approach, is O(n). Using binary search kind of a technique, we can improve this to O(log n). The main idea is to compute mid and check adjacent values.
In the given example A[ ] = {2, 5, 7, 9, 13, 10, 8, 1}, initially mid = 3 and A[mid] = 9 < 13 = A[mid + 1]. So, we set left = 4 and recompute mid = 5. Now, A[mid] = 10 < 13 = A[mid − 1]; so, we set right = 4. At this point left equals right and we can return left as the answer. For the array A[ ] = {2, 5, 7, 9, 13, 10, 8, 1, 0}, we compute mid = 4 and see that A[mid−1] < A[mid] < A[mid+1]; so, we return mid = 4 directly. We can summarize this as follows:
Algorithm for Peak Finding
· If left equals right, return left.
· If right = left + 1, return left or right whichever contains the larger value.
· Compute mid.
· If A[mid] is smaller than A[mid + 1], then set left = mid + 1
· Else If A[mid] is smaller than A[mid − 1], then set right = mid − 1
· Else return mid
· Repeat this process as long as lef t ≤ right.
Caution: You MUST use a binary search approach. Thus, the complexity should be O(log n). If your code ends up scanning the entire array (has a complexity O(n)), you will be awarded partial credit, even if your code is correct.
2: Linked List
Your task is to complete the following functions in the LinkedList.java file:
· void insertAfter(ListNode *argNode, int value) for Java:
· Function inserts a node with value value after the node argNode. You may assume that argNode is not null.
· void deleteAfter(ListNode *argNode):
· Function deletes the node after argNode. You may assume that argNode is not null.
· void selectionSort():
· Function that sorts the linked list using selection sort method.
· boolean removeDuplicatesSorted():
· Function that checks whether or not the linked list is sorted in ascending order. If it is not sorted, then the function returns false. Otherwise, the function removes the duplicate occurrences of each number from the list (i.e., only one occurrence of each number remains). Then the function returns true.
· void pushOddIndexesToTheBack():
· Function that pushes all the odd indexes to the back of the linked list, starting with index 1, then 3, then 5, and so on.
· void reverse():
· This function reverses a linked list in-place, i.e., without using any extra space (such as an array or another linked list) other than variables.
Caution: For the last 4 methods, you CANNOT use any other data structure (linked list or arrays) for storage. You CAN ONLY use variables. Also on a linked list of length n:
· the first two functions must have a complexity of O(1),
· selection sort must achieve a complexity of O(n2)
· removing the duplicates method must achieve a complexity of O(n)
· pushing the odd indexes to the back must achieve a complexity of O(n)
· reverse the linked list must achieve a complexity of O(n)
2.1: insertAfter
· create a newNode
· newNodes’s next points to argNode’s next
· argNode’s next points to newNode
· if argNode is tail, then newNode becomes tail
· increment size
2.2: deleteAfter
· if argNode is tail, then there is nothing to delete
· else if argNode’s next is tail, then
· get rid of all references to tail (Java)
· argNode becomes tail
· decrement size
· else
· use a placeholder variable to point argNode’s next
· argNode’s next points to placeholder’s next
· get rid of all references from placeholder (Java)
· decrement size
2.3: Selection Sort
Pseudo-code
· You will use virtually the same idea as in a selection sort algorithm on arrays
· Since random accesses are not possible, use three placeholder variables – iNode to point to the ListNode on which the outer loop i is iterating, minNode to point to the minimum valued node in the portion of the linked list starting from i all the way to the end, and jNode to point to the ListNode on which the outer loop j is iterating
· Initially iNode points to head
· Within the outer-loop, minNode is initially iNode and jNode is the node after iNode
· Within the inner-loop, you compare the values of jNode and minNode and you set minNode to jNode, if the latter has a smaller value. Set jNode to its next node.
· Once the inner loop terminates, you swap the values of iNode and minNode (if needed). Then, set iNode to its next node.
2.4: Removing Duplicates in Ascending Sorted List
Pseudo-code
· To check if the linked list is ascending sorted, use a loop with a place holder variable (similar to getNodeAt function). At any point, if the value of the placeholder node is larger than the value of the next node, then you return false, else move placeholder to its next node.
· Once you are done with the above for-loop (and did not return false), it is guaranteed that the linked list is sorted.
· Once again scan through the linked list using a loop and a placeholder. If the value of the placeholder equals the value of the next nodea, then you can delete the duplicate value in the next node by calling deleteAfter on the placeholder, else move placeholder to its next node.
_______________________________________
*If the next node is null, then stop the process!
2.5: Pushing Odd Indexes to the End
· If the input list is [5 → 8 → 16 → 21 → 32 → 50 → 66], then after executing this function the list will become [5 → 16 → 32 → 66 → 8 → 21 → 50]
· If the input list is [−12 → 5 → 16 → 32 → 66 → 8 → 21 → 50], then after executing this function the list will become [−12 → 16 → 66 → 21 → 5 → 32 → 8 → 50]
Pseudo-code
· Scan through the linked list using a loop and a placeholder, but this time only loop over the even indexes 0, 2, 4, 6, and so on.
· Within the loop, insert the value in the node immediately after the placeholder at...