CSCI 3333.3 Data Structures
Spring 2013
Suggested Solution to Homework #8

Exercises:

(1) Original: {22, 66, 33, 15, 90, 47, 80, 6, 39, 2, 99, 17, 42, 51, 72, 90, 74, 1, 18}

5-sorted:

Conceptual View:

Before:

After:

Result array: {22, 1, 6, 15, 2, 37, 17, 18, 39, 72, 74, 66, 33, 51, 90, 99, 80, 42}

3-sorted:

Conceptual View:

Before:

After:

Result array: {15, 1, 6, 17, 2, 37, 22, 18, 39, 33, 51, 42, 72, 74, 66, 99, 80, 90}

1-sorted:

Array: sorted.

(2)

(a) O(N2)
(b)-(d) O(N lg N)

(3)

Algorithm UniqueCount(A)
Input: A: integer array of size N.
Output: count of unique elements in A.

if N == 0 return O;
T <- Sort(A);
result <- 1;
currentInteger <- A[0];
for (int i=1; i<=N+1; i++)
   if (A[i] != currentInteger) {
       result++;
       curentInteger <- A[i];
   }
}
return result;

(4)

Algorithm HasCommonElements(A,B)
Input: A, B: integer array
Output: whether A and B has one ore more common elements.

if sizeOf(A) == 0 or sizeOf(B) == 0 return false;
S <- Sort(A);
T <- Sort(B);
NS <- SizeOf(S);
NT <- SizeOf(T);

j <- 0;
for (int i=0 to NS-1) loop
   while B[j] < A[i] loop
       j++;
       if j >= NT return false;
   end loop;
   if A[i] == B[j] return true;
end loop;
return false;

(5) The array is initially sorted.

Programming:

(1) For example, in Perl:

use strict;
# 
#    UniqueCount.pl
#
#    Count the number of unique integers in the command line.
#    Usage: UniqueCount.pl int1 int2 int3 ...
#     

#   Get the integers.
@ARGV >= 1 || die "usage: UniqueCount.pl int1 int2 int3 ... ";

my @num = sort @ARGV;     # Assume that Perl sort is O(N lg N)

my $currentElement = $num[0];
my $result = 1;
for (my $i=0; $i< scalar @num; $i++) {
    if ($num[$i] != $currentElement) {
        $currentElement = $num[$i];
        $result++;
    }
}

print "The number of unique elements: $result.\n";