CSC 311: Data Structures
(Fall 2007)
Assignment 1: Chapters 1 through 4
Due by
1. Write a Java class, Flower, that has three instance variables of type String, int, and float, which respectively represent the name of the flower, its number of pedals, and price. Your class must include a constructor method that initializes each variable to an appropriate value, and your class should include methods for setting the value of each type, and getting the value of each type.
2. Write a short Java program that outputs all possible strings formed by using the characters 'c', 'a', 'r', 'b', 'o', and 'n' exactly once.
3. Draw a class inheritance diagram for the following set of classes:
o Class Goat extends Object and adds an instance variable tail and method milk() and jump().
o Class Pig extends Object and adds an instance variable nose and methods eat() and wallow().
o Class Horse extends Object and adds instance variables height and color, and methods run() and jump().
o Class Racer extends Horse and adds a method race().
o Class Equestrian extends Horse and adds an instance variable weight and methods trot() and isTrained().
4. Write a Java program that consists of three classes, A, B, and C, such that B extends A and C extends B. Each class should define an instance variable named "x" (that is, each has its own variable named x). Describe a way for a method in C to access and set A's version of x to a given value, without changing B or C's version.
5. Let A be an array of size n>=2 containing integers from 1 to n-1, inclusive, with exactly one repeated. Describe a fast algorithm for finding the integer in A that is repeated.
6. Write a recursive algorithm that counts the number of nodes in a singly linked list.
7. Give a pseudo-code description of the O(n)-time algorithm for computing the power function p(x,n). Also, draw the recursion trace of this algorithm for the computation of p(2, 5).
8. Order the following functions by asymptotic growth rate.
4nlogn + 2n, 210, 2logn,
3n + 100logn, 4n, 2n, n2 + 10n, n3, nlogn