Assignment 1

COP 3530 - Data Structures

 

 

Instructions:

1.     Create a document (Word or pdf) that contains all your answers and all your code.

2.     Create a java and a class file for Part A.

3.     Send, by the due date (midnight), a soft copy of the document, the java file and the class file by email to Ramakrishna ramakrishna@cis.fiu.edu (of course in a single email).

4.     Turn in a hard copy of your document in class on the due date. If you are unable to come to class leave it in my mailbox the same day.

The due dates are specified in the main class web page.

 

Programming exercise:

 

A. (30 points)

Write a Java program that defines the Numbers class which stores a list of integers.

 

Include the following methods in the Numbers class:

  1. A default constructor that generates a list of random numbers in the range 0 to 1000 and store them in an array. The length of the array is also a random number from 100 to 1000. There is also a constructor that specifies the exact length l of the array (integers are again random as before).
  2. A method hasMultipleOf, that takes an integer z as parameter and checks if there is a multiple of z in that array.
  3. A method countOddNumbers, that doesn’t take any parameter but outputs the number of odd numbers present in the array.
  4. A method that takes an integer index n and returns the sum of all numbers present in array indexes from 0..n.( Note that there is a possibility of the input n being out of the array bounds. Specify how you will handle this in a Java comment.)
  5. Create get and set methods for setting and getting array values from the specified indexes passed as parameters.
  6. Finally, create a main function in this class to test the methods by creating objects and calling them. In particular, executing this program should results in the following:
    1. ask user to input the length l of the array
    2. create array
    3. ask user to input z and call hasMultipleOf(z) and output result
    4. call countOddNumbers and output result

 

 

 

Java questions:

 

B. (10 points)

Does java support Multiple Inheritance? What is the workaround? Write an example to demonstrate that.

 

C. (10 points)

What is function overloading in Java? Write a class where overloading is used and explain why it is useful in this particular class.

 

D. (10 points)

What are the advantages and disadvantages of Java being platform independent?

 

 

Algorithm Complexity exercises:

 

E. (5 points)

Order the following functions by asymptotic growth rate (if two functions have the same asymptotic growth rate, say so):

 

·        4nlogn + 2n

·        210

·        2n

·        3n + 100 log n

·        4n

·        n2 + 10n

·        n3

·        n log n

 

F. (10 points)

Show that 2n+1 is O (2n).

 

G. (25 points)

Write pseudocode for the best algorithm you can think of that given an array of integers finds the 10-th largest integer. What is the asymptotic complexity of your algorithm?