Data Structures And Algorithms In Java

Exercises from book "Data Structures And Algorithms In Java" by Robert Lafore, (Second edition).

Student: Viktor Kulygin

Chapter	Task
2 (Arrays)
chapter02-task21	Add to the HighArray class from the highArray.java program (Listing 2.3) a getMax() method that returns the highest key value in the array or -1 if the array is empty. Add code to main() to test the new method. Assume that all keys are positive numbers.
chapter02-task22	Change the method in 2.1 so that the element with the highest key is not only returned by the method, but is also removed from the array. Give the new version the name removeMax().
chapter02-task23	The removeMax() method from 2.2 can be used to sort the contents of the array by key. Implement a sorting algorithm that does not change the HighArray class (it only changes the main() code). You will need a second array to store the sorted data. (This algorithm is an extremely primitive version of the sorting by selection described in Chapter 3, "Simple sorting".)
chapter02-task24	Modify the orderedArray.java program (Listing 2.4) so that the insert() and delete() methods and the find() method use a binary search (as suggested in the text).
chapter02-task25	Add a merge() method to the orderedArray class of orderedArray.java (Listing 2.4) that merges two ordered source arrays into one ordered destination array. Include a code snippet in main() that fills the two source arrays with random numbers, calls merge(), and outputs the contents of the resulting array. The original arrays may contain different numbers of elements. Your algorithm should compare the keys of the original arrays and copy the smaller one to the target array. You should also anticipate the situation where elements in one source array end before those in another.
chapter02-task26	Add a noDups() method to the HighArray class of highArray.java (Listing 2.3) that removes all duplicates from the array. In other words, if the array contains three elements with key 17, the noDups() method should remove two of them. Don't worry about preserving the order of the elements. One solution is to compare each element with all the other elements, and then replace all duplicates with null (or another value not found among the real keys), and then remove all occurrences of null from the array. Of course, this will reduce the size of the array.
3 (Simple sorting)
chapter03-task31	In the bubbleSort.java program (Listing 3.1) and in the BubbleSort Workshop application, the index in always moves from left to right, finds the largest element and moves it to the out position on the right. Modify the bubbleSort() method so that it performs two-way moves, in other words, the in index first moves the largest element from left to right as before, but then it reverses direction and moves the smallest element from right to left. You will need two external indexes, one on the right (the old index out) and one on the left.
chapter03-task32	In the ArrayIns class of the insertSort.java program (listing 3.3), add a method called median() that returns the median of the array. (Recall that in a group of numbers, half is less than the median and the other half is greater.) Find an easy solution to this problem.
chapter03-task33	Add the noDups() method to the insertSort.java program (listing 3.3), which removes duplicates from a previously sorted array without disturbing the order of the elements. (Use the insertionSort() method to sort the data, or just insert the data in sort order in main().) It's not hard to imagine a scheme in which all elements from the duplicate detection position to the end of the array are shifted by one position, but this will slow the algorithm down to time O(N 2) - at least with a large number of duplicates. Make sure that no element in your algorithm moves more than once, regardless of the number of duplicates, to ensure that the algorithm completes in O(N) time.
chapter03-task34	Another simple sorting algorithm, even-odd permutation sort, is based on two iterations through the array repeatedly. On the first pass, all pairs of elements a(j) and a(j+1) are searched, where j is an odd number (j = 1, 3, 5, ...). If the keys are in the wrong order, the elements are swapped. On the second pass, the same is done for all even values(j = 2, 4, 6, ...). Two-pass processing is performed repeatedly until the array is completely sorted. Replace the bubbleSort() method in bubbleSort. java (Listing 3.1) with the oddEvenSort() odd-even permutation method. Make sure it works for arbitrary amounts of data. It is required to determine how many times the two-pass processing will be performed. Odd-even sorting is very useful in multiprocessor configurations, when different processors can simultaneously work with different odd (and then even) pairs. Since the odd pairs are independent of each other, each pair can be checked (with the elements rearranged if necessary) by a separate processor. This sorting is very fast.
chapter03-task35	Modify the insertionSort() method in the insertSort.java program (Listing 3.3) so that it counts the number of copies and comparisons during the sort and then prints the results. To count comparisons, you need to split the complex condition in two in the inner while loop. Use the program to measure the number of copies and compare for different amounts of data, sorted in reverse order. Do the results support the theoretical complexity of O(N 2)? Do the same for almost sorted data (in which only a few elements are out of place). What conclusions can be drawn about the efficiency of this algorithm for almost sorted data?
chapter03-task36	There is one interesting way to remove duplicates from an array. Insertion sort uses a nested loops algorithm that compares every element in an array with every other element. If you want to remove duplicates, this is one possible solution (see also Exercise 2.6 in Chapter 2). Modify the insertionSort() method in the insertSort.java program to remove duplicates during sorting. For example, when a duplicate is found, one of the instances can be replaced by a key value that is known to be less than the keys of other elements (say, -1 if all normal keys are positive). The usual insertion sort algorithm, which treats the new key equally with all others, then places it at element index 0. It will be ignored by the algorithm from now on. The next duplicate is placed at cell index 1, and so on. After the sort is complete, all deleted duplicates (now represented by the -1 key) will be placed at the beginning of the array. All that remains is to shift the non-duplicate elements so that they start at index 0 and resize the array.
4 (Stacks and Queues)
chapter04-task41	Write a method on the Queue class of the queue.java program (see Listing 4.4) to display the contents of the queue. Note that the task is not limited to simply displaying the contents of the underlying array. The contents of the queue should be displayed from the first inserted element to the last one, and the user should not see that the sequence is interrupted at the array boundary. Be careful to ensure that one element and the contents of the empty queue are displayed correctly regardless of the position of the front and rear.
chapter04-task42	Create a Deque class based on the description of decks (two-way queues) in this chapter. The class must contain methods insertLeft(), insertRight(), removeLeft(), removeRight(), isEmpty(), and isFull() methods. It must also support of cyclic indexes transfer, similar to queues.
chapter04-task43	Write a stack implementation based on the Deque class from Section 4.2. The stack class must support the same methods and features as the StackX class in the program. support the same methods and features as the StackX class in the program stack.java (see listing 4.1).
chapter04-task44	The priority queue implementation from listing 4.6 provides fast retrieval of high-priority items, but insertion of new items is relatively slow. Write a program with a modified PriorityQ class that performs fast insertion (in O(1) time) with slow retrieval of a high-priority item. Include a method to output the contents of priority queue (see section 4.1).
chapter04-task45	Queues are often used to model the flow of people, cars, airplanes, banking operations, etc. Write a program that simulates queue of customers to the cash registers in a store, based on the Queue class from the queue java program (see listing 4.4). The program must display the contents of several queues at once; use the display() method from Section 4.1. A new customer is placed in the queue by pressing a key. You must determine for yourself how he will select the queue. The service of each customer has random duration (depending on the number of items in the cart). Serviced shoppers are removed from the queue. For simplicity, the passage of time can be modeled by keystrokes - for example, each keystroke of corresponds to one minute. (Of course, Java has more advanced tools for working with time.)
5 (Linked Lists)
chapter05-task51	Implement a prioritized queue based on a sorted linked list. The fetch operation from the priority queue must fetch the element with the smallest key.
chapter05-task52	Implement a deque based on a doubly-linked list (see program project 4.2 of the from the previous chapter). The deck must support all standard operations.
chapter05-task53	A cyclic list is a linked list in which the last element contains a reference to the first element. There are many ways to implement of cyclic lists. Sometimes a list object contains a pointer to the "beginning" of the list. of the list. However, in this case, the list is no longer a closed circle, but more like a regular list with the end linked to the beginning. It is more like a regular list with the end connected to the beginning. Create a class for a single-linked list that has neither beginning nor end. The list is accessed by a single current link. accessed by a single current link, which can point to any item in the list. element of the list. The link is moved through the list as the user requires (a situation for which a cyclic list is ideally suited is presented in project 5.5). in project 5.5). The list must support insert, search, and delete operations. It is probably more convenient to perform these operations on the element following the one pointed to by current. pointed to by current. (Since the list is a single-linked list, you cannot go back to the previous element without the current. (Since the list is single-linked, you cannot return to the previous item without going through the entire chain.) It should also be possible to output the contents of the list (although it will have to be broken at some point to display it on the screen). The step() method, which method, which moves current to the next element, may also be useful.
chapter05-task54	Implement a stack class based on the cyclic list from project 5.3.
chapter05-task55	The problem of Josephus Flavius is a famous mathematical problem with historical with historical overtones. There are many legends about how it originated. One of them says that Josephus was part of the garrison of a besieged fortress that the Romans was about to be taken by the Romans. The defenders of the fortress chose death over slavery. They lined up in a circle and started counting in a circle, choosing a particular person as the starting point a particular person as the starting point. Each nth person left the circle and committed self - murder. Joseph decided that it was too early for him to die, so he chose the rules so that he would be to be the last survivor. If there were (for example) 20 people in the circle and he was was the seventh from the beginning of the count, what number should have been chosen for the count? The problem is complicated by the fact that the circle shrinks as the participants are eliminated. Create an application that models the task using a cyclic linked list (as in Project 5). linked list (as in Project 5.3). The input parameters are the number of people in the circle, the number of people in the circle, and the number of people in the circle. number of people in the circle, the number to count, and the number of people to start counting (most often 1). counting (most often 1). The program outputs a list of people who are leaving. When one of the participant leaves the circle, the counting starts again to his left (it is assumed that the counting starts from the left of him). It is assumed that the countdown is clockwise). For example, if there are seven participants with numbers from 1 to 7 in the circle, and counting is carried out in 3 positions (starting from position 1), then the participants leave the circle. from position 1, then the contestants are eliminated in the order 4, 1, 6, 5, 7, 3. Number 2 remains last.