Question

DATA STRUCTURES CLASS CMPS 2720

clear answers

ESSAY TYPE ANSWERS

1) A) Suppose an array contains N unsorted keys. What is the minimum number of comparisons necessary to find a specific key value? What is the maximum number? What is the average number?

b)   Suppose an array contains 2000 sorted keys. What is the maximum number of comparisons necessary to find a given key value if a binary search is used?

c) Suppose a large number of records need to be stored into and retrieved out of an array. What are the advantages and disadvantages of the keeping the keys in the array sorted? Be sure to address time required to store, delete, retrieve, and find data. What effect would the size of individual records (in bytes) have?

d) What is the difference between a queue and a priority queue? Be sure to address not only the structure of the data structures, but also the time required to insert an object into the queue/priority queue, and the time to remove an item from the queue/priority queue.

e) One way to sort data would be to insert the values, one at a time, into a priority queue without removing any values. Once the entire list has been entered, the data could then be removed from the queue one at a time in order. Which of the sorts would this method be most like? How efficient would this method be compared with the other methods?

f)   Suppose that 12, 20, 14 are inserted onto an empty queue, then one number removed from the queue. Suppose then that 19, 26, 10, and 17 are inserted into the queue and two numbers removed. How many numbers are in the queue at the conclusion of the procedures, and what are the values in the queue, listing the items from the first that would be removed to the last that would be removed?

g)  Compare the three sorting techniques from chapter 3, namely the bubble sort, the select sort, and the insertions sort. What are the strengths of each, and what are the weaknesses of each? Is one of the sorts always better than another, or are there cases where one sort is faster and other cases where a different sort is faster?

Answer 1

a) Since the array contains N unsorted elements, binary search cannot be applicable. Hence we use linear search to find the key.

To find the key, the best case is to find the key in first comparison. Therefore, the minimum number of comparisons required is 1. In the worst case, we need to traverse the entire array and the key may be found in the last comparison or even may not be found. Therefore maximum of N comparisons are required. In an average case, the key can be found in the middle of the array which requires around N/2 comparisons.

b) The array contains 2000 sorted elements. The algorithm used is binary search. Hence in the worst case, we can have log₂N number of comparisons. log₂N = log₂2000 = 10.96 = 11 (approx).

c) Suppose we have N records.

If we want to keep the records in a sorted order, it takes O(N) time complexity to insert a new record. Otherwise, the insertion of a new record takes O(1) time complexity.

If the records are sorted then worst case search time complexity becomes O(log₂N) which in turn reduces the time complexity for deleting a record (Since to delete a record, we first need to find the record). If the records are not sorted, the worst case search time complexity would be O(N) which is also the time complexity for deleting the record.

The size of the individual records does not effect the time complexity, but effects the space complexity. But still we search the records based on the key values, and retrieve only the required fields from the record, the size of the record does not have much impact on the insertion, deletion and search operations.

d) A queue is a linear data structure in which the two ends are open and elements can be inserted from one end and deleted from another end. A priority queue is an extension of a queue in which every element is associated with a priority.

The queue operations insertion and deletion takes O(1) time complexity. While for the priority queue, the time complexities are O(1) and O(N) for each of the operations based on the type of the queue. If it is an ordered priority queue, the insertion takes O(N) time and deletion takes O(1) time whereas for an un-ordered queue, the insertion takes O(1) and deletion takes O(N) time complexity. The operation complexity can be reduced from O(N) to O(logN) if we use a heap to represent the priority queue.

e) The method is similar to insertion sort algorithm, In the insertion sort, the new element to be inserted is compared with the already sorted array and placed in its correct position. The number of swaps or comparisons of insertion sort are less then that of the bubble sort and the best case time complexity is O(N). Hence insertion sort suits this algorithm well.

f) The elements 12, 20 and 14 are inserted into an empty queue.

12

20

14

.................

One number is removed from the queue i.e, 12 will be removed. Then the queue becomes

20

14

..............

Now, 19, 26, 10 and 17 are inserted into the queue.

20

14

19

26

10

17

...........

Now, two numbers are removed i.e, 20 and 14 are removed.

19

26

10

17

...........

At the conclusion, 4 items are left in the queue. they are 19, 26, 10 and 17.

Now, if another deletion operation is to be performed, then 19 will be the first item to be removed and then 26 and then 10 and at last 17 will be removed.

g) Bubble sort repeatedly compares and swaps (if needed) adjacent elements in every pass. Selection sort selects i^th smallest element and places it in the i^th position. In insertion sort, the (i-1) previous elements are already sorted and i^th element is inserted into its proper place in the previous sorted sub-array.

Algorithm	Time complexity
	Best case	Average case	Worst case
bubble sort	O(N)	O(N2)	O(N2)
selection sort	O(N2)	O(N2)	O(N2)
insertion sort	O(N)	O(N2)	O(N2)

The space complexity of the three algorithms is O(1).

Strengths:

Bubble sort:

• simplest sorting technique.
• The algorithm can be optimized by terminating it when the array is sorted.

Selection sort:

• The number of swaps are reduced to O(N).
• can be used in list data structures such as linked lists.

Insertion sort:

• Number of swaps are reduced when compared to bubble sort.
• works efficiently for smaller values of N.

Weaknesses:

Bubble sort:

• comparatively slower algorithm
• Requires more number of swaps.

Selection sort:

• Time complexity is O(N²) even for the best case.

Insertion sort:

• Inefficient for large values of N.

In terms of number of comparisons, bubble sort always gives worst case performance for random data, reversely sorted data, highly repetitive data and almost sorted data.

Insertion and selection sorts give the same performance for reversely sorted data, whereas for other types of data, selection sort gives better performance than insertion sort.