## Saturday, August 29, 2009

### Rolling a Six-Sided Die 6000 Times (Java Coding)

Posted by Han at 3:18 AM 2 comments

## Saturday, May 16, 2009

### Algorithms & Data Structures - Searching

Searching

√The process used to find the location of a target among the list of object.

√We begin with list searching and a discussion of two basic search algorithm

List Searches

√The two basic searches for arrays are the sequential search and the binary search.

Sequential Search

√The sequencial search is used whenever the list is not ordered.

√It is useful for small lists or lists that are not searched often.

√In sequential search, we start searching for the target at the beginning of the list and continue until we find the target or we are sure that it is not in the list.

√The efficiency of sequential search is O(n).

Binary Search

√The binary search starts by testing the data in the element at the middle of the array to determine if the target is in the first or the second half of the list.

√If it is in the first half, we do not need to check the second half.

√If it is in the second half, we do not need to check the first half.

√To find the middle of the list, we need 3 variables: one to identify the beginning of the list, one to identify the middle of the list and one to identify the end of the list.

√The formula to calculate the mid is:

Mid = [(begin + end ) / 2 ]

√The efficiency of the binary search is O(log n).

Binary Search Tree

√The array structure provides a very efficient search algorithm, but its insertion and deletion algorithms are very inefficient.

√The binary search tree and AVL tree (chapter 3)provides a very efficient search and at the same time efficient insertion and deletion algorithm.

Basic Concepts

A binary search tree is a binary tree with the following properties:

√All items in the left subtree are less than the root.

√All items in the right subtree are greater than or equal to the root.

√Each subtree is itself a binary search tree.

Posted by Han at 6:45 AM 0 comments

### Algorithms & Data Structures - Sorting

**Objective:**

At the end of the class you should be in a position to answer:

√Understand the basic concepts of internal and external sorts

√Discuss the relative efficiency of different sorts

√Recognize and discuss selection, insertion and exchange sorts

√Discuss the design and operation of external sorts

√Design and implement sequential searches

√Discuss the relative merits of different sequential searches

√Design and implement binary searches**Sort Concepts**

√Sorts arrange data according to their value.

√Sorting algorithm are classified as either internal or external.**Insertion Sorts**

In each pass of an insertion sort, one or more pieces of data are inserted into their correct location in an ordered list. In this section we study two insertion sorts: the straight insertion sort and the shell sort.**Explanation**

In a straight insertion sort, the list at any moment is divided into sorted and unsorted sublists. In each pass the first element of the unsorted sublist is inserted into the sorted sublist.

If we have a list of n elements, it will take at most n-1 passes to sort the data.

The straight selection sort efficiency is O(n^{2})**Shell Sort**

The shell sort algorithm named after its creator, Donald L.Shell.

It is an improved version of the straight insertion sort in which diminishing partitions are used to sort the data.

The Worst case running time of shell sort using shell’s increment is O(N^{2}).**Selection Sort**

In each pass of the selection sort, the smallest element is selected from the unsorted sublist and exchanged with the element at the beginning of the unsorted list.

The straight selection sort efficiency is O(n^{2})**Bubble Sort**

Bubble sort is an exchange sort. The basic operation is the exchange of an adjacent pair of elements. So in the single bubble sort algorithm, the program will pass through the data, switching consecutive items which are out of order. After each pass through the list, the program checks to see if any switches were made. If there were, it passes through the list again, switching consecutive items which are still out of order. If no switches are made during an entire pass through the list, the data is sorted.

In the best case the efficiency of bubble sort is O(N).

In the worst case the efficiency of bubble sort is O(NM^{2})**Example of Bubble sort**

Here is an example : we want to sort 390, 205, 182, 45, 235

Bubble sort for the first pass (exchange of an adjacent pairs)__390__ 205 182 45 235 (Switch 1)

205 __390__ 182 45 235 (Switch 2)

205 182 __390__ 45 235 (Switch 3)

205 182 45 __390__ 235 (Switch 4)

205 182 45 235 __390__ ( First pass-sorted list)

the first pass moves the largest element (390) to the n^{th} position ,forming a sorted list of length one

the second pass only has to consider (n-1) elements and moves the second largest element to the (n-1) position. **Quick Sort**

Quick sort is an exchange sort in which a pivot key is placed in its correct position in the array while rearranging other elements widely dispersed across the list.

The efficiemcy of the Quick sort is :

Worst Case = O(N^{2}) - the pivot is the smallest element

Average Case = O(N log n)

Best case = O(N log N) - the pivot is in the middle**Radix Sort**

The bin sorting approach can be generalized in a technique that is known as radix sorting.

Assume that we have n integers in the range (0,n^{2}) to be sorted. (For a bin sort, m = n^{2}, and we would have an O(n+m) = O(n^{2}) algorithm.) Sort them in two phases:

1. Using n bins, place a_{i} into bin a_{i} mod n,

2. Repeat the process using n bins, placing a_{i} into bin floor(a_{i}/n), being careful to append to the end of each bin.

This results in a sorted list.**Example**

Consider the list of integers

36 9 0 25 1 49 64 16 81 4

Step1: Arrange the element according to the least significant decimal digits

Step2:Arrange the elements according to the most significant digits

Step3: Sorted list is :

0 1 4 9 16 25 36 49 64 81**Merge Sort**

The basic merging algorithm takes two input arrays A and B, an output array C, and three counters, Aptr, Bptr, and Cptr, which are initially set to the beginning of their respective arrays. The smaller of A[Aptr] and B[Bptr] is copied to the next entry in C, and the appropriate counters are advanced. When either input list is exhausted, the remainder of the order list is copied to C.

Example

If the array A (Aptr) contains 1, 13 and B (Bptr) contains 2, 15, 27, 38, then the algorithm proceeds as follows.

First, a comparison is done between 1 and 2.

1 is added to C, and then 13 and 2 are compared.

2 is added in C, and 13 and 15 are compared.

The remainder of the array B is then copied to C.

Posted by Han at 5:34 AM 1 comments

## Friday, February 27, 2009

### Algorithms & Data Structures - Queue

**Definition**

- Queue is an ordered collection of items.
- These items may be deleted at one end (called the HEAD of the queue) and inserted at other end (called the TAIL of the queue).
- Example, to withdraw money at ATM
- Also known as FIFO – first in first out

**Array and linked list implementation**

**Operations of Queue**

- Dequeue
- Enqueue
- QueueEmpty
- QueueFull

**Enqueue**

- Enqueue is the shortened version of "entering a queue".
- It refers to a situation where a new item is inserted to the queue.
- After a new insertion is made, the new item becomes the tail of the queue.

**Dequeue**

- Dequeue is a shortened version of "deleting from a queue".
- This is a situation where the data element at the head of the queue will be deleted.

**Array implementation**

- Using array to implement the queue
- Will create a problem when the queue is full – memory space are fixed.

**Problem solution**

- Create a circular queue. (using linked list)
- Circular queue wraps around to the beginning whenever the Head or the Tail reaches the end of the queue.

**Linked list implementation**

* Enqueue

**Enqueue- Implementation**

void Enqueue(QUEUENODEPTR *tailPtr, QUEUENODEPTR *headPtr, char Value)

{

QUEUENODEPTR newPtr;

newPtr = malloc(sizeof(LISTNODE)); //Create a new node

if (newPtr != NULL)

{

newPtr->data = Value;

newPtr->nextPtr = NULL;

(*tailPtr)->nextPtr = newPtr;

(*tailPtr) = (*tailPtr)->nextPtr;

if (*headPtr == NULL)

*headPtr = *tailPtr;

}

**Dequeue - Implementation**

char Dequeue(QUEUENODEPTR *headPtr)

{

char value;

QUEUENODEPTR tempPtr;

if (*headPtr != NULL)

{

tempPtr = *headPtr;

(*headPtr) = (*headPtr)->nextPtr;

value = tempPtr->data;

free(tempPtr);

return value;

{

else

printf(“Queue is empty”);

}

**Application of queue**

- Scheduling system
- Advantages

- Support print spooling
- Information packet

Posted by Han at 3:47 PM 0 comments

## Saturday, December 20, 2008

### Linked List Based Implementation of Stack and Queue

Why different implementations

- The way the data structure is implemented is a measure of its efficiency (time and space)
- It is important to see different alternatives
- So far we have discussed array based implementation (vector). What if we use second class arrays?

Objectives:

Discuss linked list based implementation of stack and queue.

Compare and contrast two implementations

Linked List based Stack

- Stack is LIFO data structure
- Linked list is a collection of nodes where each node has a data element and a pointer to the next element in the list.

Linked List based Stack- basic concepts

- Stack we push into and pop from the top of the stack.
- Therefore a special pointer “toOftheStack” which is pointing to the top of the stack is created.
- Intially toOftheStack is null.
- Try following operations
- push (a), push(b), push(c)
- pop()

Linked List based Stack- C++ Details

__A Node: (figure 16.19)__

struct ListNode

{

Object element;

ListNode *next;

ListNode ( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n ) { }

};

Linked List based Stack- C++ Details

Template

template <class Object> class Stack {

public:

Stack( );

Stack( const Stack & rhs );

~Stack( ); bool isEmpty( ) const;

const Object & top( ) const;

void makeEmpty( );

void pop( );

void push( const Object & x );

Object topAndPop( );

const Stack & operator=( const Stack & rhs );

private:

struct ListNode { Object element; ListNode *next; ListNode( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n ) { } };

ListNode *topOfStack; };

Linked List based Stack- C++ Details

Implementation

push, pop, top, makeEmpty and = operator

Linked List based Queue

- Queue if FIFO data structure
- Implementation is very similar to stack. Here, both from and back of the data structure need pointers.

Linked List based Queue- basic concepts

- Queue, enqueue into the front of the stack. Dequeue from the back of the stack
- Therefore two special pointers “front,” and “back,” are created.
- Initially both both front and back are null.
- Try following operations
- enqueue (a), enqueue(b), enqueue(c)
- dequeue()

Linked List based Queue - C++ Details

A Node:

struct ListNode {

Object element;

ListNode *next;

ListNode( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n )

{ }

};

Linked List based Queue - C++ Details

Template

Notice that there are two pointers, front and back

Linked List based Queue - C++ Details

Implementation

Enqueue, dequeue, copy constructure and = operator

Array base vs. Linked list based Implementation

- For large size stacks and queue specially the size is not known linked list is better.
- For memory scare devices such as small handheld devices, linked list may perform better.

Posted by Han at 11:46 PM 2 comments

### Algorithms & Data Structures - Linked List

**Objectives**__At the end of the class you should be able to answer:__

**Basic Operations**

__The four basic list operations are :__

- Insertion
- Deletion
- Retrieval
- Traversal

**Insertion**

- Insertion is used to add a new element to the list.
- List insertion can be ordered or random.
- Ordered list are maintained in sequence according to the data or, when available, a key that identifies the data.
- In random lists there is no sequential relationship between two elements.Random lists are sometimes called chronological lists.

**Figure 5-1 Shows the insertion of data into a list**

**Deletion**

- Deletion is used to remove an element from the list.
- Deletion from a list requires that the list be searched to locate the data being deleted
- Once located, the data are removed from the list.

Figure 5-2 Shows the Deletion operation

**Retrieval**

- Retrieval is used to get the information related to an element without changing the structure of the list.
- List retrieval requires that data be located in a list and presented to the calling module without changing the contents of the list.

Figure 5-3 Shows retrieving data from a list

**Traversal**

- List traversal processes each element in a list in sequence
- It requires a looping algorithm rather than a search.

**Implementation**

- Several data structures can be used to implement a list; we use a linked list.
- Linked list is a good structure for a list because data are easily inserted and deleted at the beginning, in the middle, or at the end of the list.

**Data Structure**

To implement a list, we need two different structures, a head node and data node.

**Figure 5-5 Shows a head node and data node**

**Algorithm**

Create List:

Create list allocate the head structure and initializes the metadata for the list.

Figure 5-6 shows the header before and after it is initialized by create list.

**Figure 5-6 Create list**

**Algorithm for creating a list**

**Insert Node**

Insert node adds data to a list. Given the predecessor, there are three steps to the insertion:

1. Allocate memory for the new node and move data to the node.

2. Point the new node to its successor.

3. Point the new node’s predecessor to the new node.

**Figure 5-7 Add node to empty list**

**Insert at Beginning**

- To insert a node at the beginning of the list, we simply point the new node to the first node of the list and then ser the head pointer to point to the new first node.
- Figure 5-8 shows inserting a node at the beginning

Figure 5-8 Shows Add node at Beginning

**Insert in Middle**

- To insert a node between two nodes, we point the new node to its successor and then point its predecessor to the new node.
- Figure 5-9 shows inserting a node in the middle.

Figure 5-9 Add node in Middle

**Insert at End**

- To add at the end of the list, we only need to point the predessor to the new node.
- The Figure5-10 insert the node at the end

**Figure 5-10 Add node at End**

**Algorithm for Insertion is shown in figure 5-2**

**Delete Node**

- The delete node algorithm logically removes a node from the list by changing various link pointers and then physically delete the node from dynamic memory.
- Figure 5-11 shows Deleting the first node

**Delete First Node**

**Algorithm for Deleting a node**

**Retrieve Node**

Figure 5-5 Shows retrieve list node algorithm

**Advance Linked List**

- Circular Linked List
- Circular linked list is a type of linked list where the last node will point back to the first node

**Graphical view of a circular linked list**

Posted by Han at 10:50 PM 0 comments