Data Structures - For my Ninth Grader – Part 1

In Computer science two concepts forms foundation: Data Structures and Algorithms. Let us discuss few important data structures in this post.

Queue: Have you ever stand in a line (for USA persons)/ queue (for British) for any service like in post office, bank, airport, bus stand, railway station, theater, etc. If answer is YES, then you have experienced a queue first hand. Queue can be assumed as linear collection of items/elements in which they enter from one end and leave from another. The pictorial representation of queue:

 Now, what operations one can do with a queue

1.      Enter an item/element in the queue from one end (rear) >>> enqueue

2.      Take out an item/element from the queue from another end (front) >>> dequeue

3.      Look into last item/element in the queue at front (without removing from queue)>>> peek

4.      Clear the contents of the queue >>> clear

5.      Find out, if queue has any item/element >>> isEmpty

6.      Find out how items/elements in the queue >>> size

Queue is ordered (items/elements succeeding in order of enqueue) collection of items in which items enter from rear and exit from front - one by one. As an item/element enters the queue it starts at the rear and makes its way toward the front, as items/elements ahead of it get removed one by one.

Queue is follows FIFO (first in first out).

Stack: Make a pile of books placed one on top of another. You have stack.

 One can remove or add book at the top of the stack. The pictorial representation of stack:

  One can do following operations on a stack:

1. Add an item/element at top of stack >>> push
2. Remove an item/element from top of stack >>> pop
3. Find out, if stack has any item/element >>> isEmpty
4. Find out how items/elements in the stack >>> size
5. Look into top item/element in the stack (without removing from stack) >>> peek

Stack is ordered (items/elements succeeding in order of push) collection of items in which items enter from rear and exit from top only.

Stack is follows LIFO (last in first out). 

Deque (pronounced “deck”): Deque is double ended queue. In deque one can add item/element from rear as well as front. Similarly one can remove items/elements from both front and rear. The pictorial representation:   

One can do following operations on a deque:

1.    Add an item/element at front >>> addFront
2.    Add an item/element at rear >>> addRear
3.    Remove an item/element from front >>> removeFront
4.    Remove an item/element from rear >>> removeRear
5.    Find out, if deque has any item/element >>> isEmpty
6.    Find out how items/elements in the deque >>> size
7.    Look into last item/element in the queue at front (without removing from queue) >>> peek

Deque is ordered (items/elements succeeding in order of adding) collection of items in which items can enter from both ends (front and rear).

Deque is hybrid of Queue and Stack.

Dependency Injection: For my Ninth Grader

Homestead High’s Astronomy Club has planned to arrange a visit to Foothill Observatory. So each student was asked to reach observatory at 9.00 AM on following Saturday. Everyone agreed. On Saturday, only quarter of the club members made to the observatory.

Club’s presiding officers were surprised that why only few students made to the observatory despite being so close to school. They decided to find out the reason, so future visits can have more participation. After talking to club members following reasons were listed for low attendance:

1. Non availability of public transport near observatory
2. Parents were busy somewhere else so no ride was available
3. Lack of coordination among students, so ride share was not common
4. …
5. ….
6. …

After few months, Club proposed to visit observatory again. But to avoid previous mistake, this time Club Officers arranged transport from School to observatory and back. Attendance rose to almost 100%.

If you notice in both scenarios only one thing has changed but results were drastically different. What was the change!!

In first scenario, each student was supposed to arrange his transport and in second scenario club officers had responsibility to arrange transport.

In second scenario students were dependent on club officers. It was up to club officers to arrange transport from First Student Charter or US Coachways any other transport company. It was possible that club officers might have arranged one bus from First Student Charter and second from US Coachways. In general students were dependent upon club officers for transport so have more time and energy to focus on learning.

This is Dependency Injection (DI).

XML: For my Ninth Grader - Part 2

XML: For my Ninth Grader - Part1



But any real book has a name, author name, text under each element, chapter name, and section name. This information is still not represented anywhere. Let us try to represent this information.

  

If you notice in pictogram, few of the additional information added can be represented better if that gets its own box. For example, in Book --> Front Matter --> Forward, Content need to be broken into Paragraphs and each Paragraph should have its own box.

Lets’ redraw the book picture again with additional understanding.
 

If you notice, few of the things from boxes of previous picture are moved into new boxes while some are remaining inside the original box. For example in forward box, heading remains inside the box while paragraph has moved out.  

This decision is arbitrary and left to the designer of the XML. I have chosen to follow a simple rule. Something which is small will remain the box and something which is big enough, should move out and acquire its own box.

Now let us assume a book which is very simple (so it does not have most the optional elements). So my book’s structure is:

Now let us represent this picture in the form of the text.

 

 

This textual representation is XML.

Reference:

http://en.wikipedia.org/wiki/Book_design