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
Tuesday, January 25, 2011
Monday, January 24, 2011
[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.
Tuesday, January 18, 2011
[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
Monday, January 17, 2011
[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
Tuesday, January 11, 2011
[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.
Monday, January 10, 2011
[DSA] stack
Stack, a last in first out (LIFO) type of data structure.
very similar to our STL list learned last week, there is also a STL stack.
|a|
|b|
|c|
Long long long time ago when i was still a student and still staying in the hall (Now I am still a student, constantly learning new things!). My friends always asked me why i always wear the same t-shirt from monday to sunday. Being the computer science student, I try to explain to them the reason using the stack data structure. Every time my laundry is done, it is folded nicely (assume please) into a stack. When I fold my t-shirt, and placed them in a stack. I fold them in the same order for every week and always take from the top of the stack of tshirts so that my wardrobe will not be messy(assume it is not messy).
Talking about needing randomization in folding t-shirt and putting them on a stack. Every morning wake up, I am always in a rush. So, I always choose the first t-shirt (the top in stack data structure) of the stack. The cycle repeats it self again and again. Sometimes, I do accidentally pull a tshirt out of the middle of the stack and the stack of tshirt just collapsed. Things got better when I found another person to fold my laundry when I was staying in hall!
Stack is efficient, minimal disturbance to the memory when data is inserted/deleted because only the top of the stack is modified. But when the 5th element of a 10element in a stack need to be retrieve, there is a lot of manual code needed for manipulation. Hence the efficiency and performance of the stack data structure is not satisfied.
So......what to do with the stack data structure? It can be used to store the dungeon level information. How many of you have played the game dungeons and dragons?? The assumption is that player can only go to 1 level above or 1 level below the current level of dungeon. Hence, using a stack to store is more sensible. Of course, a list can be used too. But... what are the consequences????
Have you wondered how the mouse in the micro-mouse competition know how to escape from the maze??? All movements of the mouse, eg forward, backward, left, right are stored onto the stack. When a dead end is encountered, the mouse will take a step back by simply pop off the top item on the stack. This is for navigation that requires a step back look left/right algorithm.
Other uses of stack, is in the operating system, where the system variable is stored. The stack is used to hold temporary variable of an executing program. Another stack is used to store the starting address of programs. What happens when the stack used to store variable is "overflow" ????
Drill question for the week,
1. Create a stack of 10 items.
2. retrieve the 5th item on the stack.
3. display the remaining item on the stack.
4. Modify week 4's decimal to binary conversion program and implement with stack.
4. Modify week 5's palindrome checking program and implement with stack.
Thursday, January 6, 2011
Monday, January 3, 2011
[DSA] Linked List
Linked List (LL)
Let assume today is your first day in school and your are appointed as the class rep. Most likely the first task you and need to do is to write down the names and contact information of your class mates.
But how are you going to do it??? Do you randomly scribble the information on some paper napkins and shoved it into your bag? Or write down the names and contact information one by one, in a list form? Or fired up your web browser and point to docs.google.com and start making a spreadsheet?
Let assume today is your first day in school and your are appointed as the class rep. Most likely the first task you and need to do is to write down the names and contact information of your class mates.
But how are you going to do it??? Do you randomly scribble the information on some paper napkins and shoved it into your bag? Or write down the names and contact information one by one, in a list form? Or fired up your web browser and point to docs.google.com and start making a spreadsheet?
The data you have entered is unsorted, so this tiny piece of paper/document serves as your lookup table when you need to retrieve some information. E.g your classmate's phone number
This week, we are going to explore the several api calls to use STL list to insert data, manipulate data and to retrieve data.
Say you want to find out your new classmate catherine for her phone number. How would you look for the information in the list? Most of us would look from top to bottom, some bottom to up, some start in the middle and traverse up or down. Inherently, you still lookup the information from the list one by one. All this methods to find her name doesn't really matter, because the list of information is unsorted, it will still take n+1 effort . The effort to lookup a name in the list gets bigger when the list grow longer and longer.
In the list of names you have,how would you input new names for student that just got into your class? Do you add it at the end of the list? Or simply insert the name to any position where the space permits?
All the above is the analogy for the Linked List used in the computer
Items that is stored in Linked List have to be travsersed sequentially. There are no random access iterators to access link list. Hence, you need to declare an iterator of the same data type that is used by the STL list container.
When you are designing the code and you needed data to be access randomly, Linked list is not the best option. Traversing the whole list of items takes time. The time required will grow accordingly to the size of the list. So, vectors or arrays are the best option (at the moment of learning). The items in vectors and arrays are placed side by side in memory world and can be access in a random fashion.
Items of a Linked List are not required to be placed side by side in the memory of the computer. How items are "linked" in a link list are done by the maintaiannce of the "header" pointer and the "tail" pointer. Pointers, as we have learned in the previous sessions, are variables that store the memory address of the items we are interested with. The tail pointer of the current items contains the address of the next item, ie. the value stored in the head poiter.
0->hP|DATA1|tP->hP|DATA2|tP->hP|DATA3|tP->0
Changing the values of the pointer variable requires only O(1) effort. Hence, the linked list is efficient when data/items are required to be inserted randomly in the list.
If the deletion of an item is required in the linked list. All need to be done is to modify the tail pointer of the current item, skipping the item we want to delete and points to the head pointer of the item next to the deleted item. In other words, we are merely copying the address in the tail pointer of the deleted item to the previous item's tail pointer. cool huh. No more holes left in the memory, no more statically declared memory that is left unsed, no more ugly algorithm to compact the array after a deletion of items.
All the above, are naked to the untrained eye. Users can't see the differences, only the programmer does.
DRill Questions:
1. create a list to store name of your classmates.
2. print out class list
3. "find" a particular person in the list. return found or not found.
4. Find out a method to attach the gpa score to the names in the list above.
hint: use class and OOP.
5. sort the list by gpa descending.
hint, try out stl algorithm
Sunday, January 2, 2011
New Year Resolution
It is once again, the same period of time to do some self reflection on what I have did in 2010 and what I want to achieve in 2011.
Remember my words?? I am only worth how much I promised.....
let's recall what I promised to do in 2010.
1. drop 2kg per month I did not lose weight, instead i gained weight. Please call me dot1tonner (for) now~
2. participate in standard charted marathon I did not run in standard charted marathon. Lazy duhzzz
3. eat KFC, every saturday and sunday dinner
4. eat Macdonalds, yessss!! almost everyday especially it is so convenient.It is right below my office!
5.go to the gym. erm, only step in once last year, the day before I do my annual med check up.
6.run 10km every saturday. nope was enjoying my beauty sleep till late evening.
the conclusion, I self pwned. None of my fitness goal is achieved.
As I mentioned last year
When it comes to setting goals, be very sure the goals set are "SMART"
S= Specific / Simplified / Strategic
M= Measurable / Manageable / Money ?!
A= Achievable / Attainable / Agarlogic?!
R= Realistic / Relevant
T= Timely / Track-able / Traceable
What is missing from the above, is the how to's to achieve your goal. More importantly, a schedule on what to do that you can follow closely to achieve your goal. Since i did not paste on my wall my workout schedule as big as loan shark ah long's, hence, nothing is tracked closely and finally nothing happened.
It is once again, the same period of time to do some self reflection on what I have did in 2010 and what I want to achieve in 2011
Now, lets do a flash back what I have done in 2010 (instead of the ones I did not do)......
1.spent many late nights in the labs (FYP, WSS). Checked. (Actually I lost count how many nights)
2.spent many Saturdays and Sunday in the office, lab. Checked. (I have access to 2x labs! 24x7 yeay~)
3.study for certification. Checked. 1x CCNA-S, 1x CCAI, 1x CCNP3, 1xCCNP2, failed 1xCCNP1
4.pickup new programming language. Checked. Android, Arduino and Processing.(In the process I mentored 2x group for android competition)
5.deliver 1x segway like robot for student FYP. Checked. Delivered 4x instead, with different variations. FYP roxxxx~! It is fun to be part of the action. The anger, the sorrow, the mourning, the delight and the adrenalin rush. It was a roller coaster ride, I hope you guys that rode with me enjoyed the process and learn how to manage tech, people and team work. This item drawn most of my energy, but it is worth every single Joules!
6.coach trainees for final round. Checked. They got 1x GOLD medal in the process of preparation. It is very hard to manage disappointment, because not all manage to get through. But, I have to move on instead of swimming in alcohol to pacify the sorrows.
7.Annual leave of 56days. Checked. I am still finding ways to use them... duhzzzz
8.receive a medal of some sort. Checked. I got the Commendation award for E-learning in EETC10
9.look out for postgrad / phd lobang. Checked. None came to my favour. It is hard on me, especially got rejected twice in a row. The feeling is worst then getting rejected by my first love(let's assume I had one).
10. Treat myself nicely?? LOL...I just had to make it a 10, since it is for 2010.
nonetheless, I applied SMART goal method to achieve it. You can do it too!
I have been especially harsh on me in my own capacity and this "aura" of my RDF (Reality Distortion Field) affects the boys and girls that worked for me directly. They draw the flak most of the time and yet they survived it. It was unintentional, BUT I really want you people to buck up and start to prioritized the designated task upon others.
Now, my 2011 goals which I am going to use the SMART goal method to align it.
1. only eat 1x meat and 2x vegetables for lunch EVERYDAY
2. only eat KFC (and only 1pcs of original breast meat) for dinner once per week.
3. say NO to macdonalds extra value meal with upsize. (only 1 double cheese burger per week)
4. burn 600cal every wednesday in the gym.
5. use my 56days annual leave
Remember my words?? I am only worth how much I promised.....
let's recall what I promised to do in 2010.
3. eat KFC,
4. eat Macdonalds, yessss!! almost everyday especially it is so convenient.It is right below my office!
5.
6.
the conclusion, I self pwned. None of my fitness goal is achieved.
As I mentioned last year
When it comes to setting goals, be very sure the goals set are "SMART"
S= Specific / Simplified / Strategic
M= Measurable / Manageable / Money ?!
A= Achievable / Attainable / Agarlogic?!
R= Realistic / Relevant
T= Timely / Track-able / Traceable
What is missing from the above, is the how to's to achieve your goal. More importantly, a schedule on what to do that you can follow closely to achieve your goal. Since i did not paste on my wall my workout schedule as big as loan shark ah long's, hence, nothing is tracked closely and finally nothing happened.
It is once again, the same period of time to do some self reflection on what I have did in 2010 and what I want to achieve in 2011
Now, lets do a flash back what I have done in 2010 (instead of the ones I did not do)......
1.
2.
3.
4.
5.
6.
7.
8.
9.
10. Treat myself nicely?? LOL...I just had to make it a 10, since it is for 2010.
nonetheless, I applied SMART goal method to achieve it. You can do it too!
I have been especially harsh on me in my own capacity and this "aura" of my RDF (Reality Distortion Field) affects the boys and girls that worked for me directly. They draw the flak most of the time and yet they survived it. It was unintentional, BUT I really want you people to buck up and start to prioritized the designated task upon others.
Now, my 2011 goals which I am going to use the SMART goal method to align it.
1. only eat 1x meat and 2x vegetables for lunch EVERYDAY
2. only eat KFC (and only 1pcs of original breast meat) for dinner once per week.
3. say NO to macdonalds extra value meal with upsize. (only 1 double cheese burger per week)
4. burn 600cal every wednesday in the gym.
5. use my 56days annual leave
Subscribe to:
Posts (Atom)