Reference no: EM131310342
Search and Sort Algorithms
Objectives - To test search and sort algorithms
As you add methods to the code given, add documentation similar to what is used on the other methods (comment boxes).
Turn in IntegerList and IntegerListTest, table filled in, and the answer to a question on sorting and searching - see step 8 below.
1. The selection sort is missing two methods (swap and minIndex) - add them or copy the code for a selection sort using one method from last week's lab. Use this selection sort code in the sortAscending method.
2. Write the insertion sort, changing the insertion logic to sort in descending order and use it for sortDecreasing method. (p. 523).
3. Make sure the selection sort is increasing order and the insertion sort is decreasing order by creating small arrays, sorting them, and then printing them.
4. Write a method that to implement the enhanced bubble sort that sorts in ascending order.
5. Sort an array filled with random numbers with the selection sort for the first timing and then sort it again with the selection sort for the second timing.
6. Sort an array filled with random numbers with the insertion sort for the third timing and then sort it again with the insertion sort for the fourth timing.
7. Sort an array filled with random numbers with the enhanced bubble sort for the fifth timing and then sort it again with the enhanced bubble sort for the sixth timing.
8. Remember that the data in an array must be in ascending sequence to search it with the binary search method. Fill the arrays with sorted data before calling the binary search method. Since it doesn't matter if you fill the arrays to be used with the sequential search with sorted or unsorted data, you might as well fill the search array with sorted data once, then sequentially search it and then binary search it.
9. Write a short paragraph on sorting and another on searching. Explain why the times changed (or didn't change) for the different methods and how the algorithms were affected by the larger array sizes.
Timing Searching and Sorting Algorithms
In this exercise you will use an IntegerList class (in the file IntegerList.java) and a driver (in the file IntegerListTest.java) to examine the runtimes of the searching and sorting algorithms. The IntegerListTest class has several options for creating a list of a given size, filling the list with random integers or with already sorted integers, and searching or sorting the list. (NOTE: You may have used a version of these classes in the last lab.) Save these files to your directory and run IntegerListTest a few times to explore the options.
The runtimes of the sorting and searching algorithms can be examined using the Java method System.currentTimeMillis(), which returns the current system time in milliseconds. (Note that it returns a long, not an int.) You will have to import java.util.* to have access to this method. In IntegerListTest, just get the system time immediately before and immediately after you perform any of the searches or sorts. Then subtract the first from the second, and you have the time required for the operation in milliseconds. WARNING: Be sure you are not including any input or output in your timed operations; these are very expensive and will skew your algorithm times!
Add appropriate calls to System.currentTimeMillis() to your program, run it and fill out the tables below. Note that you will use much larger arrays for the search algorithms than for the sort algorithms; do you see why? Also note that the first couple of times you run a method you might get longer runtimes as it loads the code for that method. Ignore these times and use the "steady-state" times you get on subsequent runs. On a separate sheet, explain the times you see in terms of the known complexities of the algorithms. Remember that the most interesting thing is not the absolute time required by the algorithms, but how the time changes as the size of the input increases (doubles here).
Will the firm need external funds
: Using the percent of sales method, forecast the new balance sheet for sales of $600,000 assuming that cash changes with sales and that the firm is not operating at capacity. Will the firm need external; funds?
|
How can a company attempt to eliminate the knowledge gap
: Which of the gaps in Figure do you think represents the major problem for most firms? How can a company attempt to eliminate the knowledge gap? The communications gap?
|
Read the threads of your classmates and the articles
: Read the threads of your classmates and the articles which are referenced (this is why it is imperative that the articles be accessible via working URL links). Expect to spend some time each day reviewing all threads and replies, even those in whi..
|
Modify a classical cryptosystem to provide nonrepudiation
: The ciphertext corresponds to the plaintext enciphered under the secret key that Alice and Bob share. Explain why this does not satisfy the requirements of nonrepudiation of origin. How might you modify a classical cryptosystem to provide nonrepud..
|
Write a method that to implement the enhanced bubble sort
: Write a method that to implement the enhanced bubble sort that sorts in ascending order. Write the insertion sort, changing the insertion logic to sort in descending order and use it for sortDecreasing method. (p. 523).
|
Develop a similar class hierarchy for animals
: Develop a similar class hierarchy for Animals. You can have whatever subclasses you think would be useful. Your hierarchy should have at least three levels (the top class, Animals, counts as the first level).
|
What are the other two weak keys
: What are the other two weak keys? (Note: Differences in the parity bits, which the PC-1 permutation drops, do not count; the keys must differ in the 56 bits that are used to generate the key schedule.)
|
Create a presentation that describe the data types
: Create a 12 slide presentation describing the data types. Include the following in your presentation: Introductory slide Slide for each data type (containing a definition of the data type and examples of fields the type would include).
|
Create a program for the 3pi
: Your final project will be to create a program for the 3Pi to perform a number of line following tasks. You may not program the robot between tasks but are allowed to provide inputs to the robot before each task. All lines are dark on white backg..
|