Queues, Heaps and Priority Queues Cont'd

     So like you said, my blogs are too much like question and answer, so I'm going to switch it up a bit and actually blog to you for the first time. Basically, in the first part of this weeks homework I learned some stuff about the add() and remove() methods of the DynamicHeap, where basically add adds new strings while maintaining the principles of a heal (complete trees). After adding the string in the right place to maintain a complete tree, it reorganizes the tree to maintain the maxHeap be comparing and swapping nodes. Remove() does a similar thing but inverted in a way. It deletes the maximum value and reorganizes the tree after that, the code however was a bit confusing, but it essentially sets the root to the maxValue then deletes it.

      I'm quite confused about coding a method to find the height of a heap because I was researching on it for quite a bit and found that the height of a complete tree (which would be the height of a heap) is log(base 2) of n, which I have no idea how to code. I then looked up logarithm methods but it got way more confusing from there.

      I also really like HeapSort, it's extremely logical. You traverse your list, or array, or whatever, and add all those values into a heap. Then you just start removing values from the heap and adding them to the end of the array, this is sorting it because whenever you remove a value from a heap it's the max value. Boom, sorted array. But it's really inefficient, you traverse it twice meaning it takes O(2n) time.

Kinect

So I was just messing about on youtube with some friends this weekend and we came across this video and the first thing that jumped out to me was this kinect idea. There is this music artist called Skrillex who used something which I believe to be kinect or very similar to kinect in his live show. It was awesome I thought, and would also be awesome for us to do something similar. Basically, he had a huge screen behind him with this huge monster like creature copying his exact moves as he DJed the concert.

Here is a clear version of what it was (ignore the curses please, I just chose this video out because it clearly shows how it copies him):
http://www.youtube.com/watch?v=vFpKu5os4Po&feature=related

I don't know maybe we could do something like this, and instead of having the captains actually do their thing in the opening ceremony, they have a copy of them or their characters. I don't really know, I just found this quite awesome, and it obviously relates.

Queues, Heaps and Priority Queues

7.1 It returned true, makes sense because it's constructor doesn't fill it up with anything, and I haven't either. Then after I enqueue "one" "two" and "three" and dequeue once I get two when I peekFront(). This is all good because I dequeued one. isEmpty() returns false as it should.

Not clear on what FIFO is. Google search resulted in first in, first out? as in when I called enqueue on "one" first, and then when I dequeued it, it was the first out, since it was the first in? I guess that makes sense.

7.2 It makes it efficient because of what I just wrote up there. The FIFO nature of both LinkedLists and Queues make them a perfect match. I'm unsure of how to calculate BigO time, but I'm pretty sure it's something along the lines of log1 or something so close to zero, because it's not even BigO(n) as it doesn't loop or anything, all the methods are one liners which just return results which are already one step away from being found.

7.3 LinkedList probably has two different add methods, one for the beginning and one for the end. add() most likely adds an object to the beginning of the LinkedList whereas addLast() does the opposite.

7.4 It wasn't harder at all. Quite the same level of simplicity I would say. Still one liner and quick methods. Here's my implementation:

public class ArrayListQueue implements Queue
{

private ArrayList list;

public ArrayListQueue()
{
    list = new ArrayList();
}//constructor

public void enqueue(Object x)
{
    list.add(x);
}//enqueue

public Object dequeue()
{
    return list.remove(0);
}//dequeue

public Object peekFront()
{
    return list.get(0);
}//peekFront

public boolean isEmpty()
{
    return list.size() == 0;
}//isEmpty

}//class ListQueue

7.5 Like I said in 7.4 It's about the same. Efficiency and ease of coding was the same.

7.5 a Nothing much, it just seems to reinforce the idea of first in first out, and how that's a great advantage in many of the business related sectors of our life, where you queue an appointment first, and you therefore become the first to be appointed. The elevator in this simulation reinforces it, but in reality it's not whoever calls the elevator first that gets in, but whoever calls it first on it's way down or up. If you call an elevator from floor 24 before I call it from floor 4, when it's going up from floor 1, I will be the first to enter because it will stop on its way to pick me up. So it's similar, but not distinct.

Trees #2 6-10 & 11-12 & End

STUDENT TASKS

6_6. Complete the implementation of method recursiveFind().

private TreeNode recursiveFind(TreeNode tree, Object target)
{
if (tree == null)
    return null;
else if(((Comparable)target).compareTo(root.getValue())==0)
    return tree;
else if (((Comparable)tree.getValue()).compareTo(target)>0)
    return recursiveFind(tree.getLeft(), target);
else
    return recursiveFind(tree.getRight(), target);
}//recursiveFind

6_7. Test your implementation of recursiveFind() by creating a BST Object on the BlueJ workbench, building a small tree with String values, then calling testRecursiveFind().

Works great, just takes a long time to make the tree... might be smart to make some method to make the whole process more simple for the future if I plan to work with trees a little more.

6_8. Try sketching a run-time stack to follow the the call to testRecursiveFind(). You can observe the recursive calls by using the BlueJ to set a breakpoint in the code for recursiveFind().

Done, not sure about the breakpoint part though, haven't touched any of that stuff since the very first lesson of last year.

6_9. What are the relative advantages and disadvantages of the iterative and recursive algorithms?

Recursive algorithms tend to reduce code length, while iterative solutions are more simple to code in my opinion. It seems to me also that recursive solutions may stack overflow easier than iterative solutions. I generally prefer iterative solutions because they come to me more naturally, and up until now I've never encountered a situation where I had to reduce my code length using recursion. I also feel that recursive solutions aren't exactly logical. If I were to make an analogy, I feel like iterative solutions solve a puzzle, whereas recursive solutions build a whole new puzzle and use that puzzle to solve the puzzle we have in the first place. It requires almost a creative approach to coding.

6_10. What modifications would need to be made to class BST in order to call recursiveFind(), without recourse to a special calling method like testRecursiveFind()?
I'm confused of the question. From what I understand the answer is none, recursiveFind() works fine on its own, and testRecursiveFind() simply tests the algorithm with different parameters. If that's the question, then one simply has to change the parameters on recursiveFind() to that of the fields in the BST as testRecursiveFind() does.


6_11. The postOrder traversal produced a sequence which was the reverse order from the order of entry. Will this always be the case? Try some experiments to test the idea.

 Yes it'll always be the case.

6_12. The inOrder traversal suggests a new method of sorting. Let's call this method the binarySearchTreeSort. The efficiency of this sort is O(nlogn) which puts it in the family of more efficient sorts along with Merge Sort, and Quick Sort.
Create a new class named binarySearchTreeSortDemo. Use the class to demonstrate the binarySearchTree sort on an array of 20 random integers with values in the range 1..100.
create the array
print the array
create a binary search tree from the array (ints need to be wrapped into Integer)
do an inOrder traversal of the BST to return values to the array in ascending order
print the sorted array



public class binarySearchTreeSortDemo
{

private int[] list;


public binarySearchTreeSortDemo()
{
list = new int[20];
for (int i=0; i<20; i++)
{
list[i] = ((int)Math.random()*100);
}
}

public void sort()
{
   BST tree = new BST();
   for(int i=0; i<20; i++) {
   tree.add(list[i]); }
   tree.testTreeTraversal();
}
}

6.13 & 6.14 I'm really unsure of how to make the recursive method for this. And nobody seems to have any pointers on it in their blogs so I'm extremely lost. I'm just going to try and go on and work without this problem.

6.15 I've tested this before in one of the quizzes. It's pretty obvious too that Inorder and infix and postOrder and postfix are the same, quite logical.

6.16 I see and understand how the call in between and the nature of run-time stacks causes the desired effect. I can easily solve recursive problems and such, it's just the creation of recursive methods which drives me insane. I've been working on the recursive javabat by the way like you said.

6.17 Working on it. But I wish to also get some queues and heaps done, so i'll get back to it this week.

6. Tree Nodes 1-5

6_1. Construct a BST on paper using the following values (5, 9, 3, 7 ,8,1,6, 2, 4). How many leaves are there? How many nodes have two children? How many nodes have only one child? How many iterations are required to ascertain that 12 is not in the BST? 
Construct the tree using the simulation provided at..
http://www.cs.jhu.edu/~goodrich/dsa/trees/btree.html 
Does this simulation confirm your paper tree diagram?


6.1 In my BST I have four leaves, three nodes with two children, and two nodes with only one child. Just one iteration is needed to find that 12 is not in the BST. You go from 5 to 9 which has no right node, so you know nothing is greater than 9.


6_2. Draw a BST for the following sequence of Strings {carter, reagan, bush, clinton, bush. }Create a new BST instance on the BlueJ workbench, then use the add() method to add the sequence of Strings. Inspect the BST object on the workbench to verify that the tree has the shape that you drew. 


6.2 Worked, and verified that it's the same shape.


6_3. Modify add() so that duplicates are not inserted into the tree (only one bush allowed). Test your code with the sequence of Strings. Does the new BST contain only 4 Objects?


6.3.              if (((Comparable)newNode.getValue()).compareTo(T.getValue())==0)
            {
                System.out.println("Please only insert a value once. No copies will be tolerated.");
            }

I added that method to the while loop in add(). Daly your getting easier with your homework, I like this.

6_4. Clear the BlueJ workbench of all objects and create 5 new TreeNode Objects using the series of Strings {Carter, reagan, bush, clinton, bush. }.For the first Object, the Name of Instance should be Carter, and the Object initValue should be "Carter", the two TreeNode references should be null. Continue in the same way for the next 4 Objects and Strings
Now create a new BST instance on the workbench and add the TreeNode Objects from the workbench in the order {Carter, reagan, bush, clinton, bush. }.
You should find that the program crashes with a ClassCastException error, when an attempt is made to add the second Object (reagan).
Explain precisely why this error occurs.
What could be done to avoid this error?


6.4. I believe it's because we don't have the node T casted with the (Comparable) phrase. That would be the only thing that I believe would explain the first node (which is casted with (Comparable)) being taken by the system, and not T. To fix it we should cast the second to (Comparable).

6_5. Implement the find() method using the following header.

//returns the reference to target in the BST, if found, otherwise returns null
public Object find(Object target)

The structure of find() is quite similar to that of method add(). You should look carefully at add(), and perhaps even copy the code for add to the body of find() and edit.

6.5. 

//returns the reference to target in the BST, if found, otherwise returns null
public Object find(Object target)
{
    TreeNode newNode = new TreeNode(target.toString(),null,null);
    if(root==null)//bst is empty, make root reference node referenced by newNode
    {
        return null;
    }//if


    else//search for place to insert node referenced by newNode
    {
        TreeNode T=root;//T is a traversing TreeNode reference (pointer)
        TreeNode follow=null;//follows one node behind T


        while(T!=null)
        {
            if (((Comparable)newNode.getValue()).compareTo(T.getValue())==0)
            {
                return T;
            }
            follow=T;
            if (((Comparable)newNode.getValue()).compareTo(T.getValue())>0)
            {//the value in node referenced by newNode >= 
              //value in node referenced by T (go right)
                T=T.getRight();
            }//if
            else
            {//go left
                T=T.getLeft();
            }//else
        }//while


       return null;
    }//else
}

4.14 - END

4_14. Compile class ArithmeticExpression. Create an instance using the exception example given in the table above "(a+B)". Run method isValid(). The method should return false.

4.14. Worked, done.

4_15. Edit method isValid(), to take care of the other 9 rules given in the table above. For each implementation check the method by using the exception example given in the table above.

4.15. I added some methods to help with the changes. This was quite a complicated task, but I believe I came up with good solutions to it.


public boolean isValid()
{
    int numoperands = 0;
    int numoperators = 0;
    int numopen = 0;
    HashSet Caseoperandset = new HashSet();
    boolean tempIsValid=true;
    if(!expression.substring(0,1).equals("(") || !expression.substring(0,1).equals(")"))
       tempIsValid = false;
    for (int i =0; i<expression.length();i++)
    {
        Character tempCharacter=new Character(expression.charAt(i));
        boolean canTemp2 = i+1<expression.length();
        if(canTemp2) { Character temp2 = new Character(expression.charAt(i+1));
        if(!operatorSet.contains(tempCharacter) && !operandSet.contains(tempCharacter) && !bracketSet.contains(tempCharacter))
                tempIsValid= false;
        if(checkIfClosedParentheses(tempCharacter)) {
            if(operandSet.contains(temp2) && canTemp2)
                tempIsValid = false;
        }
        if(operatorSet.contains(tempCharacter)) {
           numoperators++;
           if(checkIfClosedParentheses(temp2) && canTemp2)
                tempIsValid = false; }
        if(operandSet.contains(tempCharacter)) {
           numoperands++;
           Caseoperandset.add(tempCharacter); }
           if(checkIfOpenParentheses(temp2) && canTemp2)
               {tempIsValid = false;}
        if(checkIfOpenParentheses(tempCharacter))
           numopen++; }
        else
        {
        if(!operatorSet.contains(tempCharacter) && !operandSet.contains(tempCharacter) && !bracketSet.contains(tempCharacter))
                tempIsValid= false;
        if(operatorSet.contains(tempCharacter))
           numoperators++;
        if(operandSet.contains(tempCharacter)) {
           numoperands++;
           Caseoperandset.add(tempCharacter); }
        if(checkIfOpenParentheses(tempCharacter))
           numopen++;
        }
    }
    if(checkParentheses(expression) || numoperands != numoperators+1 || numopen != numoperators || !checkIfConsecutiveOperands(Caseoperandset) || checkIfOperandsDouble(Caseoperandset))
       tempIsValid = false;
    return tempIsValid;
}

public boolean checkIfConsecutiveOperands(HashSet characters)
{
    boolean Consecutive = true;
    for(char c='a';c<=characters.size();c++)
    {
        if(!operandSet.contains(c))
           Consecutive = false;
    }//for
    return Consecutive;
}

public boolean checkIfOperandsDouble(HashSet characters)
{
    for(char c='a'; c<characters.size(); c++) {
       for(char z='a'; c<characters.size(); z++)
       {
           if(c == z)
              return true;
        }
    }
    return false;
}
public static boolean checkIfOpenParentheses(Character c)
{
     if(c.toString().equals("("))
        return true;
     else return false;
}

public static boolean checkIfClosedParentheses(Character c)
{
     if(c.toString().equals(")"))
        return true;
     else return false;
}

public static boolean checkParentheses(String s) { //Mark Byers method to find whether parenthesis are equal by checking the nesting level.
    int nesting = 0;
    for (int i = 0; i < s.length(); ++i)
    {
        char c = s.charAt(i);
        switch (c) {
            case '(':
                nesting++;
                break;
            case ')':
                nesting--;
                if (nesting < 0) {
                    return false;
                }
                break;
        }
    }
    return nesting == 0;
}


4_16. What changes have to be made to modify class ArithmeticExpression to use double values rather than int values.

4.16. You would have to change all your int values into doubles (but not in your loops, i believe). This seems unnecessary for now; however, because everything seems to be working fine with ints.

4_17. When the user attempts to divide by zero, an "ArithmeticException (divide by zero)" error is thrown. The ArithmeticException class is part of the APCS Java Subset.
http://www.cs.duke.edu/csed/AP/subset/doc/index.html
Place a check in method evaluate() that catches this runtime error.

4.17.        case '+': result=operand1+operand2; break;
                case '*': result=operand1*operand2; break;
                case '/': {if(operand1 == 0) {System.out.println("Cannot divide by zero."); return 0;}      result=operand2/operand1; break;}
                case '-': result=operand2-operand1; break;

     Simply checked if it's zero. If it was a gave an error and set the case to 0.

4_18. Edit class ArithmeticExpression to include a method that converts the infix expression represented by the String expression to a postfix expression..
Public String infixToPostfix()
The algorithm for this method requires two stacks, one to build the postfix expression, and an auxiliary stack for temporarily holding operators.
Moving through the expression from the left.
Ignore open parentheses
Push operands on the "build" stack.
Push operators on the auxiliary stack.
On closed parentheses, pop the operator from the auxiliary stack and push it onto the "build" stack.
After processing all the characters in the expression String the "build" stack will contain the characters making up the postfix string in order from bottom to top of the stack.
Construct the postfix String (you can use the empty auxiliary to help) and return the postfix String.

4.18. Took a while... with a bit of help from Gershon's blog to find some of my compiling errors i finally got it:


public String infixToPostfix()
 {
  ArrayListStack operatorStack = new ArrayListStack();
  String postfix = "";
  for(int i=0;i<expression.length();i++)
  {
      char c = expression.charAt(i);
      if(operandSet.contains(c))
          postfix=postfix+Character.toString(c);
      if(operatorSet.contains(c))
          operatorStack.push(c);
      if(Character.toString(c).equals(")"))
          postfix = postfix + Character.toString((Character)operatorStack.pop()); //thanks to Gershon I found the casting issue that was bothering me for ages...
  }
  return postfix;
 }

4.10-4.13

STUDENT TASKS

4_10. The minimum number of moves for a one disk game is one, and for a two disk game three. Try to find a formula, in terms of the number of disks (n), which correctly expresses the minimum number of moves required to complete the game for any given (n).

4.10

f(n) = 2^n-1 where n is the number of disks being played with.

4_11. Modify method play() so that the player is unable to place a larger disk on a smaller dsk.. Modify play() so that the game will only accept correct input from the user ('b,'g' or 'y').

4.11

public void play()

{

    setUpPegs();

    ArrayStack blue=new ArrayStack(maxPegs);

    ArrayStack green=new ArrayStack(maxPegs);

    ArrayStack yellow=new ArrayStack(maxPegs);

    int difficulty;

    SimpleInput inputDifficulty = new SimpleInput();

    difficulty=inputDifficulty.getInt("How many disks would you like?");

    for (int i=0;i<difficulty;i++)

    {

        disk temp=new disk(20,100-(i*10),0+(i*5),180-(i*20),"red",true);

        blue.push(temp);

        temp.makeVisible();

    }//for

    reDraw(blue,green,yellow);

    while(!(blue.isEmpty() && green.isEmpty()))

    {

        char from, to;

        SimpleInput moveCharacter = new SimpleInput();

        from = moveCharacter.getChar("from: b=blue, g=green, y=yellow");

        to = moveCharacter.getChar("to: b=blue, g=green, y=yellow");

        disk carry=null;

        switch (from)

        {

            case 'b': carry=(disk)blue.pop(); break;

            case 'g': carry=(disk)green.pop();break;

            case 'y': carry=(disk)yellow.pop();break;

            default : System.out.println("error");

        }//switch

        switch (to)

        {

            case 'b':     if(blue.peekTop() != null && ((disk)blue.peekTop()).getWidth()<carry.getWidth()){

                          System.out.println("Please put a smaller disk on a larger disk only."); }

                          else{

                          carry.changePosition(carry.getXPosition()%100,180-(stackHeight(blue)*20));

                          blue.push(carry); break; }

            case 'g':     if(green.peekTop() != null && ((disk)green.peekTop()).getWidth()<carry.getWidth()){

                          System.out.println("Please put a smaller disk on a larger disk only."); }

                          else{

                          carry.changePosition((carry.getXPosition()%100)+100,180-(stackHeight(green)*20));

                          green.push(carry); break; }

            case 'y':     if(yellow.peekTop() != null && ((disk)yellow.peekTop()).getWidth()<carry.getWidth()){

                          System.out.println("Please put a smaller disk on a larger disk only."); }

                          else{

                          carry.changePosition((carry.getXPosition()%100)+200,180-(stackHeight(yellow)*20));

                          yellow.push(carry); break; }

            default : System.out.println("error");

        }//switch

        reDraw(blue,green,yellow);

    }//while(main loop)

    System.out.println("Well Done");

}//play

}//class TowersOfHanoi

4_12. Create a new class named TowersDemonstration which will prompt the user for the number of disks, as in TowersOfHanoi, but which will demonstrate the game by playing automatically. As you develop the algorithm for this class you should consider both iterative and recursive approaches.

There is a classic recursive solution to Towers of Hanoi. Try to find this solution for yourself, and then try to code the solution. If you have difficulty working out the solution for yourself, search for a solution on the web.

4.12

I tried integrating this step for a long time. I don't understand how to put the algorithm I found into the method... and I also can't understand where the method switch() came from (I looked through all the other classes and was unable to find it).

4_13. Compile class ArithmeticExpression. Create an instance of the class on the BlueJ workbench with a valid arithmetic expression String parameter. Execute the evaluate() method with the following expressions. Do you get the predicted results?

4.13

Yes, except for the last one. The expression was "(a/b)" where a = 1 and b = 0. I expected to get either "null" or a string message saying "undefined" (although Mr. Reid would argue "infinity" would be a more accurate message). Instead however, the program could not process the arithmetic expression and broke the method giving me an error. This could easily be coded into giving me either "null" or "undefined".