[DSA] binary tree

terminology
the root: the beginning of a tree.

every node is possibly the root node for the nodes below it. eg. the parent node.

parent node, the n-1 lvl of the n's lvl node.
child node, the n+1 lvl of the n's lvl node.

(n-1)
|
___n____
| |
(n+1) (n+1)

edge, the path for traversal to happend.
leaves, the lowest lvl in the tree.

a binary tree, a tree where each parent node only have 2 children.

binary search tree (BST)

a binary tree, where the root node is always the middle value of the list of values.

remember binary search from previous week?
what are the 2 possible condition to be satisfied before one can qualify for binary search?

BST it self is not efficient. there is a possibility that the insertion of the node will cause it to behave like a worst case binary tree.

we need a sorted BST, where each time a node is inserted the tree is "sorted" to find out which is the new node. What are the implications if the tree are always sorted when insertion or deletion is done??? Is there any other possible way to enhance it?

3 ways for tree traversal
-Inorder
Traverse the left subtree
Visit the current parent
Traverse the right subtree

-Preorder
Visit the current parent
Traverse the left subtree
Traverse the right subtree

-Postorder
Traverse the left subtree
Traverse the right subtree
Visit the current parent


uses of binary tree data structure
- compression
- encoding
- conversion of mathematical formula to prefix or post fix form
- data structure of choice for "fast" retrieval of search items

there are many other type of binary tree
full binary tree
perfect binary tree
balanced binary tree
self balancing binary tree

[DSA] map and set container

map<string,int> mapp;
map<string,int>::iterator mit;
string name_search;

    mapp.insert(map<string,int>::value_type("Amy",81377442));
    mapp.insert(map<string,int>::value_type("Bob",32731631));
    mapp.insert(map<string,int>::value_type("Catherine",32387163));
    mapp.insert(map<string,int>::value_type("Danny",21321312));
    mapp.insert(map<string,int>::value_type("Ecuador",54543947));
    mapp.insert(map<string,int>::value_type("Felicia",32535612));
    mapp.insert(map<string,int>::value_type("Genie",24172312));



refer to above on how the map data structure is used.


use the map data structure to satisfy the following requirements.
1. create a phone book application that can store name and phone number.
1a. perform a display all entry in the phone book.
2. phone number need to that ensure it is 8 numerical digits only.
3. initialize the phone book application with some data.
4. perform a lookup for a random entry in the phone book and display it.

challenge
5. Suggest a method to store address, email and msn address to the phone book that you have already created.
6. what are the advantages and disadvantages of your method??? explain why you choose the design.

[DSA] searching

Have you ever tried to find something in your house/room. Yet can't seems to ever find it. Now, lets not talk about misplacing items out of carelessness. Let's discuss how to "find" items in your wardrobe.

Assume you have your apparels hanging in the wardrobe, how would you "find" your favorite shirt/dress? would you start looking from the left hand side? the right hand side or simply in the middle???

If you find 1 apparel at a time from either direction, that is linear search. The worst case scenario is, you would traverse all your apparels before finding your favourite.

If you have sorted your apparels according to a certain sequence, eg, warm colours to the right and cold colours to the left, you can simply start finding from the middle, then to the left if your favourite falls in the cold colour. This is binary search. searching time can be reduced significantly.

Again, if you do like what i did, simply pile up all my apparels in the wardrobe without sorting/folding/ironing it. "Finding" for a particular item in the wardrobe can be disastrous.

Linear Search => O(N)

Go through the entire array of items to lookup on the searched key. The sequence of items are not sorted.

Best case , the 1st item in the array.

Worst case, the last item in the array.

Average case, traverse for half of the array

Binary Search => O(logN)

Uses a divide and conquer method.

array of items must be sorted first, involves a cost.

L <> root

|---|---|

L---M---R

For any array of 1000000 items, Linear search need 500000 comparison (assume an average case), Binary Search 20 comparison.

Pop Quiz

1. Create a generic code of linear search to take in different data type.

2. Create a Binary Search tht uses recursive method.

3. Use find() or search() from the STL to do a lookup of a string, among many strings stored in the memory

[DSA] Sorting

Here comes the interesting part in algorithms.

Sorting and searching are the crowns in the algorithm topic. So to speak, these are hottt topics for research in computer science world.

Efficiency, cost. Remember???

We will be examining bubble sort, insertion sort, selection sort and merge sort in details. Studying the complexity of the above algorithms, and not forgetting the implementation of the algorithm. Both DIY code and STL.

But Why Bother to Sort?

Here comes the question>>>>>>>>>

1. Implement sort descending for Bubble Sort, Selection Sort, Insertion Sort, STL sort. Use int arrays or vectors to try it out.

2. In our session, we use integer to demonstrate sorting. Is it possible to sort characters, strings, double, objects etc? Use vector or arrays to try it out.

3. Use the sorting algorithm of your choice, sort 10 tropical fruits of your choice.

4. On top of the previous implementation, create a class for fruits with 2 parameter namely int price and string fruitName. Sort the 10 tropical fruits according to fruit name or price. Your implementation should be able to sort both price and fruitName ASC or DESC. A menu might help in here.

5. Lastly, what considerations when we need to ponder when comparing 2 arbitrary Sort Algo A and Sort Algo B. How would we really know that A is better then B ?

There might be more then one implementation of the above sorting algorithm. Below are my flavor for the 3 algorithm. Codes are commented for easy following.

//bubble sort

//insertion sort

//selection sort

//merge sort

[DSA] Queue

Long time ago when i was still working in shenton way...

I need to wear shirt+neck tie+business slack. If there is a need to meet then client, add another blazer under the blazing sun. It rhythms rite~

Geek like me, I find matching colour of my outfits seem to take forever to learn. There is no hard and fast rule. Best, it is very subjective. Different people will give you different preference and a piece of their mind. ARGHzzzzz. How nice if (day=monday){setBlue();} can be applied to matching my attire.

So to play safe, I bought seven sets of outfit that the colour would match generally. Hang them in my wardrobe from left to right for monday to sunday (I work 8 days per week). I applied FIFO (first in first out) on my "queue" of attire. hehe. Because, I always take from my LHS (Left Hand Side) every morning for my business, and replenish at the RHS after it is done from the laundry.

To hide the fact that i am lazy to choose my attire, and there is a high probability I would wear the same thing for that day of the week for all the weeks in a year. I did a one left shift on my "Queue". Then my wardrobe queue would behave like a barrel shift register that shifts by one bit. Hence my algorithm would keep me safe from the optic blasts of the "fashion police". Sad to say, I still did not escape the scrutiny of the fashionista.

There is this girl in my office, which takes a mental note on the pattern of the occurrence of my attire. She observed my algorithm for about 3 weeks then I am busted.... No, she did not became my wife.

Drill Questions

1. Create a queue of 10 items, of your choice.

2. Assume that the 4th item in the queue is of higher priority, retrieve it first.

3. display the remaining items in the queue.

HEROES ONLY!

4. Create a queue of objects. Each object have a different priority 1-10. 1 is highest priority, 10 otherwise. Object with the highest priority in the Queue need to be service first.

5. Based on 4, create objects at random interval of 1s to 10s and enqueue them. You can assume that the queue is dequeue at every 1 second

6. In the emergency ward, some cases are more serious then the other. Assume there is more then 1 queue is available. Suggest a method that would give Queue tickets to non-priority case, while ensuring life threatening case get service accordingly.