Problem 12 A) I'm not too sure what's wrong... haven't been able to solve this part. From my answer for part B, it seems that the method is generating elements of the Fibonacci sequence correctly. Anyone else figure this one out?
The code won't compile, because you can't access a non-static (member) variable from a static (class) method. This is fixed by declaring fibAnswers as static.
For part (b), your recursion tree is for the non-memoized version. Your answers should be much smaller, because most of the branches are going to be truncated due to the answer already being stored.
I am putting together a spoiler for the practice final exam for everyone to get a glimpse on the problems. The solutions can be found on the following link:
I want to warn everyone that not all solutions are correct or complete. If you have any thoughts on the problem to discuss or have better answers than what I have provide, feel free to do so in this discussion. I, personally, would like to better prepare for the exam by exchanging ideas of understanding the material we all have covered in class with other classmates.
For problem 1, the number of calls to mergeSort should be 1+2+4+8 = 15. I am assuming the base case is when the list size equals 1. top level: 1 original call to mergeSort. list size = 8. level 2: 2 calls to mergeSort. list sizes = 4. level 3: 4 calls to mergeSort. list sizes = 2. level 4: 8 calls to mergeSort. list sizes = 1.
For problem 6(b), the improvements should be: change the return type to T, and change the return statement from "return x" to "return smallest". If you just delete the return statement, then the method will have no effect when you run it.
For 6(c) the parameter type should be List<T extends Comparable<? super T>>
In problem 11(b), I have forgotten what was discussed about the equals method, but I know it involved with 'this.robotID == o.robotID' in the return statement. Do I need to change one of the IDs from being a class variable to class member to make it work?
For 11(a) and (b), the point is that robotID was wrongly made a class variable instead of a member variable. Removing the static keyword fixes the problem.
For 11(c), you could compare this.robotName to o.robotName instead of using the robotID field. In this case, you need to use the String.equals( ) method rather than ==.
In problem 1, I am a little confused with getting 15 recursive calls for mergesort of 32 elements. To rewrite my solution, I have thought of using the idea that 32 is 2^5, meaning that five levels of recursion are needed to sort the list using mergesort. Where is level 1 is 1 original call to mergesort with size 16, level 2 is 2 calls to mergesort with size 8, level 3 with 4 calls and size 4, level 4 with 8 calls and size 2, and level 5 with 16 calls and size 1. So if you would add 16, 8, 4, 2, and 1, you would get 31. Is this how you find the number of recursion calls in mergesort?
Okay, to clear things up. From what Prof. Hayes was trying to say above about getting 15 recursions was when you have 8 elements in a list to apply a mergesort, not 32 elements from the problem it is asking for. For the 32-element list, you would get 1+2+4+8+16+32 = 63 recursions.
I'm not sure why one would want to throw an expection if you catch it? Why wouldn't the programer just deal with the expection? Are there some expection that the programer can't handel, so it would be better to throw it?
I found this on coderanch.com "Let me start with a general comment about exception handling. The whole purpose of having an exception handling system is to allow each error to bubble up easily to a level where handling it is most appropriate, since the immediate caller of an exception-throwing method often resides at too low a level of abstraction to handle the error properly in the context of the overall application.
Now, remember that exception classes are full-fledged classes in themselves, which means that you can define instance variables and methods. These may tell you more information about the cause of the error than what you can tell from just knowing the exception class. Thus, it's actually fairly common to catch an exception, call one of its methods to learn more about the cause, and then use that information to decide whether you can reasonably handle that condition at your level. If not, then you'd re-throw the exception."
The only thing I would add to the quote Brandon found about re-throwing exceptions is that, sometimes, after catching one exception, one either constructs or otherwise generates a new exception, and throws that instead of rethrowing the original exception. Sometimes this helps to keep the list of exceptions your method might throw down to a reasonable length.
Problem 12
ReplyDeleteA) I'm not too sure what's wrong... haven't been able to solve this part. From my answer for part B, it seems that the method is generating elements of the Fibonacci sequence correctly. Anyone else figure this one out?
B) n=4 Output: 0,1,1,2,3
4
^
3 2
^ ^
2 1 1 0
^
1 0
n=6 Output: 0,1,1,2,3,5,8
6
^
5 4
^ ^
4 3 3 2
^ ^ ^ ^
3 2 21 21 10
^ ^ ^ ^
21 10 10 10
^
1 0
Edit: Formatting for the tree got butchered when I published my post - my apologies.
DeleteThe code won't compile, because you can't access a non-static (member) variable from a static (class) method.
DeleteThis is fixed by declaring fibAnswers as static.
For part (b), your recursion tree is for the non-memoized version. Your answers should be much smaller, because most of the branches are going to be truncated due to the answer already being stored.
You cannot call a non-static variable from within a static method. Took forever to figure this out.
DeleteI am putting together a spoiler for the practice final exam for everyone to get a glimpse on the problems. The solutions can be found on the following link:
ReplyDeletehttps://docs.google.com/file/d/0B3pz06Cf-nEdODZHZ0pwUjdhMHM/edit
I want to warn everyone that not all solutions are correct or complete. If you have any thoughts on the problem to discuss or have better answers than what I have provide, feel free to do so in this discussion. I, personally, would like to better prepare for the exam by exchanging ideas of understanding the material we all have covered in class with other classmates.
For problem 1, the number of calls to mergeSort should be 1+2+4+8 = 15.
DeleteI am assuming the base case is when the list size equals 1.
top level: 1 original call to mergeSort. list size = 8.
level 2: 2 calls to mergeSort. list sizes = 4.
level 3: 4 calls to mergeSort. list sizes = 2.
level 4: 8 calls to mergeSort. list sizes = 1.
For problem 6(b), the improvements should be: change the return type to T, and change the return statement from "return x" to "return smallest". If you just delete the return statement, then the method will have no effect when you run it.
DeleteFor 6(c) the parameter type should be
List<T extends Comparable<? super T>>
In problem 11(b), I have forgotten what was discussed about the equals method, but I know it involved with 'this.robotID == o.robotID' in the return statement. Do I need to change one of the IDs from being a class variable to class member to make it work?
DeleteFor 11(a) and (b), the point is that robotID was wrongly made a class variable instead of a member variable. Removing the static keyword fixes the problem.
DeleteFor 11(c), you could compare this.robotName to o.robotName instead of using the robotID field. In this case, you need to use the String.equals( ) method rather than ==.
In problem 1, I am a little confused with getting 15 recursive calls for mergesort of 32 elements. To rewrite my solution, I have thought of using the idea that 32 is 2^5, meaning that five levels of recursion are needed to sort the list using mergesort. Where is level 1 is 1 original call to mergesort with size 16, level 2 is 2 calls to mergesort with size 8, level 3 with 4 calls and size 4, level 4 with 8 calls and size 2, and level 5 with 16 calls and size 1. So if you would add 16, 8, 4, 2, and 1, you would get 31. Is this how you find the number of recursion calls in mergesort?
DeleteThis is what I got as well.
Delete5 is the number of recursive calls and 15 (nlogn) is the over all complexity of the sorting process.
DeleteOkay, to clear things up. From what Prof. Hayes was trying to say above about getting 15 recursions was when you have 8 elements in a list to apply a mergesort, not 32 elements from the problem it is asking for. For the 32-element list, you would get 1+2+4+8+16+32 = 63 recursions.
DeleteHey all,
DeleteYes, Brandon is correct. I had forgotten the original question said 32 elements, not 8.
This comment has been removed by the author.
ReplyDeleteI'm not sure why one would want to throw an expection if you catch it? Why wouldn't the programer just deal with the expection? Are there some expection that the programer can't handel, so it would be better to throw it?
ReplyDeleteI found this on coderanch.com
ReplyDelete"Let me start with a general comment about exception handling. The whole purpose of having an exception handling system is to allow each error to bubble up easily to a level where handling it is most appropriate, since the immediate caller of an exception-throwing method often resides at too low a level of abstraction to handle the error properly in the context of the overall application.
Now, remember that exception classes are full-fledged classes in themselves, which means that you can define instance variables and methods. These may tell you more information about the cause of the error than what you can tell from just knowing the exception class. Thus, it's actually fairly common to catch an exception, call one of its methods to learn more about the cause, and then use that information to decide whether you can reasonably handle that condition at your level. If not, then you'd re-throw the exception."
Thank you!
DeleteThe only thing I would add to the quote Brandon found about re-throwing exceptions is that, sometimes, after catching one exception, one either constructs or otherwise generates a new exception, and throws that instead of rethrowing the original exception. Sometimes this helps to keep the list of exceptions your method might throw down to a reasonable length.
DeleteI get the linked list memory diagram but what would a memory diagram look like for an array list?
ReplyDeleteThere is a wikipedia article and an example on the following link:
Deletehttp://en.wikipedia.org/wiki/Array_list
I was hoping it was that simple, thanks Brandon.
DeleteHi all,
ReplyDeleteWe will be posting a solution key to the practice exam in just a moment.
Here are the solutions to the practice exam:
ReplyDeletehttps://docs.google.com/document/d/1AqN3DNCGyUIQqX87apHNTvShI4Q6Sipun8zFU7OryaY/edit
For 6(a), how do you calculate the running time?
ReplyDeleteThe running time is O(n) time where n is the size of the list provided. This is because each element of the list is looked at once.
Delete