Big Oh Notation and Heaps

Hey guys. I have a mid-term next friday, and my teacher is giving me an exam from the AP Computer Science AB test. I asked her what would be on it, and i am comfortable with most of the topics (like Stacks, Queues, TreeSets, BinarySearchTrees, etc.), but I have been having trouble with a few topics.

Big Oh Notation. I understand what the point of it is, but i have no idea how to figure it out. For example, if the test gives me an algorithm and i have to figure out the Big Oh Notation, i have no idea how to do this.

Heaps. I understand what they are and why they are used, but i can't seem to understand their Tree representation.

Any help would be greatly appreciated. I am currently reading my textbook trying to understand each topic, but i'm not comprehending it =[

Quote:

---

Originally Posted by gibsonrocker800

Big Oh Notation. I understand what the point of it is, but i have no idea how to figure it out. For example, if the test gives me an algorithm and i have to figure out the Big Oh Notation, i have no idea how to do this.

Heaps. I understand what they are and why they are used, but i can't seem to understand their Tree representation.

---

gibson, best of luck on your exam, I'm sure you'll do fine - you display an above average level of intellect on our forums, even though you say you're still somewhat new to the game.

Big O notation is one of the things that I've never enjoyed. I imagine, even in an AP beginning CS course, the emphasis will not be so heavy on big O. This is left for higher level courses such as Analysis of Algorithms. If you have difficulty with your textbook, check over this. Not to repeat what was in the Wiki, but in my experience, that is such the case - that big O represents the running time of the program in relation to the input. You might want to look at it in this way, simply replacing n with a value and seeing what you come up - can it be explained...etc. O(n) where let's say n = 25, that expression O(25) is linear, but when you say O(log 25) = 1.3979, here we've used O(log n) to say the particular algorithm in question is faster than O(n). I don't fully understand it either, so I shouldn't be the authority on this. Maybe others will chime in.

I thought you meant heap, as in the system heap where objects are stored. Heap data structures simply have the rule that the root node is greater than its children. Pretty basic tree data structure here... what about the representation that you're having trouble with could you elaborate on?

-Capt

Quote:

---

Originally Posted by CaptainMorgan

gibson, best of luck on your exam, I'm sure you'll do fine - you display an above average level of intellect on our forums, even though you say you're still somewhat new to the game.

---

Thanks alot man! That really boosts my confidence coming from you!!


As for the Big O:
My teacher said that there are questions on the test where it will give a sorter (such as MergeSort, QuickSort, etc.) and i will have to identify it and determine the big O notation. She said for these, i should just memorize the Big Oh. So, i'm hoping my memorization will be enough. When she gave me review questions, there were questions that asked for the Big O of the addLast method of a class they implemented. I'll try to figure out how this works.

Heaps:
I got a question in my book(I would post the exact question if i had my book on me) that said it inserts 8 Integers into a heap. And then it says, which of the following is an accurate representation of the min-heap. And there are 4 choices, and, as i understand, the root nodes of min-heaps are the smallest (so i was able to eliminate 2 choices) but the other two were very similar, except that the order was different. But now you said that the root node is greater than its children, so i will see if this solves my problem.




By the way, if you're wondering why i don't ask this stuff to my teacher, it's because, its an AP Computer Science A class, and everyone in my class is learning loops and booleans, so she has no time to teach me, so i learn on my own. Every so often i ask her questions but i'm never fully satisfied. Like i asked her about Big O but she gave me general explanations, couldn't really explain to me how it is obtained. So this is why i come to my friends at JavaForums!

Quote:

---

Originally Posted by gibsonrocker800

Heaps:
I got a question in my book(I would post the exact question if i had my book on me) that said it inserts 8 Integers into a heap. And then it says, which of the following is an accurate representation of the min-heap. And there are 4 choices, and, as i understand, the root nodes of min-heaps are the smallest (so i was able to eliminate 2 choices) but the other two were very similar, except that the order was different. But now you said that the root node is greater than its children, so i will see if this solves my problem.

---

Ah! be careful here.. my interpretation is that there are both min-heaps, AND max-heaps where the root node is smaller than its children and where the root node is larger than the children, respectively. So there is likely a difference. ;)

Quote:

---

Originally Posted by CaptainMorgan

Ah! be careful here.. my interpretation is that there are both min-heaps, AND max-heaps where the root node is smaller than its children and where the root node is larger than the children, respectively. So there is likely a difference. ;)

---

Ahhh, well i'll be sure to check this out tomorrow morning. I had trouble with a few other questions in the review, so i'll post them (along with my proposed answers) tomorrow.

Thanks CaptainMorgan!

My test is tomorrow morning. Here is that question i was having trouble with.

Suppose that Integers 9, 5, 3, 7, 1 are added, in the order given, to an initially empty queue, q, and that Integers 2, 4, 6, and 8 are added, in the order given, to an initially empty stack, s. Also suppose that hp is an initially empty min-heap and that the min-hip method addToHeap adds an element to the min-heap using the standard algorithm for inserting into a heap thus maintaining the min-heap properties after each insertion into the heap. After the following code is executed,

Code:

---

while(!q.isEmpty())
{
    hp.addToHeap(q.dequeue());
}
while(!s.isEmpty())
{
    hp.addToHeap(s.pop());
}

---

which of the following min-heaps is a representation of hp?

A. 1
/ \
2 3
/ \ / \
6 9 5 4
/ \
7 8


B. 1
/ \
2 5
/ \ / \
3 7 8 6
/ \
9 4

C. 1
/ \
2 3
/ \ / \
4 7 8 6
/ \
9 5

D. 9
/ \
7 4
/ \ / \
8 1 2 3
/ \
5 6

E. 9
/ \
8 7
/ \ / \
6 5 4 3
/ \
2 1

-----------------------------------------------------------

There's the question. Now, as far as i know, the root of the min-heap is going to be the smallest number, so 1. So i've ruled out D and E. But to be honest, I don't know whether it's A, B, or C. I'm going to say B.

Someone please help me out, tonight, because my test is tomorrow and there are going to be Heap questions!

gibson, might you be able to reedit this post and put the tree representations in quotes or code tags - to show their true representation.. ? I hate to be a pest, but I can't tell which children belong to which parent because everything appears to be left aligned - and I'm referring mostly to the last row in each choice.. which I can't be 100% sure if it's left-aligned.. . bah, sorry to have to ask. or could you just confirm the last row belongs to the previous row's left most parent..?

gibson.. also. After reviewing your specs.. I agree, for the time being, that the resulting tree will have a root key of 1 - because this is one of the properties of a min-heap, as discussed previously. But also note, that for a queue we know that it's a FIFO structure... so we can assume what will be added to the hp min-heap when you call addToHeap, in the same respect we know that a stack employs the LIFO structure.. so we can assume what will be that popped off and added to the hp, I'm sure you know these properties... so now it's just a matter of mentally working through it.

EDIT:
Knowing the properties just mentiond, your queue becomes: 9, 5, 3, 7, 1 << which is reversed, 1 7 3 5 9 where 9 is FIFO. ie:
9
5 9
3 5 9
7 3 5 9
1 7 3 5 9

And with the stack, a slightly different happening: 2 4 6 8 where 8 is LIFO. ie:
2
2 4
2 4 6
2 4 6 8

Keep in mind that for min-heaps - the child and parent are compared and swapped if the child is less than the parent.
Now based on the code you provided above, we know that the queue is emptied/added first. Which would go something like this:
9

9
/
5 gets swapped:

5
/
9

Next is 3:
5
/\
9 3 , 3 and 5 are swapped

3
/\
9 5 , next is 7:

3
/\
9 5
/
7 , 9 and 7 are swapped:

3
/\
7 5
/
9 and last is 1 and it gets swapped/compared twice!

3
/\
7 5
/\
9 1 becomes:

3
/\
1 5
/\
9 7 and then becomes:

1
/\
3 5
/\
9 7

I believe it's more evident now how the stack will be emptied/added. I also wish there was a better way to display trees in a forum.... anyways, my resulting answer is the same as yours: B. :) Just for kicks I'm going to run through it, so what's next, 8 !

1
/\
3 5
/\ /
9 7 8 looks fine here, so 6 is next:

1
/\
3 5
/\ /\
9 7 8 6 looks good here too... next is 4:

1
/\
3 5
/\ /\
9 7 8 6
/
4 , 4 gets swapped for 9:

1
/\
3 5
/\ /\
4 7 8 6
/
9 and lastly we have 2, which gets swapped compared/swapped twice:

1
/\
3 5
/\ /\
4 7 8 6
/\
9 2 becomes:

1
/\
3 5
/\ /\
2 7 8 6
/\
9 4 finally becomes:

1
/\
2 5
/\ /\
3 7 8 6
/\
9 4

Thus, B :) heh.. that was fun. ;)

Ahh thanks for the help CaptainMorgan. Unfortunately i got a question like this on my test today, I think i might have gotten it right. The test was kinda difficult. The 40 multiple choice questions were okay, i got most of em right. As for the free-response. Those were really hard. I did alright on them but not as great as i thought i would. See my problem is that i can't understand what the AP questions ask. And of course they have to set up a class structure for you. I would much rather them to tell me to write a program that does something, and thats it. I like setting up my own structures.

One of the questions was an implementation of a binary search tree. I had to write the peekMin method. basically what i did was,

Code:

---

//Make a new node that is the same as the root since we are
//going to change it.
TreeNode newNode = new TreeNode(root, root.getValue());
while(newNode.getLeft() != null)
{
    //I can't remember exactly what i wrote
    //Something along the lines of continually going to the left
    //Then, when we reach the bottom node (since the bottom leftmost
    // node is the smallest which is what we are looking for, return this node)
}

---