CSci 2101 Data Structures: Problem set 2

Due Wednesday, September 29th at 9:15am (before the class).

Problem 1 (7 points)

Write a program to find two smallest elements in an array of integers. Assume the array has at least two elements. Test your program carefully, keep the test examples in comments.

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
}
(fill in your appropriate conditions and code). If cond1 is true, code 1 will be executed, and the rest of the conditional expression will be skipped. Otherwise cond2 will be checked, and if it's true, code 2 will be executed, otherwise the next condition will be checked, and so on. If none of the conditions are true, code n+1 will be executed.

Problem 2 (8 points)

Write a program to reverse an array of integers. You may not use a stack, a queue, or another array in this program. Print out the array at the end of the program to check that it has been reversed. Note that the smallest length of the array is 1 (there are no "empty" arrays).

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:

Problem 3 (10 points)

Your task is to model the results of throwing two 6-sided dice (with the sides marked from 1 to 6) using a random number generator (see below). You will "throw" the two dice 100 times, each time computing the sum of the results of the two dice. You will need two arrays: To use the random number generator: To test your program, start off with a loop running 10 times. Print out the values of the two dice and count the occurrences of each of the sums. Once you convince yourself that the program is working, comment out the test prints and change the loop to go 100 times.

Problem 4 (15 points)

Write a queue implementation according to the specifications on pp. 202 and 203 in CLRS. The following file defines the constructor and the class variables (why do we need the length?). If an underflow or an overflow occurs, your program should print an error message and exit. You need to fill in the methods code.

// 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
	
}
You may use the following stack implementation as an example. Note that both a stack and a queue work with characters.

// 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;
	}
}
Use the file ShowQueue.java to test the queue. Modify the testing file as needed.

Problem 5 (5 points)

Consider the following program:

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();
	}
	
    }
}
Draw the memory picture that shows the final state of the lists and the nodes. What would be printed by the two loops according to your memory picture? Run the program and check the results. Redo the picture if needed.

Problem 6 (15 points)

Based on the classes Node and LinkedList, write the classes DoubleNode with data, next, and prev fields and the methods
  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()
and DoublyLinkedList to represent a doubly linked list with the references to the first and the last elements following methods:
  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)
Write a test program that prints the linked list twice:

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.


This is a problem set from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.