Data Structures案例 20 points possible (0.3 pts/ question unless noted)11 pages, 1 hr 40 min time (~9 mins / page).Please pace appropriately.
Name:
Exam I Data Structures案例
20 points possible (0.3 pts/ question unless noted)
11 pages, 1 hr 40 min time (~9 mins / page). Please pace appropriately.
When asked for time or space requirements, use Big-O notation.
Use ‘n’ for the number of items in the collection/array
IMPORTANT NOTE: for numbered problems, if you answer and receive no partial credit, you will be deducted up to an additional 0.3 pts.
public static int recFunc (int n) {
if (n > 0) {
return (n * recFunc(n-1));
} else {
return (1);
}
}
- What value does recFunc return? Give an example.Data Structures代写
- How much time, in Big O notation, does recFunc take?
- For each recursive call, O(1) memory must be stored. In Big-O notation, how much memory is necessary to compute the solution for the value ‘n’?
After running the following four lines of code, answer the questions below:
String A = new String(“Jack”);
String B = new String(“Jack”);
String C = B;
- Does ‘A == B’ evaluate to true or false?
- Does ‘B == C’ evaluate to true or false?
- 6 Does ‘A.equals(“Jack”)’ evaluate to true or false?
- Does ‘A.equals(C)’ evaluate to true or false?
ArrayDeque implements the Deque interface, which is a subinterface of Queue.
1.Given the information above, circle the following methods you can expect ArrayDeque to implement.
.contains(Object o)
.get(int index)
.peek()
.add(Object o)
- What Java collection implementation can use all four of the methods above?
3.Collections only store objects, not primitives. However we have stored integers in collections in the homeworks. Explain very briefly how this is possible
- You have an empty stack, myStack. After running the following methods, what letter is remains in the Stack.
myStack.add(“A”);
myStack.add(“B”);
myStack.remove();
- Define encapsulation ORgive a real world example of it
- Order the following big O’s from fastest to slowest.
You will use this list for the next two questions.Data Structures代写
O(n log n), O(n2), O(2n ), O(log n), O(1), O(n!), O(n)
- Draw a line dividing the speeds in the answer above where an algorithm becomes impractically slow for ‘n’ in the thousands or more.
- In the list above, pick one of the Big-O functions above for the letters below: (1.2 pts)
a) The time for the fastest sort for a shuffled, random array
b) The number of times you can subtract 100 from the number ‘n’
c) A brute-force search of city-routes to find the shortest path
d) The number of times you can cut a number ‘n’ in half before it reaches 1
e) The speed of finding a value in an array, given the index
f) The typical speed of insertion sort, selection sort, and bubble sort.
1.What is an advantage of using ArrayList instead of arrays to store values?
2 Why should you use arrays instead of ArrayList if it is not too difficult to do so? What advantage do arrays have over ArrayList?
- Give a real-world example for either a LIFO queue or a FIFO queue, and indicate which one you picked.
- To following code clocks the amount of time it takes to run the following for loop ‘num2Check’ times. Rewrite the last line of code so it prints the average time per lookup, rather than the total time. You can rewrite it as two lines if you prefer.
long startTime = System.CurrentTimeMillis();
for (int i = 0; i < num2Check; i++) { if myColl.contains(geneSeq()) System.out.print("Found it!"); } long totalTime = System.CurrentTimeMillis() - startTime; System.out.print("It took " + String.valueOf(totalTime) + " ms");
- We often sacrifice space for speed. Quick sort and merge sort have minimum space requirements beyond the arrays themselves. What are they? (hint: quick sort’s memory comes from the recursive function calls – how often is this done in Big-O? Merge sort requires space to copy half the data array)Data Structures代写
There is a shuffled set of ‘n’ cards on a table. You pick from the top of the deck, and insert it in the proper location in your hand so that your hand is always sorted. You do this until you have all the cards are sorted in your hand.
1 What is the name for this kind of sorting algorithm?Data Structures代写
In this analogy, we will alter the algorithm from class. Unlike the sort we learned in class, instead of looking at your hand from right to left to find the proper location to place the card (a potentially O(n) operation) and then inserting, you are more likely in this case to “intelligently search” the cards in your hand (in the same way your search in a dictionary for a word) since the cards in your hand are sorted.
2 What is the big O for inserting one card in your hand this way? (note, this is not an array, but literally a hand full of cards)
3 How many times, in big O notation, will you be performing the insertion in the problem above?
4 Given the answer to the last two problems, how long does it takes to sort the entire deck of ‘n’ shuffled cards this way in big-O?
5 It would appear that the above big O time complexity is not the same as the array implementation of the same sort. Explain the discrepancy. (0.6 pts)
6 In the “deck of cards” analogy, we’re doing a binary search to find the location to place the card. Note, sorting an already-sorted deck will be slower than the expected O(n) for the standard array implementation of this sort. Why? (0.5 pts)
In the sorts homework we used merge sort and insertion sort on a mixture of two different types of data – nearly-sorted arrays and shuffled arrays.
1 Write the big-O of each in the following table (0.8 pts)
Shuffled nearly-sorted
Merge sort O( ) O( )
Insertion Sort O( ) O( )
When you add the amount of time two different operations take, the big O is the time for the slower operation (e.g. O(n2 ) + O(n3 ) = O(n3 ) ). Half of the test data was shuffled, and half was nearly-sorted. Use this information to answer the following two questions.Data Structures代写
2 What is the big-O for merge sort on the mixed test data?
3 What is the big-O for insertion sort on the mixed test data?
4 What is the big-O for a hybrid sort method that efficiently sends nearly-sorted data to insertion sort, and shuffled data to merge sort?
5 Give one good reason why it is better to use big-O notation for speed of algorithms, rather than counting operations or using other benchmarks.
6 For a given set of data, an O(n) algorithm may not necessarily be faster than an O(n2) algorithm. Explain why.
1 What is wrong with the following code ?
(hint: note A and B are objects, not primitives)
A = new String(“Adam”);
B = new String(“Amanda”);
if (A < B) {
System.out.println(A + “ is alphabetically earlier than “ + B);
}
Bubble, selection, and insertion sort are all significantly slower sorts than quick sort and merge sort for shuffled data, however,Data Structures代写
2 what advantage do they all share relative to those faster sorts?
3 Why, with modern computer hardware, is this often not enough of an advantage to use the slower three in practice?
In the lecture we discussed an implementation of quick sort that picks the leftmost value as the pivot. This leads to slow behavior if you use quick sort on sorted arrays because it doesn’t ‘divide and conquer’ your array around the pivot appropriately.
4 Again, what is the Big O in the case that you have a sorted array?
5 What is the big-O for sorted arrays if you pick the middle index as the pivot instead?
6 What would you expect to be the big-O if you picked a random index to pivot from?
1 Define only one of the following: wrapper class, boxing, unboxing, autoboxing Data Structures代写
2 This swap function doesn’t work, very briefly mention why (0.5 pts)
public static void swap (int a, int b) {
int temp = a;
a = b;
b = temp;
}
3 rewrite the swap function so it does work, swapping values in an array of integers (partial credit will be given to improper syntax if it is conceptually reasonable) (0.5 pts)
In the homeworks we used ArrayList to perform array-like operations. ArrayList uses methods to do the same things we did with indexed arrays. Translate the following ArrayList commands into an equivalent array command
Examples:
myArr.size(); à myArr.length; ArrayListmyArr = new ArrayList(50); à int [] myArr = new int[50]; 1 myArr.get(i); 2 myArr.set(j, 256); 3 myArr.set(k, myArr.get(k) + myArr.get(k + 1));
In the StackSet implementation, we extended ArrayList to be both a Queue and a Set.
4 Is a Stack a FIFO or LIFO queue?Data Structures代写
5 Name at least one function we would have had to override to get the Set functionality in the case we were extending LinkedList.
1.What is hashing?
2.Why is hashing useful?
The following are descriptions of functions performed on collections. However, you don’t have to always specify the specific implementation when it only relies on functions that are stipulated in an interface e.g. Collection, Queue, Deque, List.
Name the most general interface (the most “super” interface) you can use for the following functions.
3 Iterating through the collection using the index, and printing out each value.
4 Iterating through the collection using an iterator, or a for-each loop
5 Storing numbers that are assigned to customers as they walk in the store, then picking the number of the person that has been waiting the longest
6 Checking to see if a particular value is in the collection, and if not, adding it to the collection.
7 Sort the collection (hint: you can only sort collections that you can access based on position).Data Structures
The following code is a poor implementation of bubble sort, but it does sort the list.
public static void listBubbleSort(List x) {
int n = x.size();
for (int pass=1; pass < n; pass++) { for (int i=0; i < n; i++) { if (x.get(i) > x.get(i+1)) {
swap(x, i, i+1);
}
}
}
}
1 In big O notation, how many times is ‘i’ reset to zero? that is, how many times is the second ‘for’ loop restarted?Data Structures代写
2 What is the speed of this sort if the implementation is passed an ArrayList? (hint: if bubble sort acts as if it is simply sorting an array)
3 In big O notation, how many times is the ‘if’ statement evaluated?
4 What is the speed of executing a ‘x.get(i)’ statement in the typical case for
a) ArrayList vs.
b) LinkedList?
5 What is the speed of this sort if the implementation passed is a LinkedList? (hint, use your answer from the previous two questions to determine this)
6 After each pass of the outer for loop, the maximum unsorted value is bubbled to the end of the list. Modify the second for loop so that you don’t keep trying to sort the values that are already sorted at the end of the list.
Data Structures案例