[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.

[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.

SPINNOVEX 2011

we are featured on the channel 8 news (1:05 to 1:40)~~~

35sec of precious air time~

[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? 

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

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