DATA STRUCTURE & ALGORITHMS TUTORIAL

QUESTIONS
Question 1. What Is An Avl Tree?
Answer :
AVL trees are height balancing binary search tree. AVL tree checks the height of left and
right sub-trees and assures that the difference is not more than 1. This difference is called
Balance Factor.
BalanceFactor = height(left-sutree) − height(right-sutree)
Question 2. What Is A Spanning Tree?
Answer :
A spanning tree is a subset of Graph G, which has all the vertices covered with minimum
possible number of edges. A spanning tree does not have cycles and it can not be
disconnected.
Question 3. How Many Spanning Trees Can A Graph Has?
Answer :
It depends on how connected the graph is. A complete undirected graph can have
maximum nn-1 number of spanning trees, where n is number of nodes.
Question 4. How Kruskal's Algorithm Works?
Answer :
This algorithm treats the graph as a forest and every node it as an individual tree. A tree
connects to another only and only if it has least cost among all available options and does
not violate MST properties.
Question 5. How Prim's Algorithm Finds Spanning Tree?
Answer :
Prim's algorithm treats the nodes as a single tree and keeps on adding new nodes to the
spanning tree from the given graph.
Question 6. What Is A Minimum Spanning Tree (mst) ?
Answer :
In a weighted graph, a minimum spanning tree is a spanning tree that has minimum
weight that all other spanning trees of the same graph.
Question 7. What Is A Heap In Data Structure?
Answer :
Heap is a special balanced binary tree data structure where root-node key is compared
with its children and arranged accordingly. A min-heap, a parent node has key value less
than its childs and a max-heap parent node has value greater than its childs.
Question 8. What Is A Recursive Function?
Answer :
A recursive function is one which calls itself, directly or calls a function that in turn calls it.
Every recursive function follows the recursive properties − base criteria where functions
stops calling itself and progressive approach where the functions tries to meet the base
criteria in each iteration.
Question 9. What Is Data-structure?
Answer :
Data structure is a way of defining, storing & retriving of data in a structural & systemetic
way. A data structure may contain different type of data items
Question 10. What Are Various Data-structures Available?
Answer :
Data structure availability may vary by programming languages. Commonly available data
structures are list, arrays, stack, queues, graph, tree etc.
Question 11. What Is Algorithm?
Answer :
Algorithm is a step by step procedure, which defines a set of instructions to be executed in
certain order to get the desired output.
Question 12. Why We Need To Do Algorithm Analysis?
Answer :
A problem can be solved in more than one ways. So, many solution algorithms can be
derived for a given problem. We analyze available algorithms to find and implement the
best suitable algorithm.
Question 13. What Are The Criteria Of Algorithm Analysis?
Answer :
An algorithm are generally analyzed on two factors − time and space. That is, how much
execution time and how much extra space required by the algorithm.
Question 14. What Is Asymptotic Analysis Of An Algorithm?
Answer :
Asymptotic analysis of an algorithm, refers to defining the mathematical
boundation/framing of its run-time performance. Using asymptotic analysis, we can very
well conclude the best case, average case and worst case scenario of an algorithm.
Question 15. What Are Asymptotic Notations?
Answer :
Asymptotic analysis can provide three levels of mathematical binding of execution time of
an algorithm −
Best case is represented by Ω(n) notation.
Worst case is represented by Ο(n) notation.
Average case is represented by Θ(n) notation.
Question 16. What Is Linear Data Structure?
Answer :
A linear data-structure has sequentially arranged data items. The next time can be located
in the next memory address. It is stored and accessed in a sequential manner. Array and
list are example of linear data structure.
Question 17. What Are Common Operations That Can Be Performed On A Data-
structure?
Answer :
The following operations are commonly performed on any data-structure −
Insertion − adding a data item
Deletion − removing a data item
Traversal − accessing and/or printing all data items
 Searching − finding a particular data item
Sorting − arranging data items in a pre-defined sequence
Question 18. Briefly Explain The Approaches To Develop Algorithms?
Answer :
There are three commonly used approaches to develop algorithms:
Greedy Approach − finding solution by choosing next best option
Divide and Conquer − diving the problem to a minimum possible sub-problem and
solving them independently
Dynamic Programming − diving the problem to a minimum possible sub-problem
and solving them combinedly
Question 19. Give Some Examples Greedy Algorithms?
Answer :
The below given problems find their solution using greedy algorithm approach:
Travelling Salesman Problem
Prim's Minimal Spanning Tree Algorithm
Kruskal's Minimal Spanning Tree Algorithm
Dijkstra's Minimal Spanning Tree Algorithm
Graph - Map Coloring
Graph - Vertex Cover
Knapsack Problem
Job Scheduling Problem
Question 20. What Are Some Examples Of Divide And Conquer Algorithms?
Answer :
The below given problems find their solution using divide and conquer algorithm
approach :
Merge Sort
Quick Sort
Binary Search
Strassen's Matrix Multiplication
Closest pair (points)
Question 21. What Are Some Examples Of Dynamic Programming Algorithms?
Answer :
The below given problems find their solution using divide and conquer algorithm
approach:
Fibonacci number series
Knapsack problem
Tower of Hanoi
All pair shortest path by Floyd-Warshall
Shortest path by Dijkstra
Project scheduling
Question 22. What Is A Linked-list?
Answer :
A linked-list is a list of data-items connected with links i.e. pointers or references. Most
modern high-level programming language does not provide the feature of directly
accessing memory location, therefore, linked-list are not supported in them or available in
form of inbuilt functions.
Question 23. What Is Stack?
Answer :
In data-structure, stack is an Abstract Data Type (ADT) used to store and retrieve values in
Last In First Out method.
Question 24. Why Do We Use Stacks?
Answer :
Stacks follows LIFO method and addition and retrieval of a data item takes only Ο(n) time.
Stacks are used where we need to access data in the reverse order or their arrival. Stacks
are used commonly in recursive function calls, expression parsing, depth first traversal of
graphs etc.
Question 25. What Operations Can Be Performed On Stacks?
Answer :
The below operations can be performed on a stack:
push() − adds an item to stack
pop() − removes the top stack item
peek() − gives value of top item without removing it
isempty() − checks if stack is empty
isfull() − checks if stack is full
Question 26. What Is A Queue In Data-structure?
Answer :
Queue is an abstract data structure, somewhat similar to stack. In contrast to stack, queue
is opened at both end. One end is always used to insert data (enqueue) and the other is
used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the
data item stored first will be accessed first.
Question 27. Why Do We Use Queues?
Answer :
As queues follows FIFO method, they are used when we need to work on data-items in
exact sequence of their arrival. Every operating system maintains queues of various
processes. Priority queues and breadth first traversal of graphs are some examples of
queues.
Question 28. What Operations Can Be Performed On Queues?
Answer :
The below operations can be performed on a stack:
enqueue() − adds an item to rear of the queue
dequeue() − removes the item from front of the queue
peek() − gives value of front item without removing it
isempty() − checks if stack is empty
isfull() − checks if stack is full
Question 29. What Is Linear Searching?
Answer :
Linear search tries to find an item in a sequentially arranged data type. These sequentially
arranged data items known as array or list, are accessible in incrementing memory
location. Linear search compares expected data item with each of data items in list or
array. The average case time complexity of linear search is Ο(n) and worst case complexity
is Ο(n2). Data in target arrays/lists need not to be sorted.
Question 30. What Is Binary Search?
Answer :
A binary search works only on sorted lists or arrays. This search selects the middle which
splits the entire list into two parts. First the middle is compared.
This search first compares the target value to the mid of the list. If it is not found, then it
takes decision on whether.
Question 31. What Is Bubble Sort And How Bubble Sort Works?
Answer :
Bubble sort is comparison based algorithm in which each pair of adjacent elements is
compared and elements are swapped if they are not in order. Because the time
complexity is Ο(n2), it is not suitable for large set of data.
Question 32. Tell Me Something About 'insertion Sort'?
Answer :
Insertion sort divides the list into two sub-list, sorted and unsorted. It takes one element
at time and finds it appropriate location in sorted sub-list and insert there. The output
after insertion is a sorted sub-list. It iteratively works on all the elements of unsorted sub-
list and inserts them to sorted sub-list in order.
Question 33. What Is Selection Sort?
Answer :
Selection sort is in-place sorting technique. It divides the data set into two sub-lists: sorted
and unsorted. Then it selects the minimum element from unsorted sub-list and places it
into the sorted list. This iterates unless all the elements from unsorted sub-list are
consumed into sorted sub-list.
Question 34. How Insertion Sort And Selection Sorts Are Different?
Answer :
Both sorting techniques maintains two sub-lists, sorted and unsorted and both take one
element at a time and places it into sorted sub-list. Insertion sort works on the current
element in hand and places it in the sorted array at appropriate location maintaining the
properties of insertion sort. Whereas, selection sort searches the minimum from the
unsorted sub-list and replaces it with the current element in hand.
Question 35. What Is Merge Sort And How It Works?
Answer :
Merge sort is sorting algorithm based on divide and conquer programming approach. It
keeps on dividing the list into smaller sub-list until all sub-list has only 1 element. And then
it merges them in a sorted way until all sub-lists are consumed. It has run-time complexity
of Ο(n log n) and it needs Ο(n) auxiliary space.
Question 36. What Is Shell Sort?
Answer :
Shell sort can be said a variant of insertion sort. Shell sort divides the list into smaller
sublist based on some gap variable and then each sub-list is sorted using insertion sort. In
best cases, it can perform upto Ο(n log n).
Question 37. How Quick Sort Works?
Answer :
Quick sort uses divide and conquer approach. It divides the list in smaller 'partitions' using
'pivot'. The values which are smaller than the pivot are arranged in the left partition and
greater values are arranged in the right partition. Each partition is recursively sorted using
quick sort.
Question 38. What Is A Graph?
Answer :
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.
Question 39. How Depth First Traversal Works?
Answer :
Depth First Search algorithm(DFS) 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.
Question 40. How Breadth First Traversal Works?
Answer :
Breadth First Search algorithm(BFS) traverses a graph in a breadthwards motion and uses
a queue to remember to get the next vertex to start a search when a dead end occurs in
any iteration.
Question 41. What Is A Tree?
Answer :
A tree is a minimally connected graph having no loops and circuits.
Question 42. What Is A Binary Tree?
Answer :
A binary tree has a special condition that each node can have two children at maximum.
Question 43. What Is A Binary Search Tree?
Answer :
A binary search tree is a binary tree with a special provision where a node's left child must
have value less than its parent's value and node's right child must have value greater than
it's parent value.
Question 44. What Is Tree Traversal?
Answer :
Tree traversal is a process to visit all the nodes of a tree. Because, all nodes are connected
via edges (links) we always start from the root (head) node.
There are three ways which we use to traverse a tree:
In-order Traversal
Pre-order Traversal
Post-order Traversal
Question 45. What Is Tower Of Hanoi?
Answer :
Tower of Hanoi, is a mathematical puzzle which consists of three tower (pegs) and more
than one rings. All rings are of different size and stacked upon each other where the large
disk is always below the small disk. The aim is to move the tower of disk from one peg to
another, without breaking its properties.
Question 46. What Is Fibonacci Series?
Answer :
Fibonacci Series generates subsequent number by adding two previous numbers. For
example − 0 1 1 2 3 5 8 13.
Question 47. What Is Hashing?
Answer :
Hashing is a technique to convert a range of key values into a range of indexes of an array.
By using hash tables, we can create an associative data storage where data index can be
find by providing its key values.
Question 48. What Is Interpolation Search Technique?
Answer :
Interpolation search is an improved variant of binary search. This search algorithm works
on the probing position of required value.
Question 49. What Is The Prefix And Post Fix Notation Of (a + B) * (c + D) ?
Answer :
Prefix Notation − * + a b + c d
Postfix Notation − a b + c d + *