<p>Alright, I just have a couple questions about the exam. (By the way, I crammed pretty much the whole course as a self-study in a couple days so I apologize if some of these questions seem dumb or obvious):</p>
<li><p>Do we need to actually memorize Big O notation run times for everything? I have the Barron’s book and at the end of all the collections and data structure chapters they have a table with different methods for different collections with all the corresponding Big O notation run times for everything. They also have them for searching/sorting.</p></li>
<li><p>For searching/sorting should we know the actual Java code to program the different ways search and sort or is a overall idea of how the search/sort works fine for the exam?</p></li>
<li><p>The Barron’s books occasionally has a constructor or something that they say is not included in the AP Java subset. We’re still allowed to use it without being penalized, right?</p></li>
<li><p>In the Barron’s book they also have a lot of constructors for collections like
ArrayList(Collection<? extends E> c), or
LinkedList(Collection<? extends E> c)
What exactly do these constructors do? Could you give a short example Java program that they would be used in? Are they necessary or useful for the exam?</p></li>
<li><p>What exactly are abstract classes and what’s their purpose?</p></li>
</ol>
<p>If anyone could answer any of those questions, it would be very much appreciated.</p>
<p>I'm studying for this right now, so I hope this will be helpful for you, and correct too.</p>
<ol>
<li><p>You need to know Big O just a basic knowledge here are the sorts you need to know
Quicksort: O(n log n)
Mergesort: O(log n) Heapsort: O(n log n)
Selection Sort O(N^2), Insertion O(N^2) Bubble O(N).
Binary Search has O(log n) with O(N) worst case.
Just remember for loop is O(N) nested for loop is O(N^2) and anything where it's divided into two is O(n log n)</p></li>
<li><p>Be familiar with the methods in Maps, Sets, Trees, HashMap, but you probably won't write one. You'll use the stuff already made in the appendix.</p></li>
<li><p>Use whatever you want, if it works and does what they want you're good! Also, answer the question how they tell you, don't do things extra to that</p></li>
<li><p>No Idea....</p></li>
<li><p>Abstract classes are implemented in a class, and instead of an interface which can only be extended once an abstract class allows for additional stuff. I have a really good explanation of this that I wrote, which I'll add in for you in a moment.</p></li>
</ol>
<p>It would definitely be wise to remember the Big O for sortings, their worst time and which is the most efficient. You won't be made to write out a sorting code, you might be given a method and be asked to identify which sorting it is, so it might be helpful to differentiate between all those sortings. </p>
<p>ArrayList<string> list = new ArrayList<string>() would create an arraylist of strings. So if if you say list.get(0), it will return a string rather than an object. </string></string></p>
<p>I always mix up interface and abstract classes, so I know abstract class by differentiating it from an interface. An interface can't provide implementation for any of its methods, and it can't contain instance variables where as abstract can do both of the above. </p>
<p>Hope this helps. I don't know about using other subsets, I don't know why you would, but as long you stay with the version AP uses, you should be fine.</p>
<ol>
<li><p>Yes. There will always be 3-4 Big O problems that require prior memorization... really know the runtimes of different searches.</p></li>
<li><p>You should know the actual code to the extent that you recognize the method of searching/sorting if you were presented with the code. You won't actually have to write it, just know how it works... so if you see a code fragment, you can quickly say, "Gosh, that's definitely a MergeSort".</p></li>
<li><p>I'm not really familiar with the Barron's books, so I would like a little bit more info. But if the constructor syntax is supported by Sun Microsystems (i.e. documentation of it exists) then you should not be penalized for using it.</p></li>
<li><p>The parameters for those constructors are rarely necessary. I myself am not familiar with what types of programs these would be used for, but I guess the constructor supports some type of merge behavior because it specifically asks for a structure that extends the Collections interface. But honestly, do NOT bother with it. LinkedLists and ArrayLists on the AB test are VERY straightforward in their declarations.</p></li>
<li><p>Abstract classes are like interfaces except that Abstract classes can be declared and extended instead of implemented. Abstract classes usually contain at least one abstract method (also supports non-abstract methods) that any class extending it must possess. Like interfaces, abstract classes are used to impose some structure to child classes. </p></li>
</ol>
<p>It would be very difficult to explain abstract classes here adequately, so I really suggest that you look them up quickly, as they are very easy to understand. Also be sure that you understand inheritance and the Big O notation. If you do all this, you'll be well on your way to a 5.</p>
<p>By the way, if someone else has anything to add, please do so, as I am typing with a severe cold and may be saying that 2+2==5 for all I know. </p>
<p>I briefly looked through it and I'm not quite sure how to use it to my benefit, besides of course all the code for the case study. What are the things I should be paying attention to?</p>
<p>2 Questions concern the following algorithm, which copies values from an array into a binary search tree and then prints the values, using an inorder traversal of the tree.
Step 1: Initialize the tree to be empty.
Step 2: For each value in the array from left to right, insert the value into the tree.
Step 3: Print the values in the tree using an inorder traversal.</p>
<p>33) Assume that the array contains N values. Which of the following best characterizes the worst-case running time of the algorithm?
A) O(1)
B) O(log N)
C) O(N)
D) O(N log N)
E) O(N^2)</p>
<p>34) The algorithm is guaranteed to exhibit its worst-case running time under which of the following conditions?
A) The array contains only positive values.
B) The array contains only negative values.
C) Half of the values in the array are positive and half are negative.
D) The values are stored in the array in sorted order.
E) The values are stored in the array in nonsorted order.</p>
<p>The quick reference is only really useful to verify that a certain method exists or discover a new one in the nick of time. For example, you should be very familiar with String methods, but there might be some esoteric ArrayList methods that might help you when you're taking the test. You don't want to use a method that doesn't exist, or rewrite a preexisting one!</p>
<p>Another important use is that the reference also tells you what type of structure a certain method returns. For example, I forgot that (TreeMap or HashMap object reference).keySet() returned a set (it was very early!) rather than something that implemented Collections, like a List or ArrayList. That saved me a lot of points!</p>
<p>Just be sure to check some of the methods you use in the FR section to make sure you're spelling the method call properly, etc.</p>
<p>33) O(N^2)
34) E) The values are stored in the array in nonsorted order.</p>
<p>lol...ok you probably don;t want to listen to me though...since i'm probably not even going to take the test seriously tomrr...considering i don;t know anything</p>
<p>I can say for sure that Harkley at least didn't get the Big O for bubble sort correct. Bubble sort is N^2. I also don't trust the other Big O's he wrote because they look wrong to me. No algorythmn for any of the sorts is N.</p>