Advanced Data Structures & Algorithm Analysis
UNIT – I:
Introduction to Algorithm Analysis, Space and Time Complexity analysis,
Asymptotic Notations.
AVL Trees – Creation, Insertion, Deletion operations and Applications
B-Trees – Creation, Insertion, Deletion operations and Applications
UNIT – II:
Heap Trees (Priority Queues) – Min and Max Heaps, Operations and
Applications
Graphs – Terminology, Representations, Basic Search and Traversals,
Connected Components and Biconnected Components, applications
Divide and Conquer: The General Method, Quick Sort, Merge Sort,
Strassen’s matrix multiplication, Convex Hull
UNIT – III:
Greedy Method: General Method, Job Sequencing with deadlines, Knapsack
Problem, Minimum cost spanning trees, Single Source Shortest Paths
Dynamic Programming: General Method, All pairs shortest paths, Single
Source Shortest Paths– General Weights (Bellman Ford Algorithm), Optimal
Binary Search Trees, 0/1 Knapsack, String Editing, Travelling Salesperson
problem
UNIT – IV:
Backtracking: General Method, 8-Queens Problem, Sum of Subsets problem,
Graph Coloring, 0/1 Knapsack Problem
Branch and Bound: The General Method, 0/1 Knapsack Problem, Travelling
Salesperson problem
UNIT – V:
NP Hard and NP Complete Problems: Basic Concepts, Cook’s theorem
NP Hard Graph Problems: Clique Decision Problem (CDP), Chromatic
Number Decision Problem (CNDP), Traveling Salesperson Decision Problem
(TSP)
NP Hard Scheduling Problems: Scheduling Identical Processors, Job Shop
Scheduling
10 MARKS QUESTIONS
UNIT-1:
1. A) Write in detail about asymptotic notations
B) Write about space complexity and time complexity
2. What is an AVL tree? Explain about its operations with example?
3. What is a B-Tree? Explain its operations with example?
4. What is a B+ trees? Write its creation with 5,3,21,9,1,13,2,7,10,12,4,8 and delete 5,3,and
21?
UNIT-2:
1. What is a Heap? Write about min-max Heap? Explain its operations and it’s
applications?
2. A) What is a graph? Explain in detail about tree traversing techniques with example
list?
B) Explain in detail about Strassen’s matrix multiplication?
3. Explain about connected and biconnected graphs with examples?
4. A) what is divide and conquer approach? Explain merge sort with algorithm and your
own example? (Not less than with 10 elements), what is the best, avg, worst case
complexities of merge sort?
B) Explain Quick sort with algorithm and your own example? (Not less than with 10
elements), what is the best, avg, worts case complexities of merge sort?
UNIT-3:
1. Write about All Pair Shortest Path algorithms? Explain it with algorithm and example?
2. Write about Single Source Shortest Path algorithms? Explain it with algorithm and
example?
3. Write about Minimum Cost spanning tree algorithms? Explain any algorithm with its
algorithm and example?
4. Write about Travelling sales person problem by using Dynamic programming? What is
the space and time complexity of TSP?
4. What is a knapsack? Let us consider that n=3,m=20, p=(=25,24,15) w=(18,15,10)find the
profits and weights of a knapsack by using greedy method?
5. Explain a 0/1 Knapsack problem using Dynamic programming?
6. Write about job scheduling with deadlines with example?
UNIT-4:
1. What is a Back tracking? Explain 8-queen problem in detail?
2. Explain the Sum of Sub Sets problem completely?
3. Let n=3,m=20, p=(=25,24,15) w=(18,15,10) then what is the solution for 0/1 knap sack
problem using backtracking ?
4. What is a branch and bound approach? Explain 0/1 knapsack problem with your own
example?
5. Explain travelling sales man/person problem with your own example using branch and
bound approach?
UNIT-5:
1. What is a class P and NP? Explain about P is NP complete (cooks theorem)?
2. What is NP Hard graph problem? Explain clique decision problem with example?
3. What is NP Hard scheduling? Write about job shop scheduling?
4. Write about Number Decision Problem (CNDP) with example?
2 MARK QUESTIONS WITH ANSWERS
1. Define AVL Tree.
Ans: AVL stands for Adelson-Velskii and Landis. An AVL tree is a binary search
tree which has the following properties:
1. The sub-trees of every node differ in height by at most one.
2. Every sub-tree is an AVL tree.
Search time is O(logn). Addition and deletion operations also take O(logn) time.
2. What do you mean by balanced trees?
Ans: Balanced trees have the structure of binary trees and obey binary search tree
properties. Apart from these properties, they have some special constraints, which
differ from one data structure to another. However, these constraints are aimed only at
reducing the height of the tree, because this factor determines the time complexity.
Eg: AVL trees, Splay trees.
3. What are the categories of AVL rotations?
Ans: Let A be the nearest ancestor of the newly inserted nod which has the balancing
factor ±2. Then the rotations can be classified into the following four categories:
Left-Left: The newly inserted node is in the left subtree of the left child of A.
Right-Right: The newly inserted node is in the right subtree of the right child of A.
Left-Right: The newly inserted node is in the right subtree of the left child of A.
Right-Left: The newly inserted node is in the left subtree of the right child of A.
4. What do you mean by balance factor of a node in AVL tree?
Ans: The height of left subtree minus height of right subtree is called balance factor
of a node in AVL [Link] balance factor may be either 0 or +1 or -[Link] height of an
empty tree is -1.
5. List out the steps involved in deleting a node from a binary search tree.
Ans: ▪ Deleting a node is a leaf node (ie) No children
▪ Deleting a node with one child.
▪ Deleting a node with two Childs.
6. What is ‘B’ Tree?
Ans: A B-tree is a tree data structure that keeps data sorted and allows searches,
insertions, and deletions in logarithmic amortized time. Unlike self-balancing binary
search trees, it is optimized for systems that read and write large blocks of data. It is
most commonly used in database and file systems.
7. Illustrate an algorithm? What are the criteria for performance of an Algorithm?
Ans: An Algorithm is a step by step process for a program. It is a blue print for a program.
An Algorithm must satisfy the following criteria:
1. Input: In every algorithm there must be zero or more qualities are externally supplied.
2. Output: At least one quality is produced.
3. Definiteness: Each instruction is clear and unambiguous.
4. Finiteness: If we trace out the instructions of an algorithm then for all cases the algorithm
terminates after a finite number of steps.
5. Effectiveness: Every instruction must be very basic so that it can be carried out, in principle,
by a person using only pencil and paper.
8. Write about types of space and time complexities of an algorithm?
9. Write about asymptotic notations with their graphs?
Ans:There are mainly three asymptotic notations:
Big-O notation
Omega notation
Theta notation
Big-O Notation (O-notation)
Big-O notation represents the upper bound of the running time of an algorithm. Thus,
it gives the worst-case complexity of an algorithm.
Omega Notation (Ω-notation)
Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best case complexity of an algorithm.
Theta Notation (Θ-notation)
Theta notation encloses the function from above and below. Since it represents the upper
and the lower bound of the running time of an algorithm, it is used for analyzing the average-
case complexity of an algorithm.
10. Identify the disadvantages of AVL Trees and advantages of B-Trees?
Disadvantages of Avl:
1. It is difficult to implement compared to normal BST and easier compared to Red Black
2. Less used compared to Red-Black trees.
3. Due to its rather strict balance, AVL trees provide complicated insertion and removal
operations as more rotations are performed.
Advantages of B-trees:B-trees have several advantages over other data structures for
storing and retrieving large amounts of data. Some of the key advantages of B-trees include:
● Sequential Traversing: As the keys are kept in sorted order, the tree can be traversed
sequentially.
● Minimize disk reads: It is a hierarchical structure and thus minimizes disk reads.
● Partially full blocks: The B-tree has partially full blocks which speed up insertion and
deletion.
11. Write any 5 applications of heap tree?
1. Priority Queues: Heaps are commonly used to implement priority queues, where elements
with higher priority are extracted first. This is useful in many applications such as scheduling
tasks, handling interruptions, and processing events.
2. Sorting Algorithms: Heap sort, a comparison-based sorting algorithm, is implemented using
the Heap data structure. It has a time complexity of O(n log n), making it efficient for large
datasets.
3. Graph algorithms: Heaps are used in graph algorithms such as Prim’s Algorithm, Dijkstra’s
algorithm., and the A* search algorithm.
4. Lossless File Compression: Heaps are used in data compression algorithms such as Huffman
coding, which uses a priority queue implemented as a min-heap to build a Huffman tree.
5. Medical Applications: In medical applications, heaps are used to store and manage patient
information based on priority, such as vital signs, treatments, and test results.
12. Define a graph? Write any 5 applications of graphs?
A graph is a non-linear data structure, a collection of nodes connected to each other via
edges. Each node contains a data field and the edges act as an interaction between two data
fields.
1. Computer Science
● Graphs are used to define the flow of computation.
● Graphs are used to represent networks of communication.
2. Electrical Engineering
In Electrical Engineering, graph theory is used in designing of circuit connections. These circuit
connections are named as topologies. Some topologies are series, bridge, star and parallel
topologies.
3. Physics and Chemistry
● In physics and chemistry, graph theory is used to study molecules.
● The 3D structure of complicated simulated atomic structures can be studied
quantitatively by gathering statistics on graph-theoretic properties related to the topology
of the atoms.
4. Computer Network
● In computer network, the relationships among interconnected computers within the
network, follow the principles of graph theory.
● Graph theory is also used in network security.
[Link]
● Graphs are used to represent the routes between the cities. With the help of tree that is a
type of graph, we can create hierarchical ordered information such as family tree.
13. Explain about convex Hull? Write its types?
The convex hull of a set of points in a Euclidean space is the smallest convex polygon
that encloses all of the points. In two dimensions (2D), the convex hull is a convex polygon, and
in three dimensions (3D), it is a convex polyhedron. The below image shows a 2-D convex
polygon:
14. Write about divide and conquer with example?
1. Divide:
● Break down the original problem into smaller subproblems.
● Each subproblem should represent a part of the overall problem.
● The goal is to divide the problem until no further division is possible.
2. Conquer:
● Solve each of the smaller subproblems individually.
● If a subproblem is small enough (often referred to as the “base case”), we solve it directly
without further recursion.
● The goal is to find solutions for these subproblems independently.
3. Combine:
● Combine the sub-problems to get the final solution of the whole problem.
● Once the smaller subproblems are solved, we recursively combine their solutions to get the
solution of larger problem.
● The goal is to formulate a solution for the original problem by merging the results from the
subproblems.
15. Write briefly about greedy method?
The greedy method never alters the earlier choices, thus making it more efficient in terms
of memory. This technique prefers memorization due to which the memory complexity
increases, making it less efficient. Greedy techniques are faster than dynamic
programming. Dynamic programming is comparatively slower.
16. Write briefly about string editing?
The idea is to process all characters one by one starting from either from left or right
sides of both strings. Let us process from the right end of the strings, there are two possibilities
for every pair of characters being traversed, either they match or they don’t match. If last
characters of both string matches then we simply recursively calculate the answer for rest of part
of the strings. When last characters do not match, we perform all three operations to match the
last characters, i.e. insert, replace, and remove. We then recursively calculate the result for the
remaining part of the string. Upon completion of these operations, we will select the minimum
answer and add 1 to it.
17. Define an all pair shortest path? Give any example graph?
The all pair shortest path algorithm is also known as Floyd-Warshall algorithm is used to find all
pair shortest path problem from a given weighted graph. As a result of this algorithm, it will
generate a matrix, which will represent the minimum distance from any node to all other nodes in the
graph.
18. Explain about an optimal binary search tree?
The optimal binary search tree problem is to construct a binary search tree on these n
keys that minimizes the expected access time. One variant of this problem is when only the gaps
have nonzero access probabilities, and is called the optimal alphabetic tree problem.
In computer science, an optimal binary search tree (Optimal BST), sometimes called a
weight-balanced binary tree, is a binary search tree which provides the smallest possible search
time (or expected search time) for a given sequence of accesses (or access probabilities).
19. Define a graph coloring? write about graph coloring?
A graph coloring is an assignment of labels, called colors, to the vertices of a graph such
that no two adjacent vertices share the same color. The chromatic number χ(G) of a graph G is
the minimal number of colors for which such an assignment is possible.
20. Define Back tracking? Write Briefly about 0/1 knapsack in backtracking?
Backtracking is an algorithmic technique whose goal is to use brute force to find all
solutions to a problem. It entails gradually compiling a set of all possible solutions. Because a
problem will have constraints, solutions that do not meet them will be removed.
In 0/1 Knapsack Problem, As the name suggests, items are indivisible here. We cannot
take the fraction of any item. We have to either take an item completely or leave it completely.
21. Define Branch and Bound technique?
The Branch and Bound Algorithm is a method used in combinatorial optimization
problems to systematically search for the best solution. It works by dividing the problem into
smaller subproblems, or branches, and then eliminating certain branches based on bounds on the
optimal solution. This process continues until the best solution is found or all branches have been
explored. Branch and Bound is commonly used in problems like the traveling
salesman and job scheduling.
22. Write about a complete graph and clique with example?
A complete graph is a graph in which every pair of vertices is adjacent. A complete
subgraph of graph G will be called a clique. A clique is not necessarily a maximal complete
subgraph. A clique will sometimes be written as an unordered set of vertices.
A clique is a subgraph of a graph such that all the vertices in this subgraph are connected
with each other that is the subgraph is a complete graph. The Maximal Clique Problem is to find
the maximum sized clique of a given graph G, that is a complete graph which is a subgraph of G
and contains the maximum number of vertices. This is an optimization problem.
Correspondingly, the Clique Decision Problem is to find if a clique of size k exists in the given
graph or not.
23. Define chromatic number decision problem?
The minimum number of colors needed to color a graph is called its chromatic number.
For example, the following can be colored a minimum of 2 colors.
Example of Chromatic Number
The problem of finding a chromatic number of a given graph is NP-complete.
Graph coloring problem is both, a decision problem as well as an optimization problem.
● A decision problem is stated as, “With given M colors and graph G, whether a such color
scheme is possible or not?”.
● The optimization problem is stated as, “Given M colors and graph G, find the minimum
number of colors required for graph coloring.”
24. Write about a non deterministic algorithm?
exists no set of choices
leading to a success signal.
Whenever, there is a set of
choices that leads to a
successful completion,
then one such set of
choices is
selected and the algorithm
terminates successfully.
In case the successful
completion is not possible,
then the complexity is
O(1).
In case of successful signal
completion then the time
required is the minimum
number of steps needed to
reach a successful
completion of O(n) where n
is
the number of inputs.
The problems that are
solved in polynomial time
are called tractable
problems
and the problems that
require super polynomial
time are called non-
tractable
problems. All deterministic
polynomial time algorithms
are tractable and the
non-deterministic
polynomials are
intractable.
A nondeterministic
algorithm is considered
as a superset for
deterministic
algorithm i.e., the
deterministic algorithms
are a special case of
nondeterministic
algorithms.
Example1: A non-
deterministic algorithm for
searching an element X in
the
given set of elements
A[1:n] in the time
complexity O(1).
A non-deterministic
algorithm terminates
unsuccessfully if and only if
there
exists no set of choices
leading to a success signal.
Whenever, there is a set of
choices that leads to a
successful completion,
then one such set of
choices is
selected and the algorithm
terminates successfully.
In case the successful
completion is not possible,
then the complexity is
O(1).
In case of successful signal
completion then the time
required is the minimum
number of steps needed to
reach a successful
completion of O(n) where n
is
the number of inputs.
The problems that are
solved in polynomial time
are called tractable
problems
and the problems that
require super polynomial
time are called non-
tractable
problems. All deterministic
polynomial time algorithms
are tractable and the
non-deterministic
polynomials are
intractable.
A nondeterministic
algorithm is considered
as a superset for
deterministic
algorithm i.e., the
deterministic algorithms
are a special case of
nondeterministic
algorithms.
Example1: A non-
deterministic algorithm for
searching an element X in
the
given set of elements
A[1:n] in the time
complexity O(1).
To implement a non-deterministic algorithm, we have a couple of languages like Prolog but
these don’t have standard programming language operators and these operators are not a part of
any standard programming languages. Some of the terms related to the non-deterministic
algorithm are defined below:
● choice(X): chooses any value randomly from the set X.
● failure(): denotes the unsuccessful solution.
● success(): The solution is successful and the current thread terminates.
Example :
Problem Statement : Search an element x on A[1:n] where n>=1, on successful search return j if
a[j] is equals to x otherwise return 0.
Non-deterministic Algorithm for this problem :
1.j= choice(a, n)
[Link](A[j]==x) then
{
write(j);
success();
}
[Link](0); failure();
25. Write briefly about cook’s theorem?
Stephen Arthur Cook and L.A. Levin in 1973 independently proved that the satisfiability
problem(SAT) is NP-complete. Stephen Cook, in 1971, published an important paper titled ‘The
complexity of Theorem Proving Procedures’, in which he outlined the way of obtaining the proof
of an NP-complete problem by reducing it to SAT. He proved Circuit-SAT and 3CNF-
SAT problems are as hard as SAT.
Given a boolean expression F having n variables x1,x2,….,xn, and Boolean operators, is it
possible to have an assignment for variables true or false such that binary expression F is true?
This problem is also known as the formula – SAT. An SAT(formula-SAT or simply
SAT) takes a Boolean expression F and checks whether the given expression(or formula) is
satisfiable. A Boolean expression is said to be satisfactory for some valid assignments of
variables if the evaluation comes to be true. Prior to discussing the details of SAT, let us now
discuss some important terminologies of a Boolean expression.
● Boolean variable: A variable, say x, that can have only two values, true or false, is called a
boolean variable
● Literal: A literal can be a logical variable, say x, or the negation of it, that is x or x̄ ; x is
called a positive literal, and x̄ is called the negative literal
● Clause: A sequence of variables(x1,x2,….,xn) that can be separated by a logical OR operator
is called a clause. For example, (x1 V x2 V x3) is a clause of three literals.
● Expressions: One can combine all the preceding clauses using a Boolean operator to form an
expression.
● CNF form: An expression is in CNF form(conjunctive normal form) if the set of clauses are
separated by an AND (^), operator, while the literals are connected by an OR (v) operator.
o f = (x1 V x̄ 2 V x3) ∧ (x1 V x̄ 3 V x2)
The following is an example of an expression in the CNF form:
● 3 – CNF: An expression is said to be in 3-CNF if it is in the conjunctive normal form, and
every clause has exact three literals.