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

Exercises:

(1)

Solution (a): not using hash/map.

FindMajorityElement(A: array of numbers):
input:
    A: the array
output:
    found: whether a majority element is found.
    result: the majority element if found.
Algorithm:

[1] N <- Size(A);
[2] if (N==1)
       found <- true;
       result <- A[0];
       return;
    end if;
[3] B <- Sort(A);   /* A not altered. */
[4] currentValue <- B[0];
[5] candidateValue <- B[0];
[6] maxCount <- 1;
[7] currentCount <- 1;
[8] for i from 0 to N-2
       if (B[i] == B[i+1]
          currentMaxCount++;
       else
          currentValue = B[i+1];
          if currentCount > maxCount
             maxCount <- currentCount;
          end if;
          currentCount <- 1;
       end if;
    end for;
[9] if maxCount > (N div 2) /* integer division */
       fournd <- true;
       result <- candidateValue;
    else
       found <- false;
    end if;
   
Time complexity O(N lg N), that of the sorting call.
            
Solution (b): using hash/map.

FindMajorityElement(A: array of numbers):
input:
    A: the array
output:
    found: whether a majority element is found.
    result: the majority element if found.
Algorithm:

[1] N <- Size(A);
[2] Hash elementCounts <- {}
[3] for every element A[i] in A
       if A[i] exists as an key of elementCounts
          elementCounts[A[i]]++;
       else
          elementCounts[A[i]] <- 1;
    end for;
[4] for every key k in elementCounts
       if elementCounts[k] > (N div 2) /* integer division */
          found <- true;
          result <- k;
       end if;
    end for;
[5] found <- false;

Time complexity: O(N)
 

(2) O(N²)

(3) O(N lgN)

(4)

(a) ~2.5 ms (5 times longer
(b) ~3.5 milliseconds (or 5 * log(500)/log(100)) longer; however, this is the case where the assumption that low-order terms are negligible" is more problematic.
(c) ~12.5 milliseconds (25 times longer)
(d) ~62.5 milliseconds (125 times longer)

(5)

Fragment 1:O(N)
Fragment 2: O(N)
Fragment 3: O(N²)
Fragment 4: O(N)
Fragment 5: O(N³)
Fragment 6: O(N²)
Fragment 7: O(N⁵)
Fragment 8: O(log N)

Program:

(1) For example, using algorithm (b) in Perl (lightly documented):

use strict;
# 
#    majorityElement.pl
#
#    Print the majority element of a sequence of integers if it exists.
#    Usage: majorityElement.pl int1 int2 int3 ...
#     

#   Get the integers.
@ARGV >= 1 || die "usage: majorityElement.pl int1 int2 int3 ... ";
my @num = @ARGV;
my $threshold = int((scalar @ARGV)/2);   # N div 2 where N: number of integers.

my %elementCounts = ();
my $i;

foreach $i (@num ) { $elementCounts{$i}++; }

foreach $i (keys %elementCounts) {
    if ($elementCounts{$i} > $threshold) {
        print "The majority element is $i.\n";
        exit;
    }
}

#   No majority element.
print "There is no majority element.\n";