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.
Sunday, 27 November 2011
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
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.
Sunday, 13 November 2011
Trees #2 6-10 & 11-12 & End
STUDENT TASKS
6_6. Complete the implementation of method recursiveFind().
{
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.
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.
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.
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.
Monday, 7 November 2011
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.
//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
}
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)
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
}
Subscribe to:
Posts (Atom)