## 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:
• 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).
To use the random number generator:
• 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.
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);

// adding elements to list 1

// add one element to list 2

// 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 `DoubleNode`s 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:
• 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)

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.