Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Data Structure and Algorithms - Queue
An abstract data structure like Stacks is queue
...
The act of adding data to one end
and deleting it from the other is known as enqueuing (dequeue)
...


A useful example of a queue is a single-lane, one-way road where
cars enter and depart first
...

Queue Representation
As we now understand that in queue, we access both ends for
different reasons
...
To keep things simple, we'll
establish queues using a one-dimensional array
...
Here,
we'll try to comprehend the fundamental operations related to
queues −
•
•

enqueue() − add (store) an item to the queue
...


Few more functions are required to make the above-mentioned
queue operation efficient
...

isfull() − Checks if the queue is full
...


In queue, we always dequeue (or access) data, pointed
by front pointer and while enqueing (or storing) data in the
queue we take help of rear pointer
...
The
algorithm of peek() function is as follows −
Algorithm
begin procedure peek
return queue[front]
end procedure
Implementation of peek() function in C programming language −

Example
int peek() {
return queue[front];
}
isfull()
As we are using single dimension array to implement queue, we
just check for the rear pointer to reach at MAXSIZE to determine
that the queue is full
...
Algorithm of isfull() function
−
Algorithm
begin procedure isfull
if rear equals to MAXSIZE
return true
else
return false
endif
end procedure
Implementation of isfull() function in C programming language −
Example
bool isfull() {
if(rear == MAXSIZE - 1)
return true;
else

return false;
}
isempty()
Algorithm of isempty() function −
Algorithm
begin procedure isempty
if front is less than MIN OR front is greater than rear
return true
else
return false
endif
end procedure
If the value of front is less than MIN or 0, it tells that the queue
is not yet initialized, hence empty
...
Therefore,
its operations are comparatively difficult to implement than that
of stacks
...

Step 2 − If the queue is full, produce overflow error and
exit
...

Step 4 − Add data element to the queue location,
where the rear is pointing
...


Sometimes, we also check to see if a queue is initialized or not,
to handle any unforeseen situations
...

The
following
perform dequeue operation −
•
•

•

•

•

steps

are

taken

to

Step 1 − Check if the queue is empty
...

Step 3 − If the queue is not empty, access the data
where front is pointing
...

Step 5 − Return success
...
In this type of
search, a sequential search is made over all items one by one
...


Algorithm
Linear Search ( Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit
Pseudocode
procedure linear_search (list, value)
for each item in the list
if match item == value
return the item's location
end if
end for
end procedure

Data Structure and Algorithms Binary Search
A quick search algorithm with run-time complexity of O is binary
search (log n)
...
The data collection must be in
sorted form for this algorithm to function correctly
...
If a match occurs, then the index of item
is returned
...
If not,
the sub-array to the right of the middle item is searched for the
item
...

How Binary Search Works?
The target array must be sorted in order for a binary search to
function
...
Here is our sorted array, and let's imagine that we
need to use binary search to locate the value 31
...
5)
...


Now we compare the value stored at location 4, with the value
being searched, i
...
31
...
As the value is greater than 27 and we have
a sorted array, so we also know that the target value must be in
the upper portion of the array
...

low = mid + 1
mid = low + (high - low) / 2
Our new mid is 7 now
...


The value stored at location 7 is not a match, rather it is more
than what we are looking for
...


Hence, we calculate the mid again
...


We compare the value stored at location 5 with our target value
...


We conclude that the target value 31 is stored at location 5
...

Pseudocode
The pseudocode of binary search algorithms should look like this
−
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists
...
This
search algorithm works on the probing position of the required
value
...

Binary search has a huge advantage of time complexity over
linear search
...

There are cases where the location of target data may be known
in advance
...
Here, linear
search and even binary search will seem slow as we can directly
jump to memory space where the names start from 'M' are
stored
...
The search is
carried out in either of them
...

Position Probing in Interpolation Search
Interpolation search finds a particular item by computing the
probe position
...


If a match occurs, then the index of the item is returned
...
Otherwise, the item is searched in the subarray to
the left of the middle item
...

Runtime complexity of interpolation search algorithm is Ο(log
(log n)) as compared to Ο(log n) of BST in favorable situations
...

Step 2 − If it is a match, return the index of the item, and exit
...

Step 4 − Divide the list using probing formula and find the new
midle
...

Step 6 − If data is smaller than middle, search in lower sub-list
...


Pseudocode
A → Array list
N → Size of A
X → Target Value
Procedure Interpolation_Search()
Set Lo → 0
Set Mid → -1
Set Hi → N-1
While X does not match
if Lo equals to Hi OR A[Lo] equals to A[Hi]
EXIT: Failure, Target not found
end if
Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])
if A[Mid] = X
EXIT: Success, Target found at Mid
else
if A[Mid] < X
Set Lo to Mid+1
else if A[Mid] > X
Set Hi to Mid-1
end if
end if
End While

End Procedure
Data Structure and Algorithms - Hash Table
Hash Table is a data structure which stores data in an associative
manner
...
Access of data
becomes very fast if we know the index of the desired data
...
Hash
Table uses an array as a storage medium and uses hash
technique to generate an index where an element is to be
inserted or is to be located from
...
We're going to use modulo operator
to get a range of key values
...
Item are in
the (key,value) format
...
No
...
In such a case, we
can search the next empty location in the array by looking into
the next cell until we find an empty cell
...

Sr
...
Key

Hash

Array
Index

After Linear Probing,
Array Index

1

1

1 % 20 = 1

1

1

2

2

2 % 20 = 2

2

2

3

42 42 % 20 = 2

2

3

4

4

4 % 20 = 4

4

4

5

12

12 % 20 =
12

12

12

6

14

14 % 20 =
14

14

14

7

17

17 % 20 =
17

17

17

8

13

13 % 20 =
13

13

13

9

37

37 % 20 =
17

17

18

Basic Operations
Following are the basic primary operations of a hash table
...

Insert − inserts an element in a hash table
...


DataItem
Define a data item having some data and key, based on which
the search is to be conducted in a hash table
...

int hashCode(int key){
return key % SIZE;
}

Search Operation
Whenever an element is to be searched, compute the hash code
of the key passed and locate the element using that hash code
as index in the array
...

Example
struct DataItem *search(int key) {
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] != NULL) {
if(hashArray[hashIndex]->key == key)
return hashArray[hashIndex];
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
return NULL;
}
Insert Operation
Whenever an element is to be inserted, compute the hash code
of the key passed and locate the index using that hash code as

an index in the array
...

Example
void insert(int key,int data) {
struct DataItem *item = (struct DataItem*)
malloc(sizeof(struct DataItem));
item->data = data;
item->key = key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty or deleted cell
while(hashArray[hashIndex] != NULL &&
hashArray[hashIndex]->key != -1) {
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
hashArray[hashIndex] = item;
}
Delete Operation
Whenever an element is to be deleted, compute the hash code
of the key passed and locate the index using that hash code as
an index in the array
...

When found, store a dummy item there to keep the
performance of the hash table intact

---