CSci 2101 Data Structures: Problem set 2

Due Monday, Feb. 21st at 8pm.

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.

Problem 2 (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 3 (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
	
}
Use the Stack implementation as an example.

Use the file ShowQueue.java to test the queue. Modify the testing file as needed.

Problem 4 (10 points)

Write a program that creates a copy of a linked list. More specifically, create a linked list list1, add some nodes to it. Then declare a new linked list lists2 and add some nodes to it which are have the same values as the nodes in list1.

Important: You have to create copies of the nodes, not share the nodes between the two lists. To make sure that nodes are not shared, change one of the lists, and print out both lists to make sure that the second one hasn't changed. This way of copying (where all the elements that a data structure consists of are copied and not shared) is called a deep copy, as opposed to a shallow copy (where the elements are shared).

Problem 5 (5 points)

Consider the following program:

public class WeirdLists {
    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);

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

	// adding elements to list 1
	listOne.addFront(one);
	listOne.addFront(two);

	// add one element to list 2 
	listTwo.addFront(three);	

	// changing node one
	one.setNext(three);

	// changing something in the second list
	listTwo.getFirst().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 object diagram 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 diagram if needed. Submit the diagram.

Problem 6 (15 points)

Your task is to implement a double-linked list class based on the classes Node and LinkedList. More precisely, you need to write two classes.

The first class is DoubleNode which is similar to the class Node, but has a reference to the previous element, as well as the to next one. The DoubleNode class has the following methods:

  1. a constructor with one integer parameter to set the data. The references to the next and the previous DoubleNodes are set to null.
  2. public int getData()
  3. public void setNext(DoubleNode dn)
  4. public DoubleNode getNext()
  5. public void setPrev(DoubleNode dn)
  6. public DoubleNode getPrev()
Based on the class DoubleNode, write a class DoubleLinkedList. The class has the following methods:
  1. a constructor with no parameters,
  2. public boolean isEmpty()
  3. public DoubleNode getFirst() returns the reference to the first DoubleNode in the list. If there is no such node, returns null. The list doesn't change.
  4. public DoubleNode getLast() returns the reference to the last DoubleNode in the list. If there is no such node, returns null. The list doesn't change.
  5. public void addFront(DoubleNode dn) Adds a new node to the front of the list.
  6. public void addBack(DoubleNode dn) Adds a new node to the back of the list.
  7. public void removeFront() Removes the first element from the list. Doesn't return anything.
  8. public void removeBack() Removes the last element from the list. Doesn't return anything.
Write a test program that prints the linked list twice:
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.