![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
In addition to time complexity, there are several other factors like CPU speed, compiler optimization, memory access speed, & data input efficiency. Based on your understanding, which one is most important? Why?
For PCs, memory access speed is the most important, because what users expect the most is high multitasking performance.
On the other hand, for servers, data input efficiency is the most important, especially for database systems. If there is a disk I/O bottleneck on a system, its performance will be decreasing significantly.
Of course, CPU is important as well, but I think CPU performance can not only be measured by clock speeds. It depends on CPU architectures due to differences in vendors.
Chapter 1 discusses 'Software Quality' related topics in detail. Do not look at it right now :-) When you hear the term 'Software Quality', what comes to your mind right away? Explain in your own words.
From the aspect of "Software Quality" for business, you should include not only highly functional programs, but also well-written software design documents such as class diagrams, table definitions, ER diagrams, wire frames, also test data and test cases.
Do the following Exercises in Lewis and Chase (pp 24-25)
As listed under Course Content, I developed the following multimedia tutorial/lecture on inheritance & polymorphism. Turn ON your speakers to hear the audio before opening these links in a new tab to play these Flash videos:
http://sites.google.com/site/jeyak7/inheritance1.swf (Part 1)
http://sites.google.com/site/jeyak7/inheritance2.swf (Part 2)
You can find the PowerPoint presentation and code in this zip:
http://sites.google.com/site/jeyak7/inheritance.zip
Give an example where polymorphism is appropriate, and explain why you think it is a reasonable example. No need for code here, just the names of a few classes and at least one polymorphic method. You may find it helpful to consider some fields (attributes, instance variables) that are common to a parent class, and some others that are unique to each child class. This will require at least one parent and two child classes.
You may find the following presentations helpful too - they are focused on interfaces, but cover many other aspects of Java programming along the way:
http://sandsduchon.org/duchon/interfaces/InterfacesPart1.pdf
http://sandsduchon.org/duchon/interfaces/InterfacesPart2.pdf
http://sandsduchon.org/duchon/math/trees.html
http://sandsduchon.org/duchon/jdk/Java-Exceptions.html
Polymorphism is a mechanism in object-oriented programming that enables to the programmer to send a message to objects but make them work differently as a function of each objects. The advantage of using polymorphism is that the programmer doesn't have to modify the caller method to change the program behaviors.
For example, if there are three classes named Shape, Rectangle, and Triangle, and Shape is the parent of other two classes, polymorphism is utilized. If you want to calculate the area of them, you can define a getArea method in Shape class as an abstract method. The function of this method is only to draw. Then, you can define another getArea methods, in which are implemented detailed functions, in Rectangle and Triangle class.
Method overloading is one of the most important functions to work polymorphism that is to define two or more methods of a same name with a different return value and number/type of arguments within the same class.
Evaluate the following postfix expressions, then create one of your own and evaluate that also.
8 7 6 5 - - -
8 7 - 6 5 - -
8 7 - 6 - 5 -
8 7 6 - - 5 -
8 7 6 - 5 - -
(1) 8 7 6 5 - - -
= 8 7 1 - -
= 8 6 -
= 2
(2) 8 7 - 6 5 - -
= 1 6 5 - -
= 1 1 -
= 0
(3) 8 7 - 6 - 5 -
= 1 6 - 5 -
= -5 5 -
= -10
(4) 8 7 6 - - 5 -
= 8 1 - 5 -
= 7 5 -
= 2
(5) 8 7 6 - 5 - - = 8 1 5 - - = 8 -4 - = 12
Here is my own:
3 4 + 6 2 - * 4 /
= 7 6 2 - * 4 /
= 7 4 * 4 /
= 28 4 /
= 7
Do Programming Project PP 3.7 on pg 67 of Lewis and Chase.
CMSC350_Homework1.pdfimport java.util.*;
import javax.swing.*;
public class InfixToPostfixTranslator {
public static void main(String[] args) {
String expression;
String token;
String operator;
StringTokenizer tokens;
int parenthesis=0;
//create an output queue
LinkedList<String> postfixQueue = new LinkedList<String>();
//create empty stack of pending string operators
Stack operatorStack = new Stack();
expression = JOptionPane.showInputDialog( null, "Enter infix expression", "Input Dialog", JOptionPane.PLAIN_MESSAGE);
tokens = new StringTokenizer(expression);
while (tokens.hasMoreTokens()) { //hasn't gone thru all the "tokens"
token = tokens.nextToken(); //get next "token" from input string
if (isNumeric(token)) { //it's an operand (a number)
//extract int from String token, create Integer object, add token to queue:
postfixQueue.addLast(token);
}
else if (isOperator(token)) { //token is an operator
if (token.equals("(")) { //token is "("
parenthesis++; //for status of parentheses
operatorStack.push(token); //push token to stack
} else if (token.equals(")")) {
parenthesis++; //for status of parentheses
while (true) {
operator = (String) operatorStack.pop(); //pop until "(" found
if (operator.equals("(")) {
break;
} else {
postfixQueue.addLast(operator);
}
}
} else if (operatorStack.isEmpty()) {
operatorStack.push(token); //push token to stack
} else { //if operatorStack is not empty
String stackTop = (String) operatorStack.peek(); //get the stack top value
//token has higher precedence than stack top
if (operatorPrecedence(token) > operatorPrecedence(stackTop)) {
operatorStack.push(token);
//token has same or lower precedence than stack top
} else if (operatorPrecedence(token) == operatorPrecedence(stackTop)
|| operatorPrecedence(token) < operatorPrecedence(stackTop)) {
if (parenthesis % 2 != 0) { //not closed parenthesis
operatorStack.push(token);
} else if (parenthesis == 0) { //there is no parenthesis
if (operatorPrecedence(token) < operatorPrecedence(stackTop)) {
operator = (String) operatorStack.pop();
postfixQueue.addLast(operator);
int count = postfixQueue.size();
if (count % 2 != 0) {
operatorStack.push(token);
} else {
postfixQueue.addLast(token);
}
} else if (operatorPrecedence(token) == operatorPrecedence(stackTop)) {
operator = (String) operatorStack.pop();
postfixQueue.addLast(operator);
operatorStack.push(token);
}
} else { //closed parenthesis
operator = (String) operatorStack.pop();
postfixQueue.addLast(operator);
operatorStack.push(token);
}
}
}
} else { //token is neither a number nor an operator
System.out.println(token + " is not verified character.");
}
}
//pop all the rest of operators off stack, and add them to queue
while (!operatorStack.isEmpty()) {
operator = (String) operatorStack.pop();
postfixQueue.addLast(operator);
}
//display both infix expression and postfix expression
System.out.println("Infix Expression : " + expression);
System.out.print("Postfix Expression : ");
for (int i=0; i < postfixQueue.size(); i++) {
System.out.print(postfixQueue.get(i) + " ");
}
System.exit(0);
}
static boolean isNumeric(String n) {
try {
Double.parseDouble(n);
return true;
} catch (NumberFormatException e) {
return false;
}
}
static boolean isOperator(String t) {
if (t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/") ||
t.equals("%") || t.equals("(") || t.equals(")"))
return true;
else
return false;
}
static int operatorPrecedence(String o) {
if (o.equals("*") || o.equals("/")) {
return 2;
} else {
return 1;
}
}
}
Describe an interesting application/analogy of the linked list data structure.
LinkedList is suited for a FIFO (queue) data structure, because when inserting an element into a LinkedList, it is not reallocated elements unlike ArrayList. Queue is utilized for such as waiting print jobs of a network printer on a LAN.
How does memory consumption vary between linked lists and arrays for storing n items?
According to an article by Chris Bailey, Java Service Architect, IBM, if you compare an array list and a linked list, an array list's memory consumption is 4 bytes per entry, and a linked list's memory consumption is 24 bytes per entry because each its entry needs both value area and address area.
Incidentally, an array list reserves more memory area than a linked list does initially. Because an array list creates ten entries, although a linked list does an entry initially.
Do the following Exercises in Lewis and Chase (pp 66 and 96)
Describe a real-world scenario or an interesting application of the stack (LIFO) data structure. Try to write something new, instead of repeating popular ones already posted in the forum.
An example of stack is Tetris game, which is one of the most popular computer games in the world. When you fit falling pieces of blocks in suitable place, blocks will disappear in order from the top.
Do Programming Project PP 6.14 on pg 182 of Lewis and Chase, implementing a doubly linked list class.
import java.util.*;
public class DoubleIterator<E> {
private DoubleList<E> doubleList;
private int index;
public DoubleIterator(DoubleList<E> doubleList) {
this.doubleList = doubleList;
index = -1;
}
public boolean hasNext() {
if (index < doubleList.size()-1) {
return true;
} else {
return false;
}
}
public E next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
index++;
return doubleList.get(index);
}
}
import java.util.*;
public class DoubleReverseIterator<E> {
private DoubleList<E> doubleList;
private int index;
public DoubleReverseIterator(DoubleList<E> doubleList) {
this.doubleList = doubleList;
index = doubleList.size();
}
public boolean hasPrevious() {
if (index > 0) {
return true;
} else {
return false;
}
}
public E previous() {
if (!hasPrevious()) {
throw new NoSuchElementException();
}
index--;
return doubleList.get(index);
}
}
public class DoubleNode<E> {
private DoubleNode<E> next;
private E element;
private DoubleNode<E> previous;
// Create an empty node.
public DoubleNode() {
next = null;
element = null;
previous = null;
}
// Create a node storing the specified element.
// @param elem the element to be stored into the new node
public DoubleNode(E elem) {
next = null;
element = elem;
previous = null;
}
// Returns the node that follows this one.
// @return the node that follows the current one
public DoubleNode<E> getNext() {
return next;
}
// Returns the node that precedes this one.
// @return the node that precedes the current one
public DoubleNode<E> getPrevious() {
return previous;
}
// Sets the node that follows this one.
// @param dnode the node to be set as the one to follow the current one
public void setNext(DoubleNode<E> dnode) {
next = dnode;
}
// Sets the node that precedes this one.
// @param dnode the node to be set as the one to precedes the current one
public void setPrevious(DoubleNode<E> dnode) {
previous = dnode;
}
// Returns the element stored in this node.
// @return the element stored in this one
public E getElement() {
return element;
}
// Sets the element stored in this node.
// @param elem the element to be stored in this node
public void setElement(E elem) {
element = elem;
}
}
public class DoubleOrderedList<E> {
private DoubleNode<E> dummy;
private int length = 0;
// Constructor
public DoubleOrderedList() {
// Creates a dummy cell and sets next and previous to itself
dummy = new DoubleNode<E>(null);
dummy.setNext(dummy);
dummy.setPrevious(dummy);
}
// Adds an element
public void add(E elem) {
DoubleNode<E> dnode = new DoubleNode<E>(elem);
dnode.setNext(dummy.getNext());
dummy.setNext(dnode);
length++;
}
// Removes first node, if empty, returns null
public E removeFirst() {
length--;
DoubleNode<E> dnode = dummy.getNext();
if (dnode == dummy) {
return null;
}
dnode.getNext().setPrevious(dnode.getPrevious());
dnode.getPrevious().setNext(dnode.getNext());
return dnode.getElement();
}
// Removes last node, if empty, returns null
public E removeLast() {
length--;
DoubleNode<E> dnode = dummy.getPrevious();
if (dnode == dummy) {
return null;
}
dnode.getPrevious().setNext(dnode.getNext());
dnode.getNext().setPrevious(dnode.getPrevious());
return dnode.getElement();
}
// Removes an element at specified index
public E remove(int index) {
length--;
DoubleNode<E> dnode = dummy.getNext();
if (dnode == dummy) {
return null;
}
for (int i = 0; i < index; i++) {
dnode = dnode.getNext();
}
dnode.getNext().setPrevious(dnode.getPrevious());
dnode.getPrevious().setNext(dnode.getNext());
return dnode.getElement();
}
// Returns first element, if empty, returns null
public E getFirst() {
DoubleNode<E> dnode = dummy.getNext();
if (dnode == dummy) {
return null;
}
return dnode.getElement();
}
// Returns last element, if empty, returns null
public E getLast() {
DoubleNode<E> dnode = dummy.getPrevious();
if (dnode == dummy) {
return null;
}
return dnode.getElement();
}
// Gets an element at specified index
public E get(int index) {
DoubleNode<E> dnode = dummy.getNext();
for (int i = 0; i < index; i++) {
if (dnode == dummy) {
return null;
}
dnode = dnode.getNext();
}
return dnode.getElement();
}
// toString
public String toString() {
StringBuilder sb = new StringBuilder("[");
for (DoubleNode<E> dnode = dummy.getNext(); dnode != dummy; dnode = dnode.getNext()) {
sb.append(dnode.getElement()); // Adds a string to sb
if (dnode.getNext() != dummy) {
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
// Returns size of list
public int size() {
return length;
}
// Checks list empty or not
public boolean isEmpty() {
return length == 0;
}
}
public class DoubleList<E> {
private DoubleNode<E> dummy;
private int length = 0;
// Constructor
public DoubleList() {
// Creates a dummy cell and sets next and previous to itself
dummy = new DoubleNode<E>(null);
dummy.setNext(dummy);
dummy.setPrevious(dummy);
}
// Adds an element to front
public void addFirst(E elem) {
DoubleNode<E> dnode = new DoubleNode<E>(elem);
dnode.setPrevious(dummy);
dnode.setNext(dummy.getNext());
dummy.getNext().setPrevious(dnode);
dummy.setNext(dnode);
length++;
}
// Adds an element to rear
public void addLast(E elem) {
DoubleNode<E> dnode = new DoubleNode<E>(elem);
dnode.setNext(dummy);
dnode.setPrevious(dummy.getPrevious());
dummy.getPrevious().setNext(dnode);
dummy.setPrevious(dnode);
length++;
}
// Removes first node, if empty, returns null
public E removeFirst() {
length--;
DoubleNode<E> dnode = dummy.getNext();
if (dnode == dummy) {
return null;
}
dnode.getNext().setPrevious(dnode.getPrevious());
dnode.getPrevious().setNext(dnode.getNext());
return dnode.getElement();
}
// Removes last node, if empty, returns null
public E removeLast() {
length--;
DoubleNode<E> dnode = dummy.getPrevious();
if (dnode == dummy) {
return null;
}
dnode.getPrevious().setNext(dnode.getNext());
dnode.getNext().setPrevious(dnode.getPrevious());
return dnode.getElement();
}
// Removes an element at specified index
public E remove(int index) {
length--;
DoubleNode<E> dnode = dummy.getNext();
if (dnode == dummy) {
return null;
}
for (int i = 0; i < index; i++) {
dnode = dnode.getNext();
}
dnode.getNext().setPrevious(dnode.getPrevious());
dnode.getPrevious().setNext(dnode.getNext());
return dnode.getElement();
}
// Returns first element, if empty, returns null
public E getFirst() {
DoubleNode<E> dnode = dummy.getNext();
if (dnode == dummy) {
return null;
}
return dnode.getElement();
}
// Returns last element, if empty, returns null
public E getLast() {
DoubleNode<E> dnode = dummy.getPrevious();
if (dnode == dummy) {
return null;
}
return dnode.getElement();
}
// Gets an element at specified index
public E get(int index) {
DoubleNode<E> dnode = dummy.getNext();
for (int i = 0; i < index; i++) {
if (dnode == dummy) {
return null;
}
dnode = dnode.getNext();
}
return dnode.getElement();
}
// toString
public String toString() {
StringBuilder sb = new StringBuilder("[");
for (DoubleNode<E> dnode = dummy.getNext(); dnode != dummy; dnode = dnode.getNext()) {
sb.append(dnode.getElement()); // Adds a string to sb
if (dnode.getNext() != dummy) {
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
// Returns size of list
public int size() {
return length;
}
// Checks list empty or not
public boolean isEmpty() {
return length == 0;
}
// Forward iteration
public DoubleIterator<E> forwardIterator() {
return new DoubleIterator<E>(this);
}
// Backward iteration
public DoubleReverseIterator<E> backwardIterator() {
return new DoubleReverseIterator<E>(this);
}
}
public class TestDoubleOrderedList {
public static void main(String[] args) {
System.out.println("*** DoubleList *** ");
// Instantiates a DoubleList object
DoubleList<Integer> dlist = new DoubleList<Integer>();
// Shows the list size
System.out.println("List size: " + dlist.size());
// Returns true if the list size is 0.
System.out.println("isEmpty(): " + dlist.isEmpty());
// Adds elements to the list
System.out.println("Adds elements to front:");
dlist.addFirst(3);
System.out.println(dlist);
dlist.addFirst(20);
System.out.println(dlist);
dlist.addFirst(15);
System.out.println(dlist);
System.out.println("Adds elements to rear:");
dlist.addLast(5);
System.out.println(dlist);
dlist.addLast(50);
System.out.println(dlist);
dlist.addLast(1);
System.out.println(dlist);
// Shows the list size
System.out.println("List size: " + dlist.size());
// Returns true if the list size is 0.
System.out.println("isEmpty(): " + dlist.isEmpty());
// Forward iteration
System.out.println("Elements in order:");
DoubleIterator<Integer> fit = dlist.forwardIterator();
while(fit.hasNext()) {
int item = fit.next();
System.out.print(item + " ");
}
System.out.println();
// Backward iteration
System.out.println("Elements in reverse order:");
DoubleReverseIterator<Integer> bit = dlist.backwardIterator();
while(bit.hasPrevious()) {
int item = bit.previous();
System.out.print(item + " ");
}
System.out.println();
// Gets elements
System.out.println("get(2) result: " + dlist.get(2));
System.out.println("getFirst result: " + dlist.getFirst());
System.out.println("getLast result: " + dlist.getLast());
// Removes elements
System.out.println("removeFirst() result: " + dlist.removeFirst());
System.out.println(dlist);
System.out.println("removeLast() result: " + dlist.removeLast());
System.out.println(dlist);
System.out.println("remove(2) result: " + dlist.remove(2));
System.out.println(dlist);
System.out.println();
System.out.println("*** DoubleOrderedList *** ");
// Instantiates a DoubleOrderedList object
DoubleOrderedList<Integer> dolist = new DoubleOrderedList<Integer>();
// Shows the list size
System.out.println("List size: " + dolist.size());
// Returns true if the list size is 0.
System.out.println("isEmpty(): " + dolist.isEmpty());
// Adds elements to the list
dolist.add(15);
System.out.println(dolist);
dolist.add(20);
System.out.println(dolist);
dolist.add(3);
System.out.println(dolist);
dolist.add(5);
System.out.println(dolist);
dolist.add(50);
System.out.println(dolist);
dolist.add(1);
System.out.println(dolist);
// Shows the list size
System.out.println("List size: " + dolist.size());
// Returns true if the list size is 0.
System.out.println("isEmpty(): " + dolist.isEmpty());
}
}
Describe an interesting application of recursion. Try to find applications outside our class. If you do, please give good citations.
An example of a recursive function is DNS (Domain Name System) resolvers. A DNS resolver sends queries to DNS name servers recursively in order to find out DNS resource records for a specific domain.
Here is the equation to compute nth Fibonacci number fib(n) where:
fib(n) = 1, if n = 1 or 2
= fib(n-1) + fib(n-2) when n > 2
Implement a recursive solution based on this equation. What is the time complexity? Is it possible to write more optimal iterative version? What is the time complexity?
Time complexity for recursive solution is (2^n) and for iterative solution is O(n). My code is as below.
public class FibonacciCalculator {
// Recursive solution
public int recurseFib(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return recurseFib(n-1) + recurseFib(n-2);
}
}
// Iterative solution
public int iterateFib(int n) {
int f0 = 0;
int f1 = 1;
int f2 = 1;
if (n == 0) {
return f0;
} else if (n == 1) {
return f1;
} else if (n ==2) {
return f2;
} else {
for(int i = 2; i < n; i++) {
f0 = f1;
f1 = f2;
f2 = f1 + f0;
}
}
return f2;
}
}
Do ONE of the following Exercises in Lewis and Chase (pg 205)
Which sorting algorithm is the most useful one, when the input elements are already almost sorted? Let us define the problem more precisely: Let us say we have an input array of n elements. Each element's position in the input array is guaranteed to be maximum k positions away from its sorted position in the output array. Let us assume k is very small compared to n. Which algorithm is the best for this scenario? Feel free to make a few minor changes to any algorithm to improve the efficiency. Hint: Algorithm should run in O(kn) time (since k is a constant, it is really O(n) time).
I also agree with the idea that the insertion sort is the most useful on small or almost sorted lists because it compares elements in order from the front. Conversely, the worst case time complexity when the list is in descending order is O(n^2).
Quick Sort has the worst case time complexity of O(n2) while the average case time complexity is O(n log n). Do a limited research in the web and explain about it in your own words.
The reason why average time complexity of Quick Sort is O(n log n) is that the number of elements in divided groups decrease at a rapid rate. It will averagely be half every time items are divided. When the number becomes one, the sort is finished. If the number would be half every time dividing into m groups, the number of groups would be n/2m. When n/2m is one, m is log2n.
Do Programming Project PP 8.3 on pg 239 of Lewis and Chase, comparing sorting algorithms.
import javax.swing.JOptionPane;
public class SortingTest {
static int numberComparisons1, numberComparisons2, numberComparisons3, numberComparisons4, numberComparisons5;
public static void main(String[] args) {
String input;
int listSize;
int randInt;
long timeStart, timeEnd;
double elapsedSeconds;
input = JOptionPane.showInputDialog( "Enter number of random ints to generate" );
listSize = Integer.parseInt(input);
Integer [] intArray1 = new Integer[listSize];
Integer [] intArray2 = new Integer[listSize];
Integer [] intArray3 = new Integer[listSize];
Integer [] intArray4 = new Integer[listSize];
Integer [] intArray5 = new Integer[listSize];
for (int i=0; i<=listSize-1; i++) {
randInt = (int)(Math.random()*listSize); // random int between 0 and range-1
intArray1[i] = new Integer(randInt);
intArray2[i] = new Integer(randInt);
intArray3[i] = new Integer(randInt);
intArray4[i] = new Integer(randInt);
intArray5[i] = new Integer(randInt);
}
//*** here is the selection sorting
timeStart = System.currentTimeMillis(); // time now
selectionSort(intArray1);
timeEnd = System.currentTimeMillis(); // time now
// difference between the start and end times is the elapsed time in ms
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("*** Selection sort ***");
System.out.println("Elapsed time of selection sort: " + elapsedSeconds + "s");
System.out.println("Number of comparisons: " + numberComparisons1);
System.out.println("Time per comparison: " + (elapsedSeconds/numberComparisons1) + "s");
showIntArray(intArray1);
System.out.println();
//*** here is the insertion sorting
timeStart = System.currentTimeMillis();
insertionSort(intArray2);
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("*** Insertion sort ***");
System.out.println("Elapsed time of insertion sort: " + elapsedSeconds + "s");
System.out.println("Number of comparisons: " + numberComparisons2);
System.out.println("Time per comparison: " + (elapsedSeconds/numberComparisons2) + "s");
showIntArray(intArray2);
System.out.println();
//*** here is the bubble sorting
timeStart = System.currentTimeMillis();
bubbleSort(intArray3);
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("*** Bubble sort ***");
System.out.println("Elapsed time of bubble sort: " + elapsedSeconds + "s");
System.out.println("Number of comparisons: " + numberComparisons3);
System.out.println("Time per comparison: " + (elapsedSeconds/numberComparisons3) + "s");
showIntArray(intArray3);
System.out.println();
//*** here is the quick sorting
timeStart = System.currentTimeMillis();
quickSort(intArray4, 0, listSize-1);
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("*** Quick sort ***");
System.out.println("Elapsed time of quick sort: " + elapsedSeconds + "s");
System.out.println("Number of comparisons: " + numberComparisons4);
System.out.println("Time per comparison: " + (elapsedSeconds/numberComparisons4) + "s");
showIntArray(intArray4);
System.out.println();
//*** here is the merge sorting
timeStart = System.currentTimeMillis();
mergeSort(intArray5, 0, listSize-1);
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("*** Merge sort ***");
System.out.println("Elapsed time of merge sort: " + elapsedSeconds + "s");
System.out.println("Number of comparisons: " + numberComparisons5);
System.out.println("Time per comparison: " + (elapsedSeconds/numberComparisons5) + "s");
showIntArray(intArray5);
}
/**
* Sorts the specified array of integers using the selection
* sort algorithm.
*
* @param data the array to be sorted
*/
public static <T extends Comparable<? super T>> void selectionSort (T[] data)
{
int min;
T temp;
for (int index = 0; index < data.length-1; index++)
{
min = index;
for (int scan = index+1; scan < data.length; scan++) {
numberComparisons1++;
if (data[scan].compareTo(data[min])<0) {
min = scan;
}
}
/** Swap the values */
temp = data[min];
data[min] = data[index];
data[index] = temp;
}
}
/**
* Sorts the specified array of objects using an insertion
* sort algorithm.
*
* @param data the array to be sorted
*/
public static <T extends Comparable<? super T>> void insertionSort (T[] data)
{
for (int index = 1; index < data.length; index++)
{
T key = data[index];
int position = index;
/** Shift larger values to the right */
while (position > 0 && data[position-1].compareTo(key) > 0)
{
numberComparisons2++;
data[position] = data[position-1];
position--;
}
data[position] = key;
}
}
/**
* Sorts the specified array of objects using a bubble sort
* algorithm.
*
* @param data the array to be sorted
*/
public static <T extends Comparable<? super T>> void bubbleSort (T[] data)
{
int position, scan;
T temp;
for (position = data.length - 1; position >= 0; position--)
{
for (scan = 0; scan <= position - 1; scan++)
{
numberComparisons3++;
if (data[scan].compareTo(data[scan+1]) > 0)
{
/** Swap the values */
temp = data[scan];
data[scan] = data[scan + 1];
data[scan + 1] = temp;
}
}
}
}
public static <T extends Comparable<? super T>> void quickSort (T[] data, int min, int max)
{
int indexofpartition;
if (max - min > 0)
{
/** Create partitions */
indexofpartition = findPartition(data, min, max);
/** Sort the left side */
quickSort(data, min, indexofpartition - 1);
/** Sort the right side */
quickSort(data, indexofpartition + 1, max);
}
}
/**
* Used by the quick sort algorithm to find the partition.
*
* @param data the array to be sorted
* @param min the integer representation of the minimum value
* @param max the integer representation of the maximum value
*/
private static <T extends Comparable<? super T>> int findPartition (T[] data, int min, int max)
{
int left, right;
T temp, partitionelement;
int middle = (min + max)/2;
partitionelement = data[middle]; // use middle element as partition
left = min;
right = max;
while (left<right)
{
/** search for an element that is > the partitionelement */
while (data[left].compareTo(partitionelement) <=0 &&
left < right) {
numberComparisons4++;
left++;
}
/** search for an element that is < the partitionelement */
while (data[right].compareTo(partitionelement) > 0) {
numberComparisons4++;
right--;
}
/** swap the elements */
if (left<right)
{
temp = data[left];
data[left] = data[right];
data[right] = temp;
}
}
/** move partition element to partition index*/
temp = data[min];
data[min] = data[right];
data[right] = temp;
return right;
}
/**
* Sorts the specified array of objects using the merge sort
* algorithm.
*
* @param data the array to be sorted
* @param min the integer representation of the minimum value
* @param max the integer representation of the maximum value
*/
public static <T extends Comparable<? super T>> void mergeSort (T[] data, int min, int max)
{
T[] temp;
int index1, left, right;
/** return on list of length one */
if (min==max)
return;
/** find the length and the midpoint of the list */
int size = max - min + 1;
int pivot = (min + max) / 2;
temp = (T[])(new Comparable[size]);
mergeSort(data, min, pivot); // sort left half of list
mergeSort(data, pivot + 1, max); // sort right half of list
/** copy sorted data into workspace */
for (index1 = 0; index1 < size; index1++)
temp[index1] = data[min + index1];
/** merge the two sorted lists */
left = 0;
right = pivot - min + 1;
for (index1 = 0; index1 < size; index1++)
{
if (right <= max - min) {
if (left <= pivot - min) {
numberComparisons5++;
if (temp[left].compareTo(temp[right]) > 0) {
data[index1 + min] = temp[right++];
} else {
data[index1 + min] = temp[left++];
}
} else {
data[index1 + min] = temp[right++];
}
} else {
data[index1 + min] = temp[left++];
}
}
}
// show values of an int array
public static void showIntArray(Integer[] array) {
for (int i=0; i<array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
Given a specific node in binary search tree, how can you find the immediate larger element in the tree?
To find the immediate larger node in binary search tree, you should look at the right child of the given node. This is because a property of BST, that a node should be smaller than the right child of it and larger than the left child of it.
Details of various operations in AVL trees and Red/Black trees can make your head spin :-( What is so special about these trees that makes them better than plan binary search trees? Try to give a simple explain in your own words.
In an AVL tree, height difference between the right children and the left children is up to 1.
In a Red/Black tree, all the nodes are red or black. The root node is black. All the children of red nodes are black and all the parents of red nodes are black conversely. It should have the same numbers of black nodes from the root to any nodes which don't have a child.
Both of the trees are self-balancing binary search trees, which make more efficient to search than standard binary search trees.
Do Programming Project PP 10.8 on pg 330 of Lewis and Chase, implementing the AVL algorithm on a binary search tree.
// File : BinarySearchTreeAVL.java
// Author: Nicholas Duchon
// Date : July 31, 2008
// updates:
// Nov 16, 2008
// Nov 22, 2008
// Apr 17, 2009 - fixed toTreeString
// Apr 17, 2009 - added parents to nodes and \ and / to tree display.
// Mar 18, 2012 - cleaned up some generic lint stuff in BSTNodeND declarations
// May 13, 2012 - toTreeString - removed use of parent reference, added label parameter
//
// Simplified, linked version of a binary search tree
// uses generic class implementing Comparable
// no exceptions thrown
// static fields
// all associated with toString displays
// .. DEPTHDELTA - used to present a tree-like display using spacing
// This code implements the following public methods
// T is a Comparable class
// insert (T) : void
// find (T) : T
// max () : T
// getSize () : int
// remove (T) : void
// toString () : String // to tree string
//
// private mutator/accessor methods
// insertValue (T, BSTNodeND < T >): void - uses comparator from T
// findValue (T, BSTNodeND < T >): T - finds an T, returns null if not found
// findMax (): T - returns max value in this subtree
// getSize (BSTNodeND < T >): int
// removeRoot (BSTNodeND < T >): BSTNodeND < T >
// remove (T, BSTNodeND < T >): BSTNodeND < T >
//
// private toString methods
// toString (BSTNodeND) : uses toTreeString (int) to create a tree-like display
// toInOrderString (BSTNodeND) : recursive in-order string
// toPreOrderString (BSTNodeND) : recursive pre-order string
// toPostOrderString (BSTNodeND) : recursive post-order string
// toLevelOrderString (BSTNodeND) : level-order string, uses a queue (ArrayDeque)
// toTreeString (int, BSTNodeND, char) : recursive in-order traversal with depth offsets and parent indicators
//
// Inside the BSTNodeND class:
// Instance fields:
// data < L > generic parameter of the BSTNodeND class, NOT the BinarySearchTreeAVL class
// BSTNodeND left, right, parent - links to create the tree
// constructors
// < L > generic parameterized constructor, left and right are null
// < L >, NSTNodeND - links to parent also, for tree display
//
// import java.util.ArrayDeque;
import java.util.Scanner;
public class BinarySearchTreeAVL
< K extends Comparable < ? super K > >
// ANY class that extends the base comparable type (K)
// of this data structure instance may be inserted
{
static final int DEPTHDELTA = 5; // used to create a text tree display
BSTNodeND < K > root = null;
int balance = 0;
public void insert (K d) {
insertNode (new BSTNodeND < K > (d));
} // end insert, public version
public void insertNode (BSTNodeND < K > n) {
if (root == null) root = n;
else insertNode (n, root);
} // end insert Node
public K find (K d) {
if (root == null)
return null;
BSTNodeND < K > t = findValue (d, root);
return (t==null)?null:t.data;
} // end find method
public K max () {
if (root == null)
return null;
return findMax(root).data;
} // end max method
public int getSize () {
return getSize (root);}
public void remove (K d) {
root = remove (d, root);
} // end remove data
public String toString () {
if (root == null)
return null;
return toString(root);}
private void insertNode (BSTNodeND < K > d, BSTNodeND < K > n) {
d.parent = n;
if (d.data.compareTo (n.data) > 0) {
if (n.right == null) {
if (checkBalance(d, n) == 1) {
balance++;
} else if (checkBalance(d, n) == -1) {
balance--;
}
rotation(d, n);
n.right = d;
}
else {
insertNode (d, n.right);
}
}
else {
if (n.left == null) {
if (checkBalance(d, n) == 1) {
balance++;
} else if (checkBalance(d, n) == -1) {
balance--;
}
rotation(d, n);
n.left = d;
}
else {
insertNode (d, n.left);
}
}
} // end method insertNode
private int checkBalance (BSTNodeND < K > d, BSTNodeND < K > n) {
if (n == root) {
if (d.data.compareTo (root.data) > 0) {
return 1; // if there is a bias toward right
} else if (d.data.compareTo (root.data) < 0) {
return -1; // if there is a bias toward left
}
} else {
if (d.data.compareTo (root.data) > 0 && n.right == null && n.left == null) {
return 1;
} else if (d.data.compareTo (root.data) < 0 && n.right == null && n.left == null) {
return -1;
}
}
return 0;
} // end checkBalance
private void rotation (BSTNodeND < K > d, BSTNodeND < K > n) {
if (balance < -1) {
if ((Integer) d.data < (Integer) d.parent.parent.data) {
singleRightRotation(d, n);
} else {
doubleLeftRightRotation(d, n);
}
} else if (balance > 1) {
if ((Integer) d.data > (Integer) d.parent.parent.data) {
singleLeftRotation(d, n);
} else {
doubleRightLeftRotation(d, n);
}
}
} // end rotation
private void singleRightRotation (BSTNodeND < K > d, BSTNodeND < K > n) {
if (n.parent.parent == root) {
K temp1 = n.parent.right.data;
K temp2 = n.parent.parent.data;
K temp3 = n.parent.parent.right.data;
remove (n.parent.right.data);
removeRoot (n.parent.parent);
insert (temp2);
root.right.data = temp2;
remove (root.right.left.data);
insert (temp1);
insert (temp3);
} else {
K temp1 = n.parent.right.data;
K temp2 = n.parent.parent.data;
K temp3 = n.parent.parent.right.data;
remove (n.parent.right.data);
remove (n.parent.parent.data);
insert (temp2);
n.parent.right.data = temp2;
remove (n.parent.right.left.data);
insert (temp1);
insert (temp3);
}
balance = 0;
} // end singleRightRotation
private void singleLeftRotation (BSTNodeND < K > d, BSTNodeND < K > n) {
if (n.parent.parent == root) {
K temp1 = n.parent.left.data;
K temp2 = n.parent.parent.data;
K temp4 = n.parent.parent.left.data;
K temp3 = n.parent.data;
remove (n.parent.left.data); // temp1
remove (n.parent.data); // temp3
root.data = temp3;
remove (root.left.data); // temp4
insert (temp2);
insert (temp1);
insert (temp4);
} else {
K temp1 = n.parent.left.data;
K temp2 = n.parent.parent.left.data;
K temp3 = n.parent.parent.data;
remove (n.parent.left.data);
remove (n.parent.parent.left.data);
remove (n.parent.parent.data);
insert (temp3);
insert (temp2);
insert (temp1);
}
balance = 0;
} // end singleLeftRotation
private void doubleLeftRightRotation(BSTNodeND < K > d, BSTNodeND < K > n) {
System.out.println("doubleLeftRightRotation() is to be implemented");
} // end doubleLeftRightRotation()
private void doubleRightLeftRotation(BSTNodeND < K > d, BSTNodeND < K > n) {
System.out.println("doubleRightLeftRotation() is to be implemented");
} // end doubleRightLeftRotation()
private BSTNodeND < K > findValue (K d, BSTNodeND < K > n) {
if (n.data.compareTo(d) == 0)
return n;
if (n.data.compareTo (d) > 0)
return (n.left==null)?null:findValue (d, n.left);
return (n.right == null)?null:findValue(d, n.right);
} // end findValue
private BSTNodeND < K > findMax (BSTNodeND < K > n) {
if (n.right == null)
return n;
return findMax(n.right);
} // end findValue
private int getSize (BSTNodeND < K > t) {
if (t == null)
return 0;
return getSize (t.left) + getSize (t.right) + 1;
} // end getSize node
private BSTNodeND < K > removeRoot (BSTNodeND < K > t) {
if (t.left == null) {
if (t.right != null) {
t.right.parent = t.parent;
}
return t.right;
}
if (t.right == null) {
t.left.parent = t.parent; // t.left != null because of earlier if test case
return t.left;
}
BSTNodeND < K > newTop = findMax(t.left);
remove (newTop.data, t); // lose the node instance, leave tree intact
t.data = newTop.data; // just replace the data at the internal node
return t;
} // end remove data, tree
private BSTNodeND < K > remove (K d, BSTNodeND < K > t) {
if (t == null)
return null;
if (d.compareTo (t.data) < 0) {
t.left = remove (d, t.left );
}
else {
if (d.compareTo (t.data)> 0) {
t.right = remove (d, t.right);
}
else { // d equals t.data
t = removeRoot (t);
}
}
return t;
} // end remove data, tree
private String toString (BSTNodeND < K > n) {
return toTreeString (5, n, '>');
} // end toString
// removed use of parent reference, added label parameter, 5/13/2012
private String toTreeString (int depth, BSTNodeND < K > n, char label) { // depth = 0 is bad
return
((n.left == null)?"":toTreeString (depth + DEPTHDELTA, n.left, '/'))
+ String.format ("%" + depth + "s%s\n", label, n) // ND: fixed 4/17/2009
+ ((n.right == null)?"":toTreeString (depth + DEPTHDELTA, n.right, '\\'));
} // end method toTreeString
private String toInOrderString (BSTNodeND < K > n) {
return
((n.left == null)?"":toInOrderString(n.left ))
+ n + " "
+ ((n.right == null)?"":toInOrderString(n.right));
} // end toInOrderString
private String toPreOrderString (BSTNodeND < K > n) {
return
n + " "
+ ((n.left == null)?"":toPreOrderString(n.left ))
+ ((n.right == null)?"":toPreOrderString(n.right));
} // end toPreOrderString
private String toPostOrderString (BSTNodeND < K > n) {
return
((n.left == null)?"":toPostOrderString(n.left ))
+ ((n.right == null)?"":toPostOrderString(n.right))
+ n + " ";
} // end to PostOrderString
// See: http://en.wikipedia.org/wiki/Tree_traversal
private String toLevelOrderString (BSTNodeND < K > n) {
String st = "";
BSTNodeND < K > node;
java.util.ArrayDeque < BSTNodeND < K > > q
= new java.util.ArrayDeque < BSTNodeND < K > > ();
q.add (n); // start queue by adding this (root?) to queue
while (q.size() > 0) {
node = q.remove(); // remove the head of queue
st += (node.data + " "); // process head data to String
if (node.left != null) q.add (node.left); // insert left child at end of queue
if (node.right != null) q.add (node.right); // insert right child at end or queue
} // end queue processing
return st.toString();
} // end to LevelOrderString
// main and example methods follow
public static void main (String args []) {
integerExample ();
// stringExample ();
Scanner st = new Scanner (System.in);
while (menu(st));
System.out.println ("...Bye");
} // end main
static boolean menu (Scanner st) {
System.out.println ("enter integer values, q to quit:");
String line = st.nextLine();
if (line.length() == 0)
return true; // just <cr> causes crash on next line
Scanner tokens = new Scanner (line).useDelimiter ("[,\\s]+"); // allow comma+space separators
if (! tokens.hasNextInt())
if (tokens.hasNext() && tokens.next().equalsIgnoreCase ("q"))
return false;
else
return true;
BinarySearchTreeAVL <Integer> tree = new BinarySearchTreeAVL <Integer> ();
while (tokens.hasNextInt()) tree.insert (tokens.nextInt());
System.out.println ("Tree:\n" + tree);
System.out.println ("Tree in-order:\n" + tree.toInOrderString (tree.root));
System.out.println ("Tree pre-order:\n" + tree.toPreOrderString (tree.root));
System.out.println ("Tree post-order:\n" + tree.toPostOrderString (tree.root));
System.out.println ("Tree level-order:\n" + tree.toLevelOrderString(tree.root));
if (tokens.hasNext() && tokens.next().equalsIgnoreCase ("q"))
return false;
return true;
} // end menu
public static void integerExample () {
BinarySearchTreeAVL < Integer > x = new BinarySearchTreeAVL < Integer > ();
// In case of singleRightRotation
int arr1[] = {7, 5, 9, 3, 6, 1};
// int arr2[] = {9, 10, 7, 8, 6, 5};
// int arr3[] = {18, 20, 12, 22, 19, 14, 8, 9, 4, 2};
// int arr4[] = {25, 27, 21, 30, 26, 22, 18, 20, 16, 12, 8};
// In case of singleLeftRotation
// int arr5[] = {7, 9, 6, 12, 8, 14};
// int arr6[] = {11, 14, 8, 19, 12, 20};
// int arr7[] = {26, 28, 23, 32, 27, 24, 19, 36, 30, 39};
// In case of doubleLeftRightRotation
// int arr8[] = {9, 11, 4, 6, 3, 8, 5};
// In case of doubleRightLeftRotation
// int arr9[] = {12, 17, 9, 20, 15, 16, 13};
int rem [] = {3, 5, 7};
for (int y: arr1) {
System.out.println ("Inserting: " + y);
x.insert (y);
}
System.out.println ("X:\n" + x);
System.out.println ("X in-order:\n" + x.toInOrderString(x.root));
System.out.println ("X pre-order:\n" + x.toPreOrderString(x.root));
System.out.println ("X post-order:\n" + x.toPostOrderString(x.root));
System.out.println ("X level-order:\n" + x.toLevelOrderString(x.root));
Integer t = x.find(3);
System.out.println ("find: " + t);
System.out.println ("find: " + x.find(13));
System.out.println ("Size: " + x.getSize());
System.out.println ("MAX: " + x.max());
for (int y: rem) {
System.out.println ("Removing: " + y);
x.remove (y);
System.out.println ("result:\n" + x);
}
// System.out.println ("X:\n" + x);
} // end integerExample
public static void stringExample () {
// The following is an example using a user-defined class, see below
// notice the use of the generic parameter Example
String [] sa = {"one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"};
BinarySearchTreeAVL < Example > ex = new BinarySearchTreeAVL < Example > ();
for (String s: sa) ex.insert (new Example (s));
System.out.println ("Example using strings: \n" + ex);
} // end stringExample
// needs to be internal class so, eg, AVLNode in AVLND can extend this internal node class
class BSTNodeND < L extends Comparable< ? super L > > {
L data;
BSTNodeND < L > left, right, parent;
BSTNodeND (L d) {data = d;}
BSTNodeND (L d, BSTNodeND <L> p) {data = d; parent = p;}
public String toString () {
return data.toString();} // end toString method
} // end class BSTNodeND
} // end class BinarySearchTreeAVL
// A class that can be used with the BinarySearchTreeAVL data structure
// Notice the use of the generic parameter Example
class Example implements Comparable < Example > {
String data;
public Example (String d) {
data = d;}
// you, of course, will want a more interesting compareTo method
public int compareTo (Example e) {
return data.compareTo (e.data);
} // end compareTo method
public String toString () {
return data;
} // end toString
} // end class Example
