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.
Sample solution:
// instance fields
private String name;
private int pedals;
private float price;
// constructor
public Flower(String n, int p, float r) {
name = n;
pedals = p;
price = r;
}
// Setters
public void setName(String n) { name = n;}
public void setPedals(int p) { pedals = p;}
public void setPrice(float p) { price = p;}
// getters
public String getName() { return name;}
public int getPedals() { return pedals;}
public float getPrice() { rturn price;}
}
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.
Sample
solution:
import java.util.ArrayList;
public class CharPermutation
{
private void permute(ArrayList<Character>
bag, ArrayList<Character> permutation) {
//
When the bag is empty, a full permutation exists
if (bag.isEmpty())
System.out.println(permutation);
else { // for each element left in the bag
for (int i=0; i<bag.size(); i++) {
//
take the element out of the bag
//
and put it at the end of the permutation
Character
c = (Character) bag.get(i);
bag.remove(
i );
permutation.add( c );
//
permute the rest of the bag
this.permute(bag,
permutation);
//
take the element off the permutation
//
and put it back in the bag
permutation.remove(permutation.size() - 1);
bag.add(i, c);
}
}
}
public void printPermutation(
char[] elements) {
ArrayList<Character> bag = new ArrayList<Character>();
ArrayList<Character> permutation = new ArrayList<Character>();
for (int i=0; i<elements.length; i++)
bag.add(new
Character(elements[i]));
this.permute(bag,
permutation);
}
public static void main( String[] args)
{
char[] elemts = {'c',
'a', 'r',
'b', 'o', 'n'};
new CharPermutation().printPermutations(elements);
}
}
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().
Sample solution: omit
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.
public class A <E> {
private E x;
......
public void setAx(E aX) {
x = aX;
}
public E getAx() {
return x;
}
}
public class B extends A {
private int x;
......
public void setBx(int aX) {
x = aX;
}
}
public class C extends B {
private int x;
......
public void setCx(int aX) {
x = aX;
}
public void setXInA(int aX) {
super.setAx(aX);
}
public int getXInA() {
return super.getAx();
}
}
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.
Sample solution:
Algorithm:
findRepeated
Input:
an array A with size n>1 containing integers between 1 and n-1, inclusive,
with exactly one repeated
Output: the integer that is repeated in A
Procedure:
Sort array A using merge sort or quick
sorting;
int i = 0;
whilt (A[i+1]!=A[i]) i++;
return A[i];
Analysis: Sorting takes time of O(nlogn)
While loop takes O(n)
Total: O(nlogn)
6. Write a recursive algorithm that counts the number of nodes in a singly linked list.
Sample
solution:
Algorithm: numNodes
Input: A singly linked list lst
Output: An integer of the number of nodes in
lst
Procedure:
if lst == null;
return 0;
else
Node
next = lst.getNext();
return 1 + numNodes(next);
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).
Sample
Solution:
Algorithm
p(x, n)
Input:
number x and integer n
Output:
number x^n
Procedure:
if n==0 return 1;
else return x*p(x, n-1);
8. Order the following functions by asymptotic growth rate.
4nlogn + 2n, 210, 2logn,
3n + 100logn, 4n, 2n, n2 + 10n, n3, nlogn
Sample solution:
210,
2logn, 3n + 100logn, 4n, nlogn, 4nlogn + 2n, n2 + 10n, n3,
2n