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".

4.6-4.9

4.6

public static String getReverse(String word)

    {

    String str = "";

    for (int i = 0; i<word.length(); i++)

    {

       str += word.substring(word.length()-i-1, word.length()-i);

    }

    return str;

    }//getReverse

    //uses recursion to reverse word

    public static String getReverseRecursive(String word)

      {

     if (word.length()==1)

     {

           return word;

     }

     else

     {

       String str = word.substring(word.length()-1) + getReverseRecursive(word.substring(0, word.length()-1));

       return str;

    }

    }//getReverseRecursive

4.7

            The advantage of using an iterative approach for me is the logic, it makes much more sense for me to go through something in a linear fashion, or rather simply not backwards as you do in recursion. On the other hand, using a recursive approach is much more efficient as it doesn't use any loops, and simple uses some commands and calls. Essentially, if you can think of the solution recursively it's much more effective, but it's very hard to do so for me, in respect with an iterative approach.

4.8

public static boolean isPalindrome(String word)

    {

        if(word.length()%2 == 0)

             return(word.substring(0,word.length()/2) == getReverse(word.substring(word.length()/2, word.length())));

        else return(word.substring(0,word.length()/2) == getReverse(word.substring(word.length()/2+1, word.length())));

    }

}//class StringReverseDemo

4.9

I actually forgot the meaning of static and non-static, I'll ask about it in class.

4.1-4.5

4.1 Modified methods:

public Object pop()

{

    if(stack[stackTop] == null)

       System.out.println("Stack underflow, operation can not be completed");

    Object temp = stack[stackTop];

    stackTop--;

    return temp;

}//pop

public Object peekTop()

{

     if(stack[stackTop] == null)

       System.out.println("Stack underflow, operation can not be completed");

     return stack[stackTop];

}//peekTop

4.2

private boolean isFull()

{

     int count = 0;

     for(int i = 0; i<stack.length; i++)

     {

         if(stack[i] != null)

            count++;

        }

     if(count == max)

        return true;

     else return false;

} // returns true if full, otherwise returns false.

4.3 Modified push() method:

public void push(Object x)

{

    if(isFull()) {

      System.out.println("Stack overflow, operation can not be completed");

      return; }

    stackTop++;

    stack[stackTop]=x;

}//push

4.4 To be honest, I have no idea how to populate the ArrayStack in order to test it, and I'm coding out of pure logic, which so far seems to be working for me. I'll talk to you later about how to put in values for the Array in order to test it.

4.5

import java.util.ArrayList;

public class ArrayListStack implements Stack

{

    private ArrayList stack;

    private int stackTop;

public ArrayListStack()

{

    stack = new ArrayList();

    stackTop = -1;

}

public boolean isEmpty()

{

    return (stackTop==-1);

}//isEmpty

public void push(Object x)

{

    if(isFull()) {

      System.out.println("Stack overflow, operation can not be completed");

      return; }

    stackTop++;

    stack.get(stackTop) = x;

}//push

public Object pop()

{

    if(stack.get(stackTop) == null)

       System.out.println("Stack underflow, operation can not be completed");

    Object temp = stack.get(stackTop);

    stackTop--;

    return temp;

}//pop

public Object peekTop()

{

     if(stack.get(stackTop) == null)

       System.out.println("Stack underflow, operation can not be completed");

     return stack.get(stackTop);

}//peekTop

private boolean isFull()

{

     int count = 0;

     for(int i = 0; i<stack.length; i++)

     {

         if(stack.get(i) != null)

            count++;

        }

     if(count == max)

        return true;

     else return false;

} // returns true if full, otherwise returns false.

}//ArrayStack

AP Baron's Test

1. Report your final score for the test.

 I got 17 wrong on the multiple choice

I got two 7s an 8 and a 9 on the free response, at least that's how I graded myself, I feel it really depends, and their solutions are different from mine.

2. Predict your AP Grade

According to that I have a low four for the AP

3. Analyse your performance. Why did you loose points? Are there things that you do not understand? What do you need to do to improve your performance on the exam?

I lost points for so many of the questions, I feel some of them are just plain out wrong answers, and many of them are two-faced... I never liked the Baron's questions, however.

Practice Test

Do practice GridWorld Test (Multiple Choice & Free Response)

Check your answers.

Report on how you did.

I got two wrong, and can't understand why.

Are there still issues that you have problems with?

Yes there are, I'm unsure about why I'm wrong.

GridWorld Project

I haven't started coding, but what I think I'll do for my project is make a specific gridtype which starts with actors of a sort which  can only move diagonally, and once for each color which will indicate team color. I find that coding the actors will be quite simple, but the thing that looks hardest is defining the grid to begin with, and making sure that the sides each get one turn.

Barron's Last Chapter

How did you do on the multiple choice questions?

I got some wrong, but often I was correct.

Did you understand your errors?

Not exactly. I mean I can see what I was wrong, but not why the answer is a better answer. These questions seem to be very theoretical, and therefore I feel that the best answer as written in the book is often debatable.

What do you not understand?

See Above.

Barons

I forgot my Baron's book at school, I will do it tomorrow in my free block.

Case Study Project

Gridworld Checkers.

Barons 357-374 Multiple Choice

How did you do on the multiple choice questions?

I did pretty well, I got only a few mistakes, and most were not conceptual.

Did you understand your errors?

Not all...

What do you not understand?

 In the turning questions, I was confused. E.g. question 2 stated that when a bug turns it takes its direction and adds 45 degrees to it. So if it was South, it would be 180 + 45 = 225. Mathematically speaking, 225 degrees is South East not South West as the book said it was.

Grid World Part 4 Part 2

Gridworld: Part 4: Interacting Objects: Set 9: Page 35

        

Gridworld: Part 4: Interacting Objects: Set 9: Page 35

1	Why doesn’t CrabCritter override the processActors() method?	It doesn't override the processActors() method because the implementation of the method in the critter class is to eat other actors, and the crab does the same with movement restrictions and eating restrictions.
2	Describe the process a CrabCritter uses to find and eat other actors. Does it always eat all neighboring actors? Explain.	After moving either left or right (depending on the random value) it will check if a neighbor which is not a rock and is a critter is in front, front left, or front right of it and remove it. It won't eat all neighboring actors if they aren't critters, or if they're a rock. This because of the implementation of the processActors() in the critter class.
3	Why is the getLocationsInDirections() method used in CrabCritter?	I am not sure about this question. I can't really understand the getLocationsInDirections() method.
4	If a CrabCritter has location (3, 4) and faces south, what are the possible locations for actors that are returned by a call to the getActors()  method?	I was under the impression that getActors() returns all actors in the grid, but I assume it is only the locations around the critter, therefore they would be (2,3), (3,3), (4, 3), (2,4), (4,4), (2,5), (3, 5), (4, 5).
5	What are the similarities and differences between the movements of a CrabCritter and a Critter?	CrabCritter moves in each call of act(), just as critter does; however, it can only move right, left, or turn 90 degrees either left or right, and relies on random values in order to determine its movement.
6	How does a CrabCritter determine when it turns instead of moving?	It checks whether it's movement is blocked in any direction. If it is, then it turns instead of moving.
7	Why don’t the CrabCritter objects eat each other?	I thought CrabCritter objects can eat each other... there seems to be no part of the code which suggests otherwise.

Grid World Part 4 part 1

1	page 30 What methods are implemented in Critter? The act(), getActors(), processActors(), getMoveLocations(), and selectMoveLocation() methods are implemented in Critter, although it still contains methods from it's superclass Actor.
2	What are the five basic actions common to all critters when they act?    The actors are collected from the grid, they all invoke the processActors() method, they get their moves through getMoveLocations(), they select a location through selectMoveLocation(), and finally make a move through makeMove().
3	Should subclasses of Critter override the getActors()   method? Explain No, because the getActors() method is used to collect all actors on the grid, and if a subclass of critter overrides it, it might not even get to act because it won't be collected into the list of actors.
4	Describe three ways that a critter could process actors.    It could change the state of the critter and the actor, it could change the state of the critter based on the actor, or change the actor (i.e. removing it).
5	What three methods must be invoked to make a critter move?  Explain each of  these methods.  processActors(), getMoveLocations(), and selectedMoveLocation() must be implemented in order for the critter to move.
6	Why is there no Critter constructor? This is because the critter class is an abstract class. Furthermore, it implements methods for its subclasses to use, but can't make any objects.   page 33 1 Why does act() cause a ChameleonCritter to act differently from a Critter even though ChameleonCritter does not override act()? ChameleonCritter acts differently from a Critter even though it doesn't override act() because it has a different implementation of the processActors() method which it does override to make it's color that of its neighbors. 2 Why does the makeMove() method of ChameleonCritter call super.makeMove? ChameleonCritter calls super.makeMove() because it wants to override the makeMove method but at the same time implement the previous implementation of the method as part of the new method.   3 How would you make the ChameleonCritter drop flowers in its old location when it moves? You would put an implementation of dropping flowers in the beginning of the makeMove() method, so that for each call to the makeMove() method it would drop a flower thereby putting a flower where it was.   4 Why doesn’t ChameleonCritter override the getActors() method?  The ChameleonCritter class doesn't override the getActors() method because it wants to use the same implementation that the critter class used in order to find the actors currently on the grid. 5 Which class contains the getLocation() method?  Actor contains the getLocation() method. 6 How can a Critter access its own grid? If by grid, what is meant is location, then the critter can simply call the getLocation() method since it is implemented in the Actor class.

Barron's Polymorphism Multiple Choice

How did you do on the multiple choice questions?

I got most of them right, apart from one or two.

Did you understand your errors?

Yes. They were errors in understanding the question, but not conceptual.

What do you not understand?

I couldn't really understand the difference between polymorphism and overriding methods. From what I could understand, it seems overriding a method is simply redefining a method in a subclass, and polymorphism is using the correct overridden method in run-time. Is that precise?

Gridworld Part 3

Assume the following statements when answering the following questions. Location loc1 = new Location(4, 3); Location loc2 = new Location(3, 4); 1. How would you access the row value for loc1?
1. loc1.getRow() would return the row value of loc1. 2. What is the value of  b  after the following statement is executed? boolean b = loc1.equals(loc2); 2. The value of b will be false because loc1 does not have the same values for row and column as loc2.
3. What is the value of loc3  after the following statement is executed? Location loc3 = loc2.getAdjacentLocation(Location.SOUTH);  3. loc3 will have the values (4, 4).
4. What is the value of dir  after the following statement is executed?  int dir = loc1.getDirectionToward(new Location(6, 5)); 4. dir will have the value 135 because Location(6, 5) is directly South East from loc1.
5. How does the getAdjacentLocation()   method know which adjacent location to return? 5. It knows which adjacent location to return by taking a direction as a parameter, which will direct it towards the requested location. pg. 21 1. How can you obtain a count of the objects in a grid? How can you obtain a count of the empty locations in a bounded grid? 1. You can make a loop to go through the grid incrementing rows and collumns by 2 in order to not count the same object twice, and increment a counter value by the getNeighbors() method for each of the locations. You can do the same but with incrementing the counter value by the getEmptyAdjacentLocations() method to find the empty locations in a bounded grid. 2. How can you check if location (10,10) is in a grid? 2. You can call the isValid() method and put the location (10, 10) as a parameter. If it returns true it is valid, otherwise it is false. 3. Grid contains method declarations, but no code is supplied in the methods. Why? Where can you find the implementations of these methods?  3. 3. Because some might be labeled as abstract and to be implemented by its subclasses. In the subclasses you can find implementations of these methods.   4. All methods that return multiple objects return them in an ArrayList.   Do you think it would be a better design to return the objects in an array? Explain your answer.   4. No, because an ArrayList can grow infinitely while an array has a set size. It could be that we would want to mess with the size of the ArrayList, and therefore, it serves as a better holder of the objects. pg. 23 1. Name three properties of every actor. 1. They all have a color, a direction, and an implementation of the act() method. 2. When an actor is constructed, what is its direction and color? 2. When an actor is constructed its direction is north and its color is blue. 3. Why do you think the Actor class was created as a class instead of an interface? 3. It was probably made as a class instead of an interface because it is a general rule for all objects on the grid, and not necessarily something they implement. The Actor class also defines fields which an interface cannot do, which apply to its subclasses. 4. Can an actor put itself into a grid twice without first removing itself? Can an actor remove itself from a grid twice? Can an actor be placed into a grid, remove itself, and then put itself back? Try it out. What happens? 4. No, it can't put itself into a grid twice without first removing itself. No it also can't remove itself twice. It also can't place itself, then remove itself, and then put itself back, because as soon as it is removed it disappears. 5. How can an actor turn 90 degrees to the right? 5. It can call its setDirection() method and place the direction + 90 as the parameter of the method thus turning it 90 degrees to the right. pg. 25-26 1 Which statement(s) in the canMove()  method ensures that a bug does not try to move out of its grid?   The statement "if(!gr.isValid(next))     return false; else ... ensures the bug doesn't try to move out of the grid. 2 Which statement(s) in the canMove() method determines that a bug will not walk into a rock?   The statement "return (neighbor == null) || (neighbor instanceof Flower)" determines that a bug will not walk into a walk because it evaluates to false if the neighbor object is a rock, which will cause the canMove() method to be false as a whole and not let the bug walk into a rock. 3 Which methods of the Grid  interface are invoked by the canMove()  method and why? The isValid() method of the Grid interface is invoked by the canMove method to check whether the location chosen by the bug is still in grid. 4 Which method of the Location  class is invoked by the canMove() method and why? The Location class is invoked in order to find a new location for the bug to move to invoking its getAdjacentLocation() method. 5 Which methods inherited from the Actor class are invoked in the canMove() method? None are invoked in the canMove() method.   6 What happens in the move() method when the location immediately in front of the bug is out of the grid? When the location immediately in front of the bug is out of the grid it removes itself from the grid. 7 Is the variable loc needed in the move() method, or could it be avoided by calling getLocation() multiple times? It is not needed in the move() method because the loc variable is only referred to once, and therefore is redundant.   8 Why do you think the flowers that are dropped by a bug have the same color as the bug? Because it calls the getColor() method when constructed which will return the bug's color, and construct a flower with that color.   9 When a bug removes itself from the grid, will it place a flower into its previous location? Depends when. If it simply calls the removeSelfFromGrid() method then it won't. However, there is one case where it will. In the move() method, if the bug finds no valid place to go to, it will remove itself from the grid, but at the same time place a flower in its place.   10 Which statement(s) in the  move() method places the flower into the grid at the bug’s previous location? "Flower flower = new Flower(getColor()); flower.putSlefInGrid(gr, loc);" puts a flower in the bug's previous location.   11 If a bug needs to turn 180 degrees, how many times should it call the turn() method? It will have to call the turn() method 4 times, because each one call moves the but 45 degrees to the right.