CSCI 3333.3
Data Structures
Spring 2013
Homework #4

Due Date: Feb 27th (Wednesday)

Exercises:

(1) (35%) Exercise 5.33, page 224, Textbook. Your algorithm does not need to be linear. Provide the time complexity of your algorithm.

(2) (5%) Exercise 5.7, page 217, Textbook.

(3) (5%) Exercise 5.8, page 217, Textbook.

(4) (10%) Exercise 5.14, page 218, Textbook.

(5) (20%) Exercise 5.20 (a) only, page 220, Textbook.

Program:

(1) (35%) Implement your algorithm in Exercise (1) as a program majorityElement. It takes a sequence of integers as command line arguments and print out the majority element if found. For example, if you are using Java, your program should be majorityElement.java. Test runs should look like this:

c:\whatever\java majorityElement 8
The majority element is 8.

c:\whatever\java majorityElement 8 7
There is no majority element.

c:\whatever\java majorityElement 8 8
The majority element is 8.

c:\whatever\java majorityElement 8 5 4 4 4 7
There is no majority element.

c:\whatever\java majorityElement 8 5 4 4 4 7 4
The majority element is 4.

c:\whatever\java majorityElement 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8
The majority element is 8.

c:\whatever\java majorityElement 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 87
The majority element is 8.

c:\whatever\java majorityElement 1000000 1000000
The majority element is 1000000.

 

Submission