CSci 2101 Data Structures: Problem set 2

Problem 1 (7 points)

The following form of cascading if/else statements may (or may not, depending on your code) be helpful:

if (cond1) {
   code 1
} else if (cond2) {
   code 2
} ...
  ...
} else if (condn {
   code n
} else {
   code n+1
}

Problem 2 (8 points)

NEW! As it turns out, an almost complete solution for this problem is found in Assignment 8 in CSci 1302 (Problem 5). However, you must modify the solution in two ways:

• Make it work in Java (as it is, it wouldn't work correctly -- why?)
• Rewrite this solution using a 'for' loop instead of the 'while' loop. You must use only one loop variable, so you should get rid of the variable j.

Problem 3 (10 points)

• An array of integers to keep track of how many times each of the sums has occurred (how many elements do you need in this array?)
• An array of doubles which will store the percent of the times each value of the sum has occurred (you only need to compute these percentages at the end of the program, after the loop).

• Put the line import java.util.*; as the very first line of your program file.
• In the beginning of main declare and initialize the random number generator:
  Random r = new Random();
  You only need to do this once in your program.
• In order to get a random integer between 0 and n (including 0, not including n) you need to call the method nextInt on r:
  k = r.nextInt(n);
  (where k is an integer variable to store the result). You need to figure out what to do to get the numbers between 1 and 6.

Problem 4 (15 points)

// Queue implementation with arrays

public class CharQueue {
	private char [] items = new char [100];
	private int first = -1; // in the book this is called 'head'
	private int last = 0;   // in the book this is called 'tail'
	private int length = 0;
	
	// a constructor, need for every class
	public CharQueue() {
		// do nothing	
	}

	// add the code for isEmpty

	// add the code for dequeue

	// add the code for enqueue
	
}

// Stack implementation with arrays

public class CharStack {
	private char [] items = new char [100];
	private int top = -1;
	
	// a constructor, need for every class
	public CharStack() {
		// do nothing	
	}
	
	public boolean isEmpty() {
		return top == -1;	
	}
	
	public char pop() {
		if(isEmpty()) {
		    System.out.println("Stack underflow");
		    System.exit(0);					
		}
		// if we got here, the stack is not empty
		char c = items[top];
		top--;
		return c;
	}
	
	public void push(char c) {
		if (top == 99) {
		    System.out.println("Stack overflow");
		    System.exit(0);
		}
		// if we got here, the stack has more room
		top++;
		items[top]=c;
	}
}

Problem 5 (5 points)

public class MoreWeirdLists {
    public static void main(String [] args) {
	// creating nodes
	Node one = new Node(1);
	Node two = new Node(2);
	Node three = new Node(3);
	Node four = new Node(4);
	two.setNext(one);

	LinkedList listOne = new LinkedList();
	LinkedList listTwo = new LinkedList();

	listOne.setFirst(one);
	listTwo.setFirst(two);
	listOne.addFront(three);
	
	listOne.getFirst().getNext().setNext(four);
	
	// what will be printed?

	System.out.println("Printing listOne:");
	Node n = listOne.getFirst();
	while (n != null) {
	    System.out.println(n.getData());
	    n = n.getNext();
	}

	System.out.println("Printing listTwo:");
	n = listTwo.getFirst();
	while (n != null) {
	    System.out.println(n.getData());
	    n = n.getNext();
	}
	
    }
}

Problem 6 (15 points)

1. a constructor with one integer parameter to set the data
2. public int getData()
3. public void setNext(DoubleNode dn)
4. public DoubleNode getNext()
5. public void setPrev(DoubleNode dn)
6. public DoubleNode getPrev()

1. a constructor with no parameters,
2. public boolean isEmpty()
3. public void setFirst(DoubleNode dn)
4. public DoubleNode getFirst()
5. public void setLast(DoubleNode dn)
6. public DoubleNode getLast() (there is no setLast())
7. public void addFront(DoubleNode dn)
8. public void addBack(DoubleNode dn)

• Starting from the front going towards the end,
• Starting at the end (using getLast() method) and going to the front (the elements would be printed in reverse order)

Make sure that your implementation creates a new node in every method that takes a node as a parameter. Returning a node from a method is fine.