Data Structures

DATA STRUCTURES AND ALGORITHMS ASSIGNMENT ONE

1. For each of the following pairs of data structures, name one advantage that the first data structure has over the second and one advantage that the second has over the first. Your answers should be brief. Note that "having more operations" is not an acceptable answer since the given Abstract Data Type (ADT) determines the set of operations. Further, note that we are assuming high-quality implementations are readily available, so “easier to implement” is also not an acceptable answer(15marks)

a. [Linked List vs. Array] used as a Stack.

Linked List advantage:

No bound on size

Array advantage

Less space

b. [Heap vs. Sorted Array] used as a Priority Queue.

Heap advantage:

All PQ operations are O(log n) time.

Sorted Array advantage:

Fast if no insertions after initialization or getMax takes O(1) time.

c. [Hashing with Chaining and Table-Doubling vs. Balanced BST] used as a Dictionary.

Hashing advantage:

O(1) expected time (but bad worst-case)

Balanced BST advantage:

O(log n) worst-case time

d. [Array of Lists, one list for each priority (sometimes called a bounded-height priority queue) vs. Heap] used as a Priority Queue.

[Sorted Array vs. Balanced BST] used as a Dictionary.

Array of Lists advantage:

O(1) per operation (but requires small number of priorities) or FIFO for items with tied priorities

Heap advantage:

Can allow arbitrary number of different priorities.

2. For each of the problems below, you need to show the important steps of a sorting algorithm. The idea is to show that you understand how the algorithm works. We are not interested in code; just show how the data is moved during the algorithm at the level-of-detail one might use while explaining the algorithm on a blackboard. Show the important steps that occur when MergeSort is performed on the following array of integers:...