CSCI 3333.3
Data Structures
Spring 2013
Homework #8

Due Date: May 1 (Wednesday)

Exercises: 75%

(1) Show the evolution of applying Shell Sort with gap sequence (5,3,1) to the array: {22, 66, 33, 15, 90, 47, 80, 6, 39, 2, 99, 17, 42, 51, 72, 90, 74, 1, 18} by showing the array after 5-sorted, 3-sorted and 1-sorted. Show the conceptual view also.

(2) Exercise 8.5, p386, Weiss. Answer in the Big O Notation. For quicksort, you may assume that the middle element is selected as the pivot.

(3) Write an O(N lg N) algorithm (O(N2) algorithm not acceptable), UniqueCount(A), to return the counts of an unique elements in an integer array A. For example, if A is {10, 3, 2, 5, 2, 10, 10, 10, 2, 5, 3, 2}, the algorithm should return 4 since there are four unique elements: 2, 3, 5 and 10.

(4) Write an O(N lg N) algorithm (O(N2) algorithm not acceptable), HasCommonElements(A,B) to check whether two integer arrays A and B have a common element. For example, if A={1,3,2,4,3,2,4,5,6} and B={10, 20, 30, 20, 10, 15}, the return result should be false. For A= A={1,3,2,4,3,2,4,5,6} and B={10, 2, 11, 4, 2, 100, 100, 8}, the return result should be true since A and B both have the elements 2 and 4.

(5) Provide a worst case scenario for quicksort when the first element of the array is always used as the pivot.

Programming: 25%

(1) Implement your algorithm for question (3) as a program, taking command line arguments as the input array. For example, if you are using Java, you may have:

...>java UniqueCount 1 2 1 2 1
The number of unique elements: 2.

...>java UniqueCount 1 2 1 2 1 3 1 4
The number of unique elements: 4.

...>java UniqueCount 1

 For this programming assignment, turn in:

• The sour program UniqueElement.java (which includes the class file), or something similar if you use other programming languages.
• A screen shot of the execution of the UniqueElement.class.

As usual, email everything to the TA.