//Insertion short //BubbleSort

#include <stdio.h> #include <stdio.h>

void insertionSort(int a[], int n) { void bubbleSort(int a[], int n) {
for (int i = 1; i < n; i++) { for (int i = 0; i < n - 1; i++)
int key = a[i], j = i - 1; for (int j = 0; j < n - i - 1; j++)
while (j >= 0 && a[j] > key) if (a[j] > a[j + 1]) {
a[j + 1] = a[j--]; int temp = a[j];
a[j + 1] = key; a[j] = a[j + 1];
} } a[j + 1] = temp;
int main() { } }
int a[] = {5, 2, 9, 1, 6}; int main() {
int n = sizeof(a) / sizeof(a[0]); int a[] = {5, 1, 4, 2, 8};
insertionSort(a, n);
int n = sizeof(a) / sizeof(a[0]);
printf("Sorted array: "); bubbleSort(a, n);
for (int i = 0; i < n; i++){ printf("Sorted array: ");
printf("%d ", a[i]);} for (int i = 0; i < n; i++){
return 0; printf("%d ", a[i]); }
} return 0;
}
––-–––––––––––+++
//Merge Sort Quick Sort
#include <stdio.h> #include <stdio.h>
void merge(int a[], int b[], int m, int n, int void quickSort(int a[], int low, int high) {
merged[]) {
if (low < high) {
int i = 0, j = 0, k = 0;
int pivot = a[high];
while(i < m && j < n) {
int i = low - 1;
if(a[i] < b[j])
for (int j = low; j < high; j++) {
merged[k++] = a[i++];
if (a[j] < pivot) {
else
i++;
merged[k++] = b[j++];
int temp = a[i]; a[i] = a[j]; a[j] =
} temp;
while(i < m) }
merged[k++] = a[i++]; }
while(j < n) int temp = a[i + 1]; a[i + 1] = a[high];
a[high] = temp;
merged[k++] = b[j++];
int pi = i + 1;
}
quickSort(a, low, pi - 1);
int main() {
quickSort(a, pi + 1, high);
int a[] = {1, 3, 5};
} }
int b[] = {2, 4, 6};
int main() {
int merged[6];
int a[] = {10, 7, 8, 9, 1, 5};
int m = 3, n = 3;
int n = sizeof(a) / sizeof(a[0]);
merge(a, b, m, n, merged);
quickSort(a, 0, n - 1);
printf("Merged array: ");
printf("Sorted array: ");
for(int i = 0; i < m + n; i++)
for (int i = 0; i < n; i++)
printf("%d ", merged[i]);
printf("%d ", a[i]);
return 0;
return 0;
}
}
C program implementing a singly linked list // Delete at beginning

void deleteBeginning() { if (head == NULL) {

#include <stdio.h> #include <stdlib.h> printf("List is empty\n"); return; }

struct Node { int data; struct Node* next; }; struct Node* temp = head; head = head->next;

struct Node* head = NULL; free(temp); }

// Insert at the end

void insertEnd(int value) { struct Node* newNode = // Delete at end

(struct Node*)malloc(sizeof(struct Node)); void deleteEnd() { if (head == NULL) {
newNode->data = value; newNode->next = NULL; printf("List is empty\n"); return; }
if (head == NULL) { head = newNode; return; } if (head->next == NULL) { free(head);
struct Node* temp = head; head = NULL; return; }
while (temp->next != NULL){ temp = temp->next; struct Node* temp = head;
temp->next = newNode; } while (temp->next->next != NULL){
// Insert at the beginning temp = temp->next; free(temp->next);
void insertBeginning(int value) { struct Node* temp->next = NULL; }
newNode = (struct Node*)malloc(sizeof(struct Node));
// Delete at a given position (1-based)
newNode->data = value; newNode->next = head;
void deleteAtPosition(int pos) { if (head == NULL) {
head = newNode; }
printf("List is empty\n"); return; }
// Insert at a given position (1-based)
if (pos == 1) { deleteBeginning(); return; }
void insertAtPosition(int value, int pos) { if (pos == 1) {
struct Node* temp = head;
insertBeginning(value); return; }
for (int i = 1; i < pos - 1 && temp != NULL; i++)
struct Node* newNode =
(structNode*)malloc(sizeof(struct Node)); { temp = temp->next;

newNode->data = value; if (temp == NULL || temp->next == NULL) {

struct Node* temp = head; printf("Position out of range\n"); return; }

for (int i = 1; i < pos - 1 && temp != NULL; i++) struct Node* toDelete = temp->next;

temp = temp->next; temp->next = toDelete->next; free(toDelete); }

if (temp == NULL) { printf("Position out of range\n");

free(newNode); return; }

newNode->next = temp->next;

temp->next = newNode; }
// Display the list

void display() { if (head == NULL) {

printf("List is empty\n"); return; }

struct Node* temp = head; printf("List: ");

while (temp != NULL) {

printf("%d -> ", temp->data);

temp = temp->next; } printf("NULL\n"); }

// Search for a value

void search(int value) { struct Node* temp = head;

int pos = 1; while (temp != NULL) {

if (temp->data == value) {

printf("Value %d found at position %d\n", value, pos); return; } temp = temp->next; pos++; }

printf("Value %d not found in the list\n", value); }

int main() {
insertEnd(10);
insertEnd(20);
insertEnd(30);
display();

insertBeginning(5); display();
insertAtPosition(15, 3); display();
deleteBeginning(); display();
deleteEnd(); display();

deleteAtPosition(2); display();

search(20); search(100);

return 0;

}
C program for Doubly Linked List // Insert at position (1-based)
#include <stdio.h> void insertAtPosition(int value, int pos) {
#include <stdlib.h> if (pos == 1) { insertBeginning(value); return; }
struct Node { int data; struct Node* newNode =
struct Node* prev; struct Node* next; (structNode*)malloc(sizeof(struct Node));

};struct Node* head = NULL; newNode->data = value;

// Insert at beginning struct Node* temp = head;

void insertBeginning(int value) { for (int i = 1; i < pos - 1 && temp != NULL; i++)

struct Node* newNode = (struct temp = temp->next;

Node*)malloc(sizeof(struct Node)); if (temp == NULL) {
newNode->data = value; printf("Position out of range\n"); free(newNode);
newNode->prev = NULL; return; }
newNode->next = head; newNode->next = temp->next;
if (head != NULL) newNode->prev = temp;
head->prev = newNode; if (temp->next != NULL){
head = newNode; temp->next->prev = newNode;
} temp->next = newNode; }
// Insert at end // Delete at beginning
void insertEnd(int value) { struct Node* newNode = void deleteBeginning() { if (head == NULL) {
(struct Node*)malloc(sizeof(struct Node));
printf("List is empty\n"); return; }
newNode->data = value; newNode->next = NULL;
struct Node* temp = head; head = head->next;
if (head == NULL) { newNode->prev = NULL;
if (head != NULL) { head->prev = NULL; free(temp);}
head = newNode; return; }
// Delete at end
struct Node* temp = head;
void deleteEnd() { if (head == NULL) {
while (temp->next != NULL){
printf("List is empty\n"); return; }
temp = temp->next;
struct Node* temp = head;
temp->next = newNode; newNode->prev = temp; }
if (temp->next == NULL) {

free(head); head = NULL; return; }

while (temp->next != NULL){

temp = temp->next; temp->prev->next = NULL;

free(temp); }
// Delete at position (1-based)
void deleteAtPosition(int pos) { if (head == NULL) { // Search for a value
void search(int value) {
printf("List is empty\n"); return; }
struct Node* temp = head;
if (pos == 1) { deleteBeginning(); return; } int pos = 1;
while (temp != NULL) {
struct Node* temp = head;
if (temp->data == value) {
for (int i = 1; i < pos && temp != NULL; i++){ printf("Value %d found at position %d\n", value,
pos);
temp = temp->next;
return;
if (temp == NULL) { }
temp = temp->next;
printf("Position out of range\n"); return; }
pos++;
if (temp->next != NULL){ }
printf("Value %d not found in the list\n", value);
temp->next->prev = temp->prev; }
}
if (temp->prev != NULL) { int main() {
temp->prev->next = temp->next; free(temp); } insertEnd(10);
insertEnd(20);
// Display forward insertEnd(30);
void displayForward() { displayForward();
if (head == NULL) { printf("List is empty\n"); displayBackward();
return; }
struct Node* temp = head; insertBeginning(5); displayForward();
printf("Forward: "); insertAtPosition(15, 3); displayForward();
while (temp != NULL) { deleteBeginning(); displayForward();
printf("%d <-> ", temp->data); deleteEnd(); displayForward();
temp = temp->next; deleteAtPosition(2); displayForward();
} search(20); search(100);
printf("NULL\n"); return 0;
} }
// Display backward
void displayBackward() { Output:-
if (head == NULL) { Forward: 10 <-> 20 <-> 30 <-> NULL
printf("List is empty\n"); return; } Backward: 30 <-> 20 <-> 10 <-> NULL
Forward: 5 <-> 10 <-> 20 <-> 30 <-> NULL
struct Node* temp = head; Forward: 5 <-> 10 <-> 15 <-> 20 <-> 30 <-> NULL
// Move to last node Forward: 10 <-> 15 <-> 20 <-> 30 <-> NULL
while (temp->next != NULL) { temp = temp->next; Forward: 10 <-> 15 <-> 20 <-> NULL
printf("Backward: "); Forward: 10 <-> 20 <-> NULL
while (temp != NULL) { Value 20 found at position 2
printf("%d <-> ", temp->data); Value 100 not found in the list
temp = temp->prev;
}
printf("NULL\n");
}
C program implementing a Circular Singly Linked List // Insert at position (1-based)

#include <stdio.h> void insertAtPosition(int value, int pos) {

#include <stdlib.h> if (tail == NULL) { if (pos == 1) {

struct Node { int data; struct Node* next; }; insertBeginning(value);

struct Node* tail = NULL; } else { printf("List is empty, position out of

range\n"); }return; }
// Insert at beginning
if (pos == 1) { insertBeginning(value); return; }
void insertBeginning(int value) {
struct Node* temp = tail->next; // head
struct Node* newNode =
(structNode*)malloc(sizeof(struct Node)); struct Node* newNode =

newNode->data = value; (struct Node*)malloc(sizeof(struct Node));

if (tail == NULL) { newNode->data = value;

tail = newNode; tail->next = tail; int count = 1;

} else { newNode->next = tail->next; while (count < pos - 1 && temp != tail) {

tail->next = newNode; } } temp = temp->next;

count++;

// Insert at end } if (count != pos - 1) { printf("Position out of

range\n"); free(newNode); return; }
void insertEnd(int value) {
newNode->next = temp->next;
insertBeginning(value);
temp->next = newNode;
tail = tail->next; // move tail to the new node
if (temp == tail){ tail = newNode; }
}

// Delete at beginning

void deleteBeginning() { if (tail == NULL) { // Delete at end

printf("List is empty\n"); return; } void deleteEnd() { if (tail == NULL) {

struct Node* head = tail->next; printf("List is empty\n"); return; }

if (head == tail) { free(head); tail = NULL; struct Node* temp = tail->next; // head
return; } if (temp == tail) { free(tail); tail = NULL; return;}
tail->next = head->next; free(head); } while (temp->next != tail) {temp = temp->next;

temp->next = tail->next; free(tail); tail = temp;

}
// Delete at position (1-based) // Search for a value
void deleteAtPosition(int pos) { void search(int value) { if (tail == NULL) {
if (tail == NULL) { printf("List is empty\n"); printf("List is empty\n"); return; }
return; }
struct Node* temp = tail->next;
if (pos == 1) { deleteBeginning(); return; }
int pos = 1;
struct Node* temp = tail->next; // head
do {
int count = 1;
if (temp->data == value) {
while (count < pos - 1 && temp->next != tail->next)
{ printf("Value %d found at position %d\n", value,
pos);
temp = temp->next; count++; }
return; } temp = temp->next; pos++;
if (temp->next == tail->next || count != pos - 1) {
} while (temp != tail->next);
printf("Position out of range\n"); return; }
printf("Value %d not found in the list\n", value); }
struct Node* toDelete = temp->next;
int main() {
temp->next = toDelete->next; insertEnd(10);
if (toDelete == tail){ tail = temp; free(toDelete); } insertEnd(20);
insertEnd(30);
// Display list display();
void display() { if (tail == NULL) {
insertBeginning(5); display();
printf("List is empty\n"); return; } insertAtPosition(15, 3); display();
struct Node* temp = tail->next; // head deleteBeginning(); display();
deleteEnd(); display();
printf("List: "); deleteAtPosition(2); display();
do { search(20); search(100); return 0;}

printf("%d -> ", temp->data);

Output:-
temp = temp->next;
List: 10 -> 20 -> 30 -> (back to head)
} while (temp != tail->next);
List: 5 -> 10 -> 20 -> 30 -> (back to head)
printf("(back to head)\n"); List: 5 -> 10 -> 15 -> 20 -> 30 -> (back to head)
List: 10 -> 15 -> 20 -> 30 -> (back to head)
}
List: 10 -> 15 -> 20 -> (back to head)
List: 10 -> 20 -> (back to head)
Value 20 found at position 2
Value 100 not found in the list
C program implementing a Circular Deque // Delete at Rear

#include <stdio.h> void deleteRear() { if (isEmpty()) {

#define SIZE 5 printf("Deque is empty\n"); return; }
int deque[SIZE];
int front = -1, rear = -1; printf("Deleted from rear: %d\n",
deque[rear]);
// Check if deque is full if (front == rear) { front = rear = -1; }
int isFull() { return (front == (rear + 1) % else if (rear == 0) { rear = SIZE - 1; } else
SIZE); } { rear--; } }
// Check if deque is empty //Display

int isEmpty() { return (front == -1);} void display() { if (isEmpty()) {

void insertFront(int value) { printf("Deque is empty\n"); return; }

if (isFull()) { printf("Deque is full\n"); printf("Deque elements: "); int i = front;

return; } while (1) {
if (isEmpty()) { front = rear = 0; } else if printf("%d ", deque[i]);
(front == 0) {
if (i == rear){ break; i = (i + 1) % SIZE; }
front = SIZE - 1; } else { front--; }
printf("\n");}
deque[front] = value; }
int main() {
//Insert in rear insertRear(10);
void insertRear(int value) { if (isFull()) { insertRear(20);
insertFront(5);
printf("Deque is full\n"); return; }
insertFront(1);
if (isEmpty()) { front = rear = 0; } else { display();
rear = (rear + 1) % SIZE; }
deleteFront();
deque[rear] = value; } deleteRear();
void deleteFront() { if (isEmpty()) { display();

printf("Deque is empty\n"); return; }

insertRear(30);
printf("Deleted from front: %d\n", insertFront(40); // may show "Deque is
deque[front]); full" if full
if (front == rear) { front = rear = -1; } else { display();

front = (front + 1) % SIZE; } } return 0;

}
1. Define data structure. What is the main advantage of data structure?
A data structure is a logical or mathematical way of organizing data. It is the way of organizing,
storing and retrieving data and the set of operations that can be performed on that data. Eg.: Arrays,
structures, stack, queue, linked list, trees, graphs.
2. What are the different types of data structures.
Primitive Data Structure- It is basic data structure which is defined by the language and can be
accessed directly by the computer.Non Primitive Data Structure- Data structure emphasize on
structuring of a group of homogenous or heterogeneous data item. Linear Data Structure- A data
structure which contains a linear arrangement of elements in the memory. Non-Linear Data
Structure- A data structure which represents a hierarchical arrangement of elements.
3. Define Abstract Data Type.
An Abstract data type is a data type that is organized in such a way that the specification of the
objects and the specification of operations on the objects is separated from the representation of
the objects and the implementation of the operations. In other words, ADT is a collection of values
and a set of operations on those values. ADT is a mathematical tool for specifying the logical
properties of a datatype.
4. Define an array. Mention the different kinds of arrays with which you can manipulate and
represent data.
An array is a group of related data items that shares a common name. In other words, we can say it
is a collection of data items which are of same data type. The data items are stored in contiguous
memory locations. There are three kinds of arrays present for the manipulation and representation
of data.They are 1. One dimensional array. 2. Two dimentional array. 3. Multi dimentional array
12. Define queue and give its applications
A Queue is an ordered list in which all insertions take place at one end called the rear and all
deletions take place at the opposite end called the front. The Queue is called as the FIFO data
structure.Applications of Queue: 1. It is used in batch processing of O.S 2. It is used in simulation 3.
It is used in queuing theory 4. It is used in computer networks where the server takes the jobs of
the clients using queuing strategy.
13. What is a circular queue? How do you check the queue full condition?
In circular queue, the elements are arranged in a circular fashion. Circular queue is a data structure
which efficiently utilizes the memory space & the elements Q[0], Q[1], …, Q[n- 1] are arranged in
circular fashion such that Q[n-1] is followed by Q[0]. It returns queue full condition only when the
queue does not have any space to insert new values. But ordinary queue returns queue full
condition when the rear reaches the last position
. Void CircularQFull() { if (front == (rear+1)%maxsize) printf(“Circular Queue is Full”);}
1. Define tree. A tree is a finite set of one or more nodes such that there is a specially designated
node called the root. The remaining nodes are partitioned into n>=0 disjoint sets T1, T2, …, Tn,
where each of these sets is a tree. T1,…,Tn are called the subtrees of the root.
2. Define the following terms: node, leaf node, ancestors, siblings of a node
Node: Each element of a binary tree is called node of a tree. Each node may be a root of a tree
with zero or more sub trees. Leaf node: A node with no children (successor) is called leaf node or
terminal node. Ancestor: Node n1 is an ancestor of node n2 if n1 is either a father of n2 or father of
some ancestor of n2. Siblings: Two nodes are siblings if they are the children of the same parent.

3. Define level of a node, degree of a node, degree of a tree, height and depth of a tree.
Level of a node: The root node is at level 1. If a node is at level l, then its children are at level i+1.
Degree of a node: The number of sub trees of a node is called as degree of a node. The degree of a
tree is themaximum of the degree of the nodes in the tree. The height or depth of a tree is defined
to be the maximum level of any node in the tree.
4. What are the ways to represent Binary trees in memory?
1. Array representation (or) Sequential Representation.
2. Linked List representation (or) Node representation.
5. Define binary tree. Binary tree is a finite set of elements that is either empty or is partitioned
into three disjoint subsets. The first subset contains the single element called the root of tree. The
other two subsets are themselvesbinary tree called the left and right sub tree of original tree. In
other words, a binary tree is a tree inwhich each node can have a maximum of two children.
6. Define Full binary tree (or) Complete binary tree
A full binary tree of depth k is a binary tree of depth k having 2k – 1 nodes. In other words, all the
levels in the binary tree should contain the maximum number of nodes
7. Define strictly binary tree
If every non leaf node in a binary tree has non empty left and right sub trees then the tree is
termed as strictly binary tree. In other words, a strictly binary tree contains leaf nodes and non leaf
nodes of degree
8. List out few of the Application of tree data-structure?
The applications of tree data-structure are the manipulation of Arithmetic expression, Symbol Table
construction, Syntax analysis.
9. Define expression tree
An expression tree is built up from the simple operands and operators of an(arithmetic or logical)
expression by placing the simple operands as the leaves of a binary tree and the operators as the
interior nodes
12. What is a binary search tree?
A binary search tree is a binary tree. It may be empty1. Every element has a key & the keys are
distinct. 2. The keys in the left sub tree is smaller than the key in the root. 3. Keys in the right sub
tree is larger than the key in the root. 4. The left & right sub trees are also BST.
13. How will you construct binary search tree?
a. Make the first node as the root node.b. To insert the next node into the BST, search for the value
in the BST. If the value is found in the BST, then a duplicate value cannot be inserted into the BST. c.
If the element is not found, add the element at the point where the search becomes unsuccessful.
14. Define the term skewed tree?
In skewed tree all the nodes are skewed in one direction either left or right.
Left Skewed Tree: A tree in which all nodes are skewed in left direction.
Right Skewed Tree: A tree in which all nodes are skewed in right direction.

15. What is the maximum number of nodes in level i of a binary tree and what is the
maximum number of nodes in a binary tree of depth k?
The maximum number of nodes in level i of a binary tree = 2i-1
The maximum number of nodes in a binary tree of depth k = 2k -1, where k>0
16.What are the non-linear data structures? (JAN 2014)
Non-Linear Data Structure- A data structure which represents a hierarchical arrangement
ofelements. Examples: Graphs and trees.
17. Define balanced search tree.
Balanced search tree have the structure of binary tree and obey binary search tree properties with
that it always maintains the height as O(log n) by means of a special kind of rotations. Eg. AVL, Splay,
B-tree.
18.What are the drawbacks of AVL trees?
The drawbacks of AVL trees are Frequent rotations  The need to maintain balances for the
tree’s nodes  Overall complexity, especially of the deletion operation.
19. Define B-tree?
A B-tree of order m in an m-way search tree that is either empty or is of height ≥1 and
1. The root node has at least 2 children
2. All nodes other than the root node and failure nodes have at least m/2 children.
3. All failure nodes are at same level.
20. Explain AVL rotation.
Manipulation of tree pointers is centered at the pivot node to bring the tree back into height
balance. The visual effect of this pointer manipulation so to rotate the sub tree whose root is the
pivot node. This operation is referred as AVL rotation.
22. Explain Hashing.
Hashing is a technique used to identify the location of an identifier ‘x’ in the memory by some
arithmetic functions like f(x), which gives address of ‘x’ in the table.
24..Define Splay Tree.
A splay tree is a self-adjusting binary search treewith the additional property that recently accessed
elements are quick to access again. It performs basic operations such as insertion, look-up and
removal in O(log n) amortized time.
26.Write short notes on Heap.
Heap is a special case of balanced binary tree data structure where the root-node key is compared
with its children and arranged accordingly. If α has child node β then − key(α) ≥ key(β)
27.Define Binomial Heap.
A Binomial Heap is a collection of Binomial Trees A Binomial Tree of order 0 has 1 node. A Binomial
Tree of order k can be constructed by taking two binomial trees of order k-1, and making one as
leftmost child of other. A Binomial Tree of order k has following properties.
a) It has exactly 2k nodes. b) It has depth as k. c) There are exactly kCi nodes at depth i for i = 0,
1, . . . , k. d) The root has degree k and children of root are themselves Binomial Trees with order k-1,
k- 2,.. 0 from left to right.
28.Define Fibonacci Heaps.
Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-
ordered trees. It has a better amortized running time than many other priority queue data
structures including the binary heap and binomialheap.
29.Write notes on Hash Set.
 Implements Set Interface.
 Underlying data structure for HashSet is hashtable.
 As it implements the Set Interface, duplicate values are not allowed.
 Objects that you insert in HashSet are not guaranteed to be inserted in same order.
 Objects are inserted based on their hash code.
 NULL elements are allowed in HashSet.
 HashSet also implements Searlizable and Cloneable interfaces.
1. Write the concept of Prim’s spanning tree.
Prim’s algorithm constructs a minimum spanning tree through a sequence of expanding sub trees.
The initial sub tree in such a sequence consists of a single vertex selected arbitrarily from the set V
of the graph’s vertices. On each iteration, we expand the current tree in the greedy manner by
simply attaching to it the nearest vertex not in that tree. The algorithm stops after all the graph’s
vertices have been included in the tree being constructed
2. What is the purpose of Dijikstra’s Algorithm?
Dijikstra’s algorithm is used to find the shortest path between sources to every vertex. This
algorithm is applicable to undirected and directed graphs with nonnegative weights only.
3. How efficient is prim’s algorithm?
It depends on the data structures chosen for the graph itself and for the priority queue of the set V-
VT whose vertex priorities are the distances to the nearest tree vertices.
7. Write the concept of kruskal’s algorithm.
Kruskal’s algorithm looks at a minimum spanning tree for a weighted connected graph G=(V,E) as an
acyclic sub graph with |V|-1 edges for which the sum of the edge weights is the smallest.
Consequently, the algorithm constructs a minimum spanning tree as an expanding sequence of sub
graphs, which are always acyclic but are not necessarily connected on the intermediate stages of
the algorithm. The algorithm begins by sorting the graph’s edges in non decreasing order of their
weights. Then, starting with the empty sub graph, it scans this sorted list, adding the next edge on
the list to the current sub graph if such an inclusion does not create a cycle and simply skipping the
edge otherwise.
8. What is the difference between dynamic programming with divide and conquer method?
Divide and conquer divides an instance into smaller instances with no intersections whereas
dynamic programming deals with problems in which smaller instances overlap. Consequently divide
and conquer algorithm do not explicitly store solutions to smaller instances and dynamic
programming algorithms do
11. Define the single source shortest paths problem.
Dijkstra’s algorithm solves the single-source shortest-path problem of finding shortest paths from a
given vertex (the source) to all the other vertices of a weighted graph or digraph. It works as Prim’s
algorithm but compares path lengths rather than edge lengths. Dijkstra’s algorithm always yields a
correct solution for a graph with nonnegative weights
13. What do you meant by graph traversals?
Graph traversal (also known asgraph search) refers to the process of visiting (checking and/or
updating) each vertex in a graph. Such traversalsare classified by the order in which the vertices are
visited. Tree traversal is a special case of graph traversal
14. Define Depth First Search DFS
Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack to
remember to get the next vertex to start a search, when a dead end occurs in any iteration.
15. Write down the steps involved in DFS
Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices
from the stack, which do not have adjacent vertices.)
Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty
16. Define Breadth First Search (BFS)
Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and uses a queue to
remember to get the next vertex to start a search, when a dead end occurs in any iteration.
17. Write down the steps involved in Breadth First Search (BFS)
Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.
Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.
Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty
18. Define graph data structure
A graph is a pictorial representation of a set of objects where some pairs of objects are connected
by links. The interconnected objects are represented by points termed as vertices, and the links that
connect the vertices are called edges. Formally, a graph is a pair of sets (V, E), where V is the set of
vertices and Eis the set of edges, connecting the pairs of vertices.
4. Define Asymptotic Notations.
The notation that will enable us to make meaningful statements about the time and space
complexities of a program. This notation is called asymptotic notation. Some of the asymptotic
notation are 1. Big Oh notation, 2. Theta notation, 3. Omega notation, 4. Little Oh notation.
5. What is best-case efficiency?
The best-case efficiency of an algorithm is its efficiency for the best-case input of size n, which is an
input or inputs for which the algorithm runs the fastest among all possible inputs of that size.
6. Define divide and conquer design technique
A problem’s instance is divided into several smaller instances of the same problem, ideally of about
the same size The smaller instances are solved If necessary, the solutions obtained for the smaller
instances are combined to get a solution to the original instance
8. Define Knapsack problem
Given n items of known weights w1…wn and values v1…vn and knapsack of capacity W. The aims is
to find the most valuable subset if the items that fit into the knapsack. The exhaustive search
approach to knapsack problem leads to generating all the subsets of the set of n items given,
computing the total weight of each subset to identify feasible subsets and finding a subset of the
largest value among them.
9. Define merge sort.
The merge sort algorithm divides a given array A[0..n-1] by dividing it into two halves A[0.. n/2-1]
and A[ n/2-..n-1], sorting each of them recursively, and then merging the two smaller sorted arrays
into a single sorted one.
10. Define quick sort
Quick sort employs a divide-and-conquer strategy. It starts by picking an element from the list to be
the "pivot." It then reorders the list so that all elements with values less than the pivot come before
the pivot, and all elements with values greater than the pivot come it (a process often called
"partitioning"). It then sorts the sub-lists to the left and the right of the pivot using the same
strategy, continuing this process recursively until the whole list is sorted
11. What is a pivot element?
The pivot element is the chosen number which is used to divide the unsorted data into two halves.
The lower half contains less than value of the chosen number i.e. pivot element. The upper half
contains greater than value of the chosen number i.e. pivot element. So the chosen number is now
sorted.
12. Define Binary Search
Binary search is a efficient algorithm for searching in a sorted array. It works by comparing a search
key K with the array‟s middle element A[m]. If they match, the algorithm stops; otherwise, the
same operation is repeated recursively for the first half of the array if K<a[m] and for the second
half if K>A[m]
13. Define dynamic programming.
Dynamic programming is a technique for solving problems with overlapping sub problems. Rather
than solving overlapping sub problems again and again, dynamic programming suggests solving
each of the smaller sub problems only once and recording the results in a table from which a
solution to the original problem can then be obtained.
14. Define Optimal Binary Search Tree (OBST). (June 06)
Dynamic programming can be used for constructing an optimal binary search tree for a given set of
keys and known probabilities of searching for them. If probabilities of searching for an element of a
set are known, the average number of comparisons in a search will have smallest possible value in
an OBST.
15. State greedy technique.
The greedy approach suggests constructing a solution through a sequence of steps, each expanding
a partially constructed solution obtained so far, until a complete solution to the problem is reached.
16. Write down the optimization technique used for Warshall’s algorithm. State the rules and
assumptions which are implied behind that.
Optimization technique used in Warshall’s algorithm is Dynamic programming. Dynamic
programming is a technique for solving problems with overlapping sub problems. Typically, these
sub problems arise from a recurrence relating a solution to a givenproblem with solutions to its
smaller sub problems of the same type. Dynamic programming suggests solving each smaller sub
problem once and recording the results in a table from which a solution to the original problem can
be then obtained.
17. Define objective function and optimal solution
To find a feasible solution that either maximizes or minimizes a given objective function. It has to be
the best choice among all feasible solution available on that step.
18. Define knapsack problem using dynamic programming.
Designing a dynamic programming algorithm for the knapsack problem: given n items of known
weights w1. . . wn and values v1, . . . , vn and a knapsack of capacity W, find the most valuable
subset of the items that fit into the knapsack. We assume here that all the weights and the
knapsack capacity are positive integers; the item values do not have to be integers.