COP 3503H Fall 2004 Exam #2 Solution
1) (20 pts) For this question you will write a simplified linked list class. The Node class will be given to you as will a framework for your code along with pre and post conditions for each method you need to write. Write each method according to the given pre and post conditions.
public class Node {
public String name;
public Node next;
public Node(String s) {
name = s;
next = null;
}
}
public class LinkedList {
private Node head;
// Pre-condition: none
// Post-condition: Returns an empty LinkedList object.
public LinkedList() {
head = null;
}
// Pre-condition: none
// Post-condition: Creates a Node storing s and inserts this
// Node to the front of the current LinkedList
// object
public void insertToFront(String s) {
// Create the new node.
Node temp = new Node(s);
// Attach it to the front of the list.
temp.next = head;
// Adjust the new head of the list.
head = temp;
}
// Pre-condition: none
// Post-condition: If no node in the current object stores s,
// this method returns false and does nothing else.
// If s is stored in a Node in the current object,
// this node will be moved to the front of the
// current object. Then true will be returned.
public boolean searchAndFront(String s) {
// Take care of the empty list.
if (head == null)
return false;
// If the first node has s, return true, and no other change is
// necessary.
if (s.equals(head.name))
return true;
Node temp = head;
// Iterate through the list.
while (temp.next != null) {
// See if the next node stores s.
if (s.equals(temp.next.name)) {
Node save = temp.next; // Save a reference to the node with s.
temp.next = temp.next.next; // Patch this node out of the list.
save.next = head; // Attach it to the front of the list.
head = save; // Adjust the head of the list.
}
else
temp = temp.next; // Advance to the next node.
}
}
}
2) (15 pts) For this question you will write a simplified hash table class that uses the linear chaining hashing technique. Assume that the methods from question 1 work when answering this question. A framework is provided for you below along with pre and post conditions for each method you need to write. Write each method according to these pre and post conditions.
public class HashTable {
private LinkedList[] items;
// Pre-condition: size is a positive prime number
// Post-condition: An hash table with size empty linked lists is
// created. If the pre-condition is not met, the
// default size of the hash table is 101.
public HashTable(int size) {
items = new LinkedList[size]; // Allocate the array for the table.
for (int i=0; i<size; i++)
items[i] = new LinkedList(); // Init. each empty linked list.
}
// Pre-condition: s is not null.
// Post-condition: Returns the hash Value of s for the current
// object.
public int hashFunction(String s) {
return s.hashCode()%items.length;
}
// Pre-condition: s is not null.
// Post-condition: A Node object storing s will be inserted into the
// front of the linked list corresponding to the hash
// value of s.
public void insert(String s) {
// Access the proper linked list and insert s.
items[hashFunction(s)].insertToFront(s);
}
// Pre-condition: s is not null.
// Post-condition: if s is NOT stored in the current object, false is
// returned and nothing else is done. If s is found
// in the current object, its Node will be moved to
// the front of the linked list it is currently in
// and then true is returned.
public boolean search(String s) {
// Access the proper linked list and return the search from there.
return items[hashFunction(s)].searchAndFront(s);
}
}
3) (5 pts) Show the result of inserting 13 from the AVL tree below:
10
/ \
5 20
\ / \
7 15 27
/ \
12 17
10
/ \
5 15
\ / \
7 12 20
\ / \
13 17 27
4) (7 pts) Show the result of deleting 7 from the AVL tree below:
10
/ \
5 20
/ \ / \
2 7 15 27
/ / \ \
1 12 17 33
\
13
10, after first rotation.
/ \
2 20
/ \ / \
1 5 15 27
/ \ \
12 17 33
\
13
15, after final rotation.
/ \
10 20
/ \ / \
2 12 17 27
/ \ \ \
1 5 13 33
5)
a) (3 pts) Explain why the original tree from question four could not be a red-black tree.
This was a bad question. (Everyone will received full credit.) That tree could be a Red-Black Tree. Here's a valid coloring with red nodes underlined:
10
/ \
5 20
/ \ / \
2 7 15 27
/ / \ \
1 12 17 33
\
13
b) (10 pts) Insert the values 3, 11 and 23 into the original tree from question 4, using a standard binary search tree insert. This adjusted tree could be a red-black tree. Denote a valid coloring for this tree that shows that it could be a valid red-black tree. To differentiate red nodes from black nodes, simply underline the red nodes and omit that mark from the black nodes.
10
/ \
5 20
/ \ / \
2 7 15 27
/ \ / \ / \
1 3 12 17 23 33
/ \
11 13
c) (5 pts) Draw the corresponding 2-4 Tree to the red-black tree from part b.
10
/ \
5 15 , 20
/ \ / | \
1 7 11 17 23
2 12 27
3 13 33
6) (5 pts) What is the result of deleting 35 from the 2,4 Tree shown below:
10, 20, 30
/ | | \
4 12 22, 24 35
10, 20, 24
/ | | \
4 12 22 30
7) (5 pts) What is the result of deleting 11 from the 2,4 Tree shown below:
10, 20, 30
/ | | \
4 12 22, 24 35
/ \ / \ / | \ / \
2 6 11 14 21 23 27 31 39
20, 30
/ | \
4 , 10 22, 24 35
/ | \ / | \ / \
2 6 12,14 21 23 27 31 39
8) (25 pts) Fill in the methods makeHeap, percolateUp and removeMin in the Heap class below. Use clues from the given code to determine how to go about your task.
import java.io.*;
public class Heap {
private int[] heaparray;
private int size;
// Pre-condition: none
// Post-condition: Allocates a default heap capable of storing 99
// elements.
public Heap() {
heaparray = new int[100];
size = 0;
}
// Pre-condition: values is not null.
// Post-condition: Creates a Heap object from the given array of
// integers.
public Heap(int[] values) {
heaparray = new int[values.length+1];
for (int i=1; i<heaparray.length; i++)
heaparray[i] = values[i-1];
size = values.length;
makeHeap();
}
// Pre-condition: heaparray stores random integers in array locations
// 1 through size.
// Post-condition: heaparray has arranged the original integers into
// a valid heap configuration.
private void makeHeap() {
// Must go through half the nodes in reverse order.
for (int i=size/2; i> 0; i--) {
percolateDown(i);
}
}
// Pre-condition: index is in between 1 and size, inclusive, and all
// values stored in the current object satisfy the
// heap invariant except for possibly the item stored
// in index.
// Post-condition: The value stored in index will be "percolated
// Down" so that the heap property is achieved.
private void percolateDown(int index) {
if ((2*index+1) <= size) {
int min = minimum(heaparray[2*index], 2*index,
heaparray[2*index+1], 2*index+1);
if (heaparray[index] > heaparray[min]) {
swap(index, min);
percolateDown(min);
}
}
else if (size == 2*index) {
if (heaparray[index] > heaparray[2*index])
swap(index,2*index);
}
}
// Precondition: index is a positive integer in between 1 and size,
// and all nodes are in proper heap order except for
// possibly the node stored in index.
// Postcondition: The value stored in index is percolated Up through
// the rest of the heap resulting in a valid heap
// configuration.
private void percolateUp(int index) {
// Can't percolateUp the root node!
if (index > 1) {
// Check if the current node needs to swap with its parent.
if (heaparray[index/2] > heaparray[index]) {
swap(index, index/2); // Do the swap.
percolateUp(index/2); // Continue percolating Up this node.
}
}
}
// Pre-condition: none
// Post-condition: value is inserted into the current object.
public void insert(int value) {
if (size+1 == heaparray.length) {
int[] temp = new int[2*heaparray.length];
for (int i=1; i<heaparray.length; i++)
temp[i] = heaparray[i];
heaparray = temp;
}
size++;
heaparray[size] = value;
percolateUp(size);
}
// Pre-condition: Current object is non-empty.
// Post-condition: Removes the minimum value stored in the current
// object, restores the heap and returns this
// minimum value.
public int removeMin() {
int retval = heaparray[1]; // Store the return value.
heaparray[1] = heaparray[size]; // Copy the last value into the
// first spot.
size--; // Adjust the size of the heap.
percolateDown(1); // Percolate Down the out of place node.
return retval; // Return the minimum value.
}
// Pre-condition: index1 and index2 are positive integers in between
// 1 and size, inclusive.
// Post-conditions: The values stored in index1 and index2 of
// heaparray are swapped.
private void swap(int index1, int index2) {
int temp = heaparray[index1];
heaparray[index1] = heaparray[index2];
heaparray[index2] = temp;
}
// Pre-condition: a and b are values stored in heaparray in
// indexes indexa and indexb, respectively.
// Post-condition: The index storing the lower value is returned.
private int minimum(int a, int indexa, int b, int indexb) {
if (a < b)
return indexa;
else
return indexb;
}
}