a) Define time complexity and space complexity

->Time Complexity: Time complexity is the measure of the time taken by an algorithm to execute
according to the input size n.
Space Complexity: Space complexity is the measure of the total memory space required by an
algorithm during execution.
b) What do you mean by divide and control strategy?
->Divide and Conquer Strategy:
It is an algorithm design technique in which a problem is divided into smaller subproblems, each
subproblem is solved separately, and their solutions are combined to get the final solution.
Example: Merge Sort, Quick Sort.
c) Consider 4 programs with the length 15, 5, 20, 8 respectively are to be stored on a computer
tape. Find MRT using greedy method.
-> Program lengths: 15, 5, 20, 8
Using Greedy Method, arrange programs in ascending order: 5, 8, 15, 20
Waiting times:
P1 = 5
P2 = 5 + 8 = 13 P3 = 5 + 8 + 15 = 28
P4 = 5 + 8 + 15 + 20 = 48

MRT= 94/4 =23.5 ∴ Minimum Retrieval Time (MRT) = 23.5 units.

Total Retrieval Time = 5 + 13 + 28 + 48 = 94

d) Principle of Optimality: It states that an optimal solution of a problem contains optimal

solutions to its subproblems.
e) N-Queen’s Problem:- The N-Queen’s problem is to place N queens on an N×N chessboard such
that no two queens attack each other.
f) P and NP Class:- P Class: Problems that can be solved in polynomial time by a deterministic
algorithm.
NP Class: Problems whose solutions can be verified in polynomial time.
a) List all asymptotic notations.
->1. Big Oh O, [Link] Ω, [Link] Θ, [Link] oh o, 5 Little omega ω
b) Control Abstraction for Divide and Conquer
[Link] the problem into smaller subproblems., [Link] subproblems recursively., [Link]
solutions to get final solution.
c) Feasible Solution and Optimal Solution.
Feasible Solution: A solution that satisfies all constraints of the problem.
Optimal Solution: The best feasible solution among all possible solutions.
d) Principle of Optimality.
-> It states that an optimal solution contains optimal solutions to its subproblems.
e) Live Node and Dead Node
-> Live Node: A node that may produce further child nodes.
Dead Node: A node that cannot produce any further child nodes.
f) Non-deterministic Algorithm.
-> A non-deterministic algorithm can choose one of many possible moves at each step to reach the
solution.
a) Write an algorithm for binary search algorithm. State its best case, average case and worst
case time complexity.
-> Binary Search Algorithm
Binary Search is used to search an element in a sorted array.
Algorithm:
1. Set low = 0 and high = n-1, 2. Find middle element
mid= low+high/2, 3. If A[mid] = item, element is found.
4. If item < A[mid], search left half., 5. If item > A[mid], search right half.
6. Repeat until element is found or low > high.
Time Complexity. Best Case: O(1)
Average Case: O(logn). Worst Case: O(logn).
a) Define Huffman Coding Problem and give algorithm to find Huffman
code.
-> Huffman Coding Problem
Huffman Coding is a greedy method used for data compression. It assigns shorter binary codes to
frequently used characters and longer codes to less frequent characters to reduce storage space.
Algorithm for Huffman Coding
[Link] a leaf node for each character with its frequency.
[Link] all nodes into a priority queue.
[Link] two nodes with minimum frequency.
[Link] a new node with these two nodes as children and frequency equal to their sum.
[Link] the new node back into the queue.
[Link] steps 3 to 5 until only one node remains.
[Link] the tree:
Left edge → 0
Right edge → 1
Dijkstra’s Algorithm Bellman-Ford Algorithm
Used to find shortest path from source vertex. Also used to find shortest path from source vertex.
Does not work with negative edge weights. Works with negative edge weights.
Faster algorithm. Slower than Dijkstra’s algorithm.
Time Complexity: O(V2)O(V^2)O(V2) Time Complexity: O(VE)O(VE)O(VE)
Uses greedy approach. Uses dynamic programming approach.
d) Define Satisfiability Problem. Write non-deterministic problem for the same.
Satisfiability Problem (SAT)
The satisfiability problem is to determine whether there exists an assignment of truth values to
variables such that a given Boolean formula becomes TRUE.
Non-Deterministic Algorithm for SAT
1. Assign TRUE or FALSE values to variables non-deterministically.
2. Evaluate the Boolean expression.
3. If the expression becomes TRUE, return SATISFIABLE. Otherwise, return NOT SATISFIABLE.

c) What do you mean by Articulation point? Write algorithm to find all possible articulation point
in the given graph.
-> An articulation point is a vertex in a graph whose removal increases the number of connected
components in the graph.
Algorithm to Find Articulation Points:
1. Start DFS traversal from any vertex., 2. Mark each visited vertex.
[Link] discovery time and low value of each vertex. 4. A vertex is an articulation point if:
It is the root node with more than one child.
It is a non-root node and no back edge exists from its child to its ancestor.
[Link] all articulation points..
d) Define Satisfiability Problem. Write non-deterministic problem for the same.
->The satisfiability problem is to determine whether a Boolean expression can be made TRUE by
assigning suitable truth values to variables.
Non-Deterministic Algorithm for SAT
[Link] TRUE or FALSE values to variables non-deterministically.
[Link] the Boolean expression.
[Link] expression becomes TRUE, return SATISFIABLE.
[Link] return NOT SATISFIABLE.
a) Knapsack Problem
The Knapsack problem is to select items with given weights and profits so that total profit is
maximum without exceeding the knapsack capacity. Methods to Find Feasible Solutions
[Link] Method by Profit – Select items with highest profit first. [Link] Method by Weight –
Select items with minimum weight first. [Link] Method by Profit/Weight Ratio – Select items
with highest
weight/profit ratio first.
b) Bellman Ford Algorithm
Bellman Ford Algorithm is used to find the shortest path from a source vertex to all other vertices
in a graph with possible negative edge weights.
Algorithm [Link] distance of source vertex as 0 and others as infinity.
[Link] all edges repeatedly for V−1 times.
[Link] for negative weight cycles.
[Link] shortest distances.
c) Definitions
*Tree Edge: Edge included in DFS traversal tree. *Back Edge: Edge from a node to its ancestor.
*Forward Edge: Edge from a node to its descendant. *Cross Edge: Edge between two different
subtrees.
P Class NP Class
Problems solved in polynomial time. Problems verified in polynomial time.
Uses deterministic algorithm. Uses non-deterministic algorithm.
Easier to solve. Harder to solve.

a) Define time complexity. List asymptotic notations.

->Time complexity is the measure of the time required by an algorithm to execute according to
input size n.
Asymptotic Notations
[Link] Oh O, [Link] Ω, [Link] Θ
[Link] oh o, [Link] omega ω.
b) Merge Sort is not an In-place Algorithm.
-> Merge sort requires extra memory for merging subarrays. Hence, it is not an in-place algorithm.

-> MRT=107/5=21.4 ∴ Minimum Retrieval Time = 21.4 units.

c) Consider 4 programs with the length 14, 5, 20, 8, 3,. MRT.

d) What is negative weighted cycle? Does Flyod Warshall algorithm consider the negative
weighted cycle?
->A negative weighted cycle is a cycle in a graph whose total edge weight is negative.
Yes, Robert Floyd-Warshall algorithm can detect negative weighted cycles.
e) What do you mean by branch and bound? Where this technique might be useful.
-> Branch and Bound is a problem-solving technique used to find optimal solutions by dividing
problems into subproblems and eliminating unnecessary solutions using bounds.
Applications: Traveling Salesman Problem, Knapsack Problem, Job Scheduling Problem.
a) What is Divide & Conquer strategy? Explain Binary Search algorithm and State worst time
complexity.
->Divide and Conquer is an algorithm design technique in which a problem is divided into smaller
subproblems, each subproblem is solved recursively, and their solutions are combined to get the
final solution.
Binary Search Algorithm
Binary Search is used to search an element in a sorted array.
Algorithm
[Link] middle element of array.
[Link] middle element is equal to key, search is successful. [Link] key is smaller, search left half.
[Link] key is greater, search right half.
[Link] until element is found or search space becomes empty.
Worst Time Complexity: O(logn)
a) What is Huffman code? Obtain the set of optimal Huffman codes for the messages with
frequencies 6, 7, 9, 10, 12, 14, 22
->Huffman coding is a greedy method used for data compression. It assigns shorter binary codes to
frequently occurring symbols and longer codes to less frequent symbols.
Frequency Code
22 0
14 100
12 101
10 1100
9 1101
7 1110
6 1111

b) Define: Tree edge, Back Edge, Forward Edge, Cross Edge.

[Link] Edge: Edge included in DFS traversal [Link] Edge: Edge from a node to its
[Link] Edge: Edge from a node to its [Link] Edge: Edge connecting two
different subtrees.
c) Write non deterministic algorithm to sort set of 'n' positive integers.
[Link] a permutation of given integers.
[Link] whether numbers are in ascending [Link] sorted, output the permutation.
[Link] reject it.
d) String Editing Problem.
-> The string editing problem finds the minimum number of operations needed to convert one
string into another.
Operations are insertion, deletion, and substitution.
Recurrence Relation

DFS (Depth First Search) BFS (Breadth First Search)

Traverses graph depth wise. Traverses graph level wise.
Uses Stack or recursion. Uses Queue.
Visits one branch completely before another. Visits all adjacent nodes first.
Less memory required. More memory required.