midterm preparation CSC263

Mid term season seems endless!

This is my posting for preparing csc263.

Let’s start!

Abstract data type(ADT)?

We’re talking about mostly about Abstract data type and how to analyze its running time.

Before to jump into the idea, what is “Abstract data type”?

Abstract data type is like a imaginary machine that have some skills that we need to use.

Programmer is the engineer to build this robot. But if you just simply want to this robot, you just need to know what operation you can use with this.

For example there is a stack in ADT. Just think of one robot called “stack” and what it does is stores all the things that you put in it and take it back to you the item but in reverse order that you put in. So the item that you put in at the last time, will be popped it out first.

Programming is the implementation of this ADT. (i.e., building process of this robot)

Since this is for my midterm preparation, I’ll just explain shortly about each ADT and maybe write more later on.

Today, we will talk about 6 major abstract data structure that I’ve learned in my class.

Insane? Yes, let’s do this without any help from alcohol.

Priority Queue 

Priority Queue is a data structure that stores all items by its priority. Priority Queue is very useful in the real life.It’s like a note that you put on your wall. You will probably put a number besides each item in the list by it’s priority. By the way, by saying priority queue, I’m referring “minimum priority queue” (maximum priority queue is you’re saying a item in order of the size of key in the minimum case, it’s revering the order(i.e., minimum 1,2,3… maximum 5,4,3…))

 Usually, we use heap(complete binary tree) for priority queue. The reason why is heap has nice compact property in it. So you can get the item that has the highest priority in O(1) time. Also, by using the compact property, you can convert it as a list and  since in the list it’s indexed already you don’t need to store key(priority) and also you can get an advantage of using arithmetic between index which takes also O(1) time.

So like all the ADT, we need to perform specific operation on them.

What operation would you expect your priority queue(Memo) will take care of?

The list of work that handles is like this.

Decrease-Key(S,i,k): decrease the value of element at the index ‘i’ to key k

Insert(S,x): insert element x into Set S. 

Minimum(S): return the item with the smallest key.

Extract-Min(S): remove-return element of S with smallest key

All code for those functions are below.

Decrease-Key(S,i,k){

if S[i]< k:

error: Can’t decrease anymore.

S[i] = k

while i > 1 and S[parent] > S[i]:

S[parent], S[i] = S[i], S[parent]

parent = i

}

Insert(S, x){

S.size = S.size + 1

S[size] = ∞

Decrease-key(S, S.size, x)

}

Minimum(S){

return S[0]

}

Extract-Min(S){

k = S[0]

S[0] , S[S.size -1] = S[S.size -1], S[0]

Min-Hipify(S, 0) #It’s just a bubbling down process.

}

I think the “Insert” is pretty smart to move of using the function “Decrease-key”

Binomial Heap

Binomial Heap is bit more fun than the “Priority Queue”.

Binomial Heap is a set of Binomial Tree that has minimum-heap property.

If we can call the Priority Queue as a “Memo”, then we can call the “Binomial Heap” as a calendar.

So it’s a collection of Memos that is listed by date and each entry for a day is binomial tree.

Let’s see what is mean by “Binomial Tree”

Binomial Tree is Tree that has a mean-heap property and it can be defined in a recursive way.

So it’s like this.

It starts from a node and to increase the size of tree, you need to put same thing and you can go to the next level. Not obvious? I can explain this by pictures below.

The first one is valid because it’s adding same things but second one is not. Easy?

So if you add same thing, the thing that you’re adding becomes the left most child of the root of another tree and you should decide which tree will be the tree that contains root by their value.

So the tree at the right side of addition is added to the other tree b/c they should keep min-heap property(i.e., small things should precede the big things)

So the formal drawing will be look like above.

There are some important things that you need to remember regarding this tree.

THINGS that you MUST stick into your brain about “binomial tree”!

For “Binomial Tree B_k(k is the height of the tree)”

1. There are 2^k nodes.

– Well, B1 = 2*B0 and B2 = 2*B1 = 2^2B0.

Hence, Bk = 2^kB0 and the number of node for B0 = 1.

Hence, Bk = 2^k.

2. The height of the tree is k.

Well, we define Bk in terms of height.

3. There are exactly kCi nodes in the height i. (C is combination)

(I explained about this at the end of this list)

4.The root has a “k” degree, which is grater than that of any other node; moreover if the children of the root are numbered from left to right by k-1, k-2, ….,0 child i is the root of the subtree Bi.

Well, the first sentence is not a very exciting fact. Because, when you’re adding something to it, you are adding the root as a sub child of the other tree’s root. SO the children nodes of the root is increased by 1. Oh by the way degree is just another term to call # of children nodes. I know most of terms are annoying. I guess there are some obnoxious people in the academic filed keep saying “We have to call this and this!”. It’s annoying to me. Anyway, second sentence in 4. seems pretty interesting. That’s saying that if you took out a root then you have k sub – trees. But it’s just merely tree was recursively defined and the tree has all the sub tree that we added recursively.. That’s it.

5. The height of the tree is lgn. Well the height of Bk is k and the # of nodes are 2^k = n hence, k=lgn.

So let’s explore the 3. part. It’s related to the reason why we call this kind of tree as binomial tree.

kCi is the coefficient for a^ib^(k-i) and a^(k-i)b^i in the binomial, (a+b)^k.

Hence, we call this tree as binomial tree.

It took me for a while to understand why this kind of things happen b/c I couldn’t find any information of this from the internet. SO this below is what I’m guessing.

Let me use the example of B3.

To make B3, we need to “two” B2s.

Let’s call the tree at the left as “B” and the other as “A”. Then, write “b” on the all nodes in “B” and let’s write “a” on the nodes of “A”. # of nodes of A, B = 4 = 2^2.  # of nodes of  B3 = 2^3.

Well, just notice the fact above and let’s them put together to make B3.

Can you see the symmetric structure of that?

The total number of nodes in tree should be 2^3, the number of node at the first floor should be 1 and the most important thing is the tree should be symmetric!

Now what you can think of? Yes, binomial of (A+B)^3 = (A+B)(A+B) (A+B) because binomial is symmetric and it the coefficient for the end term(a^3 and b^3) is zero! and also the sum of all the coefficient is 8= 2^3 which is the total # of nodes. We can think of why this happen esially. Just put 1 for A and B. When we think of tree in terms of the number of nodes, each node whether it’s from A or B it is just 1. So we put 1 for A,B and we got 2^3. I hope it more make sense. So the all the outcome that “I” wonder(Why it’s called binomial tree and why each height has the number of nodes which is same as the coefficient of binomial?) was actually because of it’s symmetric structure. (Oh, it’s still my guess, so maybe it’s wrong to assert it.)

Well, that was fun-wasting of time..And now we

It was not hard to prove it. You can use induction but I just wanted to understand why this kind of things happen.

So finally binomial heap is the list of these binomial trees.

e.g., {B1, B3, B5}

It’s sorted by the height of the trees and any tree can’t have same height in the list. Each item is actually the root of the each binomial tree. Well, That’s the rule that we need to stick with. Let me show you some picture of Binomial Heap.

<Some pic later from PDF no internet in my home. DARN IT>

There are some property we want to look at before what operation it has

1. Each tree has mean-heap property

2. For any non-negative integer k, there is at most one binomial tree that root has k degree.

And in the PDF file that my prof gave to me, it’s saying the 2. part implies that n-node binomial heap(Binomial heap that contains n nodes total) has at most bottom of (lgn)  + 1 trees.

First time I heard that, I was what? how? and then I started understand after I saw an example given in the file. It’s saying that we need to observe the number of binary string to express a number. So if you got 11 then it’s 1101 => 4 strings which is (bottom of lg11 )+ 1 = 3 + 1.

And we can apply this for our binary heap. Let’s say we got n-node binomial heap then, since binomial heap is a merely list of the binomial trees, we can express n as some kind of form of 2^k + 2^j …. It’s absolutely same as how we represent a number with binary string.

But only difference is if the binary digit is 0 it doesn’t matter to count the binary string but it’s meaning that there is no binomial tree for that spot. Confused right?

Let’s think of 11 case. Using binomial 4 strings you can make the number and the string is

1101. But let’s think of 11-binomial heap! Then there’s only B0 , B1, B3 tree which are 3 trees because the spot for B2 is 0.

Well, we saw all the property then, let’s go to the operation part.

The operation that we can do with this ADT is like below.

1. Make-Binomial-Heap

2.Find-Minimum

3. Union

4. Insert

5.Extract-Min

6.Decrease

7.Delete

AVL tre

Augmenting data structure

-list tree, weighted tree

Hashing

Disjoint set