## 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:

• 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)

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 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() {
}

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);

listOne.setFirst(one);
listTwo.setFirst(two);

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:
• 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.

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.