CS 127, Data Structures

Analytical Assignment: Questions on Big-O, Searching, and Sorting

Part I Assigned in class on Wednesday, 10/30.
Part I due on paper in class on Monday, 11/4.

Part II Assigned on Friday, 11/1.
Part II due on paper in class on Wednesday, 11/6.

You should not electronically submit anything for this assignment.

Part I:

1. Page 296, E1 (a).

2. Page 296, E3.

3. Page 312, E2.

Part II:

1. On paper, sort 9, 8, 7, 6, 5, 4, 3, 2, 1 using Shellsort with increments {7, 3, 1}.

2. On paper, sort 3, 1, 4, 1, 5, 9, 2, 6 using merge sort.

3. On paper, sort 3, 1, 4, 1, 5, 9, 2, 6 using quicksort with pivot in the first position.

4. Suppose that you have an array of n elements, containing only two distinct keys, true and false. Give an O(n) algorithm to rearrange the list so that all false elements precede the true elements. You may use only constant extra space.

5. The choice of pivot for quicksort can dramatically affect its performance. Some common choices are:

• The first element
• The middle element
• A randomly selected element
• The median element of the array
• The median element of the first three elements in the array