CS 0445 Data Structures



CS 0445 Data StructuresExam 2 Practice Long Form Question SolutionsBefore looking at these, I recommend giving the problems a good try (simulate test conditions)?Consider the MergeSort and QuickSort sorting algorithms. Give the Big-O run-times for both algorithms (average and worst cases). In real terms, which algorithm has the faster run-time and why? Be specific.Answer:MergeSort average and worst case: O(Nlog2N)QuickSort average case: O(Nlog2N); QuickSort worst case: O(N2)Despite its possible poor worst case performance, QuickSort tends in general to be faster than MergeSort due to extra overhead incurred in the MergeSort algorithm. This overhead is due to the merge algorithm, which requires the data to be merged into a new, temporary array before being copied back into the original array. This extra copying requires extra time. QuickSort, on the other hand, sorts the data in place, and does not require an extra array.Consider implementations of the Queue ADT:One simple implementation option is to use an underlying ArrayList for the data and simply do add() for enqueue and remove(0) for dequeue. Is this a good implementation? Explain why or why not in detail.Answer: No, it is not, because remove(0) on an ArrayList requires the shifting of the remaining items over to fill the gap. This causes remove(0) to take O(N) time when it should only take O(1) time. The add() method, on the other hand, is fine since it takes O(1) time in an ArrayList.If we use the same operations listed in a) above, but with a LinkedList rather than an ArrayList as the data, will this be a good implementation? Explain why or why not in detail.Answer: It depends on how the LinkedList is implemented. If the LinkedList has a Rear or Tail reference (or is circular or doubly-linked) both add() and remove(0) can be easily done in O(1) time and the implementation is good. However, if only a Front reference is available, the add() requires a traversal of the list, making it an O(N) operation. In a standard Java LinkedList the implementation would be good, since it is a doubly linked list.?Assume that you are using?linear probing?in a simple hash table of?Strings, with the instance variable shown below. ?Function?h(x) is defined as we discussed it in class (and you do NOT have to write it). Complete the code for the contains() method below, which will return true if the item is present and false otherwise. Be sure to handle ALL possibilities.String [] table; // instance variable// Other methods not shown. Note that all table locations are// initialized to null prior to any Inserts. Assume that no // deletes are allowed. // Fill in the code.public boolean contains(String item){ int?index = h(item);? // Answers vary. One possible answer is shown below. Note that // in the worst case (table is full) we may have to try all // locations. for?(int i = 0; i < table.length; i++) { int?curr = (index + i) % table.length; // try next loc // note that we must wrap around the endif?(table[curr] == null) // empty loc ends searchreturn?false;else?if (table[curr].equals(item)) // finding valuereturn?true; // ends search } return?false; // cycled through all locations – not found}?Consider the SelectionSort algorithm, as we discussed in lecture. Justify the worst case run-time for this algorithm. Be complete and detailed in your analysis.Answer: Let comparisons be our key operation. At each iteration of the outer loop we find the next smallest item in the array. Consider iteration 0:Assume A[0] is the 0th smallest; In inner loop we compare N-1 other items to find actual 0thConsider iteration 1:Assume A[1] is the 1th smallest; In inner loop we compare N-2 other items to find actual 1th Consider iteration 2:Assume A[2] is the 2nd smallest; In inner loop we compare N-3 other items to find actual 2nd ...Consider iteration N-2:Assume A[N-2] is (N-2)th smallest; In inner loop we compare 1 other item to find actual (N-2)thOverall the total number of comparisons is 1 + 2 + ... + N-1 = (N-1)(N)/2. This is O(N2). ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download