Centre for Distance & Online Education

INTERNAL ASSIGNMENT

SET-I

Q1. What are the characteristics and Building Blocks of an Algorithm? And what are
Control Mechanism and Control structures?

The five important characteristics of an algorithm are:

1. Finiteness: An algorithm must terminate after a finite number of steps and further each step
must be executable in finite amount of time.
2. Definiteness: (no ambiguity) Each step of an algorithm must be precisely defined; the
action to be carried out must be rigorously and unambiguously specified for each case.
3. Inputs: An algorithm has zero or more but only finite, number of inputs. An examples of
algorithm requiring zero inputs is Print the largest integer, say MAX, representable in the
computer system being used.
4. Outputs An algorithm has one or more outputs. The requirement of at least one output is
obviously essential. The outputs have specific relation to the inputs, where the relation is by
the algorithm.
5. Effectiveness An algorithm should be effective. This means that each of the operations to
be performed in an algorithm must be sufficiently basic that it can, in principle, be done
exactly and in a finite length of time, by a person using pencil and paper.

The building blocks of algorithm are:

i) Assignment of a value to a variable is denoted by Variable  expression;
Where the expression is composed from variable and constant operands using familiar
operators like +, –, * etc. Assignment action includes evaluation of the expression on the
R.H.S. An example of assignment instruction/ statement is
j  2 * i + j – r.
ii) The next basic action is read values of variables i, j, etc. from some secondary storage
device, the identity of which is (implicitly) assumed here, by a statement of the form read (i j,
); The values corresponding to variables i, j, ... in the read statement, are, due to read
statement, stored in the corresponding locations loc (i), loc(j) ...., in the main memory.
iii) The last of the three basic actions is to deliver/ write values of some variables say i, j etc.
to the monitor or to an external secondary storage by a statement of the form
Write (i, j,….);
The three basic control mechanisms or structuring rules are:
i) Direct sequencing: When the sequence of execution of instructions is to be the same as the
sequence in which instruction are written in program text, the control mechanism is called
direct sequencing.
ii) Selection: In many situations, we intend to carry out some action A if condition Q is
satisfied and some other action B if condition Q is not satisfied. This intention can be denoted
by If Q then do A else do B, Where A and B are instructions, which may be even composite
instructions obtained by applying these structuring rules recursively to the other instructions.

Page 1 of 11 Mail id: helpdesk@mujonline.edu.in

Phone: +91 79966 00444 (Toll
Free)
 Centre for Distance & Online Education
(iii) Repetition: Iterative repetitive execution of a sequence of actions is the basis of
expressing long processes by comparatively small number of instructions. The repeated
execution of the sequence of actions has to be terminated. The termination may be achieved
either through some condition Q or by stating in advance the number of times the sequence is
intended to be executed.

Q2. A. What are Binary trees? How many types of Binary trees are there, discuss?

A binary tree is characterized by the fact that any node can have at most two branches, i.e.,
there is no node with degree greater than two.
Definition: A binary tree is a special case of tree where no node of a tree can have a degree of
more than two. Therefore, a binary tree is a set of zero or more nodes T such that: i) there is a
specially designated node called the root of the tree ii) the remaining nodes are partitioned
into two disjointed sets, T1 and T2, each of which is a binary tree. T1 is called the left subtree
and T2 is called right subtree.
There are 3 types of binary trees:

1) Skewed binary tree

2) Full binary tree
3) Complete binary tree
Skewed binary tree: A binary tree which has only left subtree is called left skewed tree and
has only right subtree is called right skewed tree. Skewed trees are not efficient in memory
management because generally, an n node binary tree needs an array whose length is between
n+1 and 2n, but while storing skewed binary tree it wastes most of the memory space.

Full binary tree: A binary tree is a full binary tree if and only if :-
o Each non leaf node has exactly two child nodes
o All leaf nodes are at the same level

Complete binary tree A complete binary tree is a binary tree in which every level, except
possibly the last, is completely filled, and all nodes are as far left as possible. Complete
binary tree from left to right A complete binary tree of depth k is a tree with n nodes in which
these n nodes can be numbered sequentially from 1 to n, as if it would have been the first n
nodes in a full binary tree of depth k.

B. Discuss the linked storage representation of binary tree.

The most popular way to present a binary tree is Linked storage representation. Binary tree
consists of nodes which can have at most two child, linked representation of such tree will be
stored in the form shown below, where LPTR and RPTR denote the address or locations of
the left and right subtrees respectively of a particular root node.

Page 2 of 11 Mail id: helpdesk@mujonline.edu.in

Phone: +91 79966 00444 (Toll
Free)
 Centre for Distance & Online Education
Empty subtrees are represented with NULL. DATA specifies the information associated with
the node. The space required by an n node binary tree is n * size of (binaryTreeNode)
Figure below contains an example of linked storage representation of binary tree. Linked
representation of binary tree is considered as dynamic in nature as the block of memory
required for the tree can be allocated on demand.

Binary Tree Linked List Representation

Advantages of linked representation of binary tree 1) Utilization of memory is efficient. 2)

Enhancement of tree is possible in this representation. 3) Insertion and deletion of nodes can
be easily handled with the pointers without data movement
Disadvantages of linked representation of tree
1) It is difficult to implement with the language which does not support the dynamic
allocation of memory.
2) Since pointer is involved for data reference it occupies more memory.

Q3. Explain the algorithms of Bubble sort and Merge sort.

Bubble sort is a straightforward and simplistic method of sorting data that is used very
commonly. It compares the first two elements, and if the first is greater than the second, then
it swaps them. It continues doing this for each pair of adjacent elements to the end of the data
set. It then starts again with the first two elements, repeating until no swaps have occurred on
the last pass. This algorithm is highly inefficient, and is rarely used except as a simplistic
example. For example, if only one element is not in order, bubble sort will only take 2n time.
If two elements are not in order, bubble sort will only take at most 3n time. Bubble sort
average case and worst case are both O(n²).

Page 3 of 11 Mail id: helpdesk@mujonline.edu.in

Phone: +91 79966 00444 (Toll
Free)
 Centre for Distance & Online Education
Procedure: BUBBLE_SORT (K,N). Given vector K and N elements this procedure sorts the
elements into ascending order using the method just described. The variables PASS and
LAST denote the pass counter and position of the last unsorted element, respectively.
Variable I is used as index of vector elements variable EXCHS is used to count the number of
exchanges.
1. [Initialize ] LAST N (entire list is unsorted at this point)
2. [Loop on pass index]
Repeat thru step 5 for PASS = 1, 2, ... N-1
3. [initialize exchanges counter for this pass] EXCHS 0
4. [perform pairwise comparisons on unsorted elements]
Repeat for 1 = 1, 2, ... LAST-1
If K[1] > K[I+1]
then K[I] K[I+1]
EXCHS EXCHS +1
5. [were any exchanges made on this pass]
If EXCHS=0
then Return
else LAST LAST-1
6. [Finished]
Return (maximum number of passes required).

Before each pass, the interchange marker EXCHS is initialized to zero. This marker is
incremented each time an interchange is made. If, at the end of a pass, EXCHS has a value of
zero, the sort is complete
Merge sort:
Divide-and conquer is a general algorithm design paradigm: Divide: divide the input data S
in two disjoint subsets S1and S2
Recur: solve the sub problems associated with S1 and S2
Conquer: combine the solutions for S1 and S2 into a solution for S
The base case for the recursion is sub problems of size 0 or 1 Merge-sort on an input
sequence S with n elements consists of three steps:
Divide: partition S into two sequences S1 and S2 of about n/2 elements each
Recur: recursively sort S1 and S2
Conquer: merge S1 and S2 into a unique sorted sequence.
Merge sort algorithm proceeds as follows:
1) Divide the array with the size of m as middle= m/2.
2) Update left from 1 to middle.
3) Update right from middle+1 to m
4) Repeat 1 to 3 until m≤1 5)
Call merge [left, right].

merge_sort[m]
if length[m] ≤ 1
return m
middle length[m] / 2
for x 1 to middle
add x to left

Page 4 of 11 Mail id: helpdesk@mujonline.edu.in

Phone: +91 79966 00444 (Toll
Free)
 Centre for Distance & Online Education
for x middle to m
add x to right
left merge_sort[left]
right merge_sort[right]
result merge[left, right]
return result
merge[left, right]
while length[left] > 0 or length[right] > 0
if length[left] > 0 and length[right] > 0
if first[left] ≤ first[right]
append first[left] to result
left rest[left]
else
append first[right] to result
right rest[right]
else if length[left] > 0
append first[left] to result
left rest[left]
else if length[right] > 0
append first[right] to result
right rest[right]
end while
return result

SET-II

Q4. A. What is dynamic memory storage and how is link list stored in memory? Write
the algorithm for traversal of a singly link list.

Dynamic Memory Storage

Page 5 of 11 Mail id: helpdesk@mujonline.edu.in

Phone: +91 79966 00444 (Toll
Free)
 Centre for Distance & Online Education
In computer programming, dynamic memory allocation refers to the technique of allocating
memory for variables and data structures during program execution (runtime) instead of at
compile time. This provides flexibility when dealing with data of unknown size beforehand.

There are two main memory regions used for dynamic allocation:

 Heap: A more flexible memory pool that can grow or shrink as needed during
program execution. It's typically used for dynamically allocated data structures like
linked lists and trees.
 Stack: A faster memory region with a fixed size, often used for local variables within
functions. The size of data on the stack is known at compile time.

Linked list is a linear collection of data elements called nodes. Each node is divided into two
parts: the first part is called data field where the data are stored and the second part is called
the link field or next field, contains the address of the next node in the list.
If we represent linked lists in memory it requires two arrays one store the data part and one
for the address part such that DATA [K] and LINK [K] respectively. It also requires a
variable name START which contains the address of the first node and a next pointer sentinel
denoted by NULL which indicates the end of the list. The figure 2.3 shows how the linked
list is stored in memory. The nodes of a list need not occupy adjacent elements in the array
DATA and LINK.

Generally the data field of a node may be a record with more than one data item. In such
case, the data must be store in some type of record structure or in a collection of parallel
arrays.

Traversing a Linked List Traversing a linked list means processing each node of list exactly
once.
Algorithm: Traversing a linked list
1. Set P: = START. [ Initializes pointer PTR]
2. Repeat Step 3 and 4 while P ≠ NULL.
3. Apply PROCESS to DATA [P].
4. Set P := LINK [P] .[P points to the next node] [End of Step 2 loop]

Page 6 of 11 Mail id: helpdesk@mujonline.edu.in

Phone: +91 79966 00444 (Toll
Free)
 Centre for Distance & Online Education
5. Exit
In the algorithm P is the pointer variable which points to the node that is currently being
processed and LINK [P] points to the next node to be processed. P := LINK [P] Thus the
pointer moves to the next node in the lis-t.

B. What are the different types of link list. Write an algorithm to create circular list.

The different types of link list are:

1. Doubly linked list
2. Circular Linked List

1. Doubly Linked List: In some situation we need to traverse both forward and backward of a
linked list. The linked list with this property needs two link field one to point the next node is
called next link field and another to point the previous node is called previous link field. The
linked list containing this type of nodes is called doubly linked list or two- way list. shows the
structure of doubly linked list. The operations of doubly linked list are same as one- way list
they are traversing, searching, insertion and deletion.
2. Circularly linked list Circular linked list is the one where the null pointer in the last node is
replaced with the address of the first node so that it forms a circle. The advantage of this
circular linked list is easy accessibility of node i.e. every node is accessible from a given
node. The circular linked list can be implemented both in one- way list and two- way lists.

struct Node {
int data;
Node* next;
};
void insertNode(Node** head, int data) {
Node* newNode = new Node;
newNode->data = data;
// Handle first node
if (*head == NULL) {
newNode->next = newNode;
*head = newNode;
return;
}

// Find the last node

Node* current = *head;
while (current->next != *head) {
current = current->next;
}
// Insert at the end and make it circular
newNode->next = *head;
current->next = newNode;
}

Page 7 of 11 Mail id: helpdesk@mujonline.edu.in

Phone: +91 79966 00444 (Toll
Free)
 Centre for Distance & Online Education

Q5. Write the Algorithm to find the maximum and minimum items in a set of n element.
Also explain the working of the algorithm.

function find_max_and_min(set):
if set is empty:
return None, None // or appropriate values indicating an empty set

// Initialize max_item and min_item

max_item = set[0]
min_item = set[0]

// Iterate through the set

for each item in set:
if item > max_item:
max_item = item
if item < min_item:
min_item = item

// Return the results

return max_item, min_item

Initialization:
The algorithm starts by initializing max_item and min_item with the first element of the set.
This is because we need a baseline to compare all other elements against.
Iteration:
The algorithm then iterates through each element in the set. For each element, it checks if the
element is greater than the current max_item. If it is, it updates max_item to this new
element.
Similarly, it checks if the element is less than the current min_item. If it is, it updates
min_item to this new element.
Result:
After completing the iteration through the set, the max_item will contain the highest value
found in the set, and min_item will contain the lowest value.
Example
This algorithm ensures that each element is compared only once, making it efficient with a
time complexity of O(n)O(n)O(n), where nnn is the number of elements in the set.
Q6. A. What is Stack? Discuss the Array implementation of a stack along with push()
and pop() algorithms.

A stack is a data structures in which insertion and deletion of items are made at the one end,
called the top of the stack.
Array implementation of stack:

Page 8 of 11 Mail id: helpdesk@mujonline.edu.in

Phone: +91 79966 00444 (Toll
Free)
 Centre for Distance & Online Education

Array Representation of Stack

Push operation
The push operation is used to add an item into a stack. Before executing push operation one
must check for the OVERFLOW condition, i.e. check whether there is room for the new item
in the stack. The following procedure performs the PUSH operation.
PUSH (STACK, TOP, MAXSTK, ITEM)
1. [Stack already full?]
If TOP = MAXSTK, then: print: OVERFLOW, and Return.
2. Set TOP := TOP + 1. [Increases TOP by 1]
3. Set STACK [TOP]:= ITEM. [Insert ITEM in new TOP position]
4. Return.

As per the procedure first it checks for the OVERFLOW condition. Since the stack is not full
the TOP pointer is incremented by 1, TOP= TOP + 1. So, now TOP points to a new location
and then the ITEM is inserted into that position.
Pop operation
The pop operation is used to remove an item from a stack.
Procedure: POP (STACK, TOP, ITEM)
1. [Stack is empty?]
If TOP = 0, then: Print: UNDERFLOW, and Return.
2. Set ITEM := STACK [TOP] . [Assign Top element to ITEM]
3. Set TOP := TOP – 1. [Decreases Top by 1]
4. Return.
As per the procedure, first it checks for the underflow condition. Since the stack is not empty
the top element in the stack is assigned to ITEM, ITEM: = STACK [TOP]. Then the top is
decremented by 1.

B. What is Queue? Discuss the Array implementation of a queue along with enqueue()
and dequeue() algorithms.

Page 9 of 11 Mail id: helpdesk@mujonline.edu.in

Phone: +91 79966 00444 (Toll
Free)
 Centre for Distance & Online Education
A queue is a linear list of elements in which deletions can take place only at one end, called
the front and insertions can take place only at the other end, called the rear. The terms “front”
and “rear” are used in describing a linear list only when it is implemented as a queue.

Queue representation
Following are the two methods offered by queue for adding and deleting element from the
queue.  enqueue - add a new item at the back of the queue
 dequeue - remove the item at the front of the queue

Array implementation of queue

Here the queue in a linear way is maintained with two pointers called FRONT, containing the
location of the front element of the queue and REAR, to hold the location which is at rear.
Whenever the element is deleted from the queue the value of the FRONT is increased by 1
this can be implemented by FRONT: =FRONT+1. Similarly whenever an element is added to
the queue, the value of REAR is increased by 1 by assigning REAR: =REAR +1

Array representation of queue

Enqueue Algorithm:
QINSERT (QUEUE,N,FRONT,REAR,ITEM)
1. If FRONT=1 and REAR =N, or FRONT=REAR+1 then
Write OVERFLOW, and Return
2. [Find new value of REAR]
If FRONT :=NULL, then: [Queue is empty initially]
Set FRONT :=1 and REAR:=1
Else if REAR=N then:
Set REAR :=1.
Else
Set REAR:=REAR+1
3. Set QUEUE[REAR]:=ITEM

Page 10 of 11 Mail id: helpdesk@mujonline.edu.in

Phone: +91 79966 00444 (Toll
Free)
 Centre for Distance & Online Education
4. Return

Dequeue Algorithm:
QDELETE (QUEUE, N, FRONT, REAR, ITEM)
1. If FRONT: =NULL, then write : UNDERFLOW and Return.
2. Set ITEM:=QUEUE[FRONT].
3. If FRONT = REAR, then: // only one element.
Set FRONT: =NULL and REAR: =NULL.
Else if FRONT := N then:
Set FRONT: =1.
Else:
Set FRONT: = FRONT +1.
4. Return.

Page 11 of 11 Mail id: helpdesk@mujonline.edu.in

Phone: +91 79966 00444 (Toll
Free)