Algorithms | Subject Wise Questions

Given problem is Subset-sum problem which required dynamic programming to solve So, Option B is Correct

Subset Sum Problem - Dynamic Programming
Given a set of Positive integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

For Example:
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
There is a subset (4, 5) with sum 9.

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
There is no subset that add up to 30.

The number of comparisons needed in the worst case by the merge sort algorithm will be m+n-1
Best case it is min(m, n) if we consider number of elements in one array is m and n in one array
Worst case it will take m+n-1 comparisons..when alternate element goes into 3rd array which is merged and sorted array.
Number of merges will be same in all cases which is M+N

Quick sort - In Quick sort, if the array is already sorted or if it is reverse sorted then it takes O(n²) and if array is not sorted then it will take o(nlogn).so it depend upon ordering of input.

Insertion sort - In Insertion sort if the array is already sorted then it takes O(n) and if it is reverse sorted then it takes O(n²) to sort the array.so it depend upon ordering of input.

Selection sort - The best and worst case performance of Selection is O(n²) only. it does not depend upon ordering of input.

Merge sort - In Merge sort best and worst time complexity o(nlogn). it dosent depend ordering of input. .like array is sorted or not.

Best[merge] = Worst[merge] and Best[selection] = Worst[selection]. Why aren't they equally good answers ?
The best and worst case performance of Selection is O(n²) only. But if the array is already sorted then less swaps take place. In merge sort, time complexity is O(nlogn) for all the cases and performance is affected least on the the order of input sequence.

Order of the algorithm for which below recurrence is applicable for the time complexity, is a constant,
T(n) = T(n−1)+T(n−2)−T(n−3) (Assume Sufficient Large n value)

T(n) = T(n−1)
   T(n)    = T(n)+T(n−2)−T(n−3)
   T(n−2)=T(n−3)
   '
   '
   '
   '
T(1)=T(2)=T(3)

Transitive closure can be found by Floyd Warshall's algorithm in O(n³)

Warshall's Algorithm
Warshall's algorithm uses the adjacency matrix to find the transitive closure of a directed graph.

Transitive closure
The transitive closure of a directed graph with n vertices can be defined as the n-by-n boolean matrix T, in which the element in the ith row and jth column is 1 if there exist a directed path from the ith vertex to the jth vertex, otherwise it is zero.

For operational control is Detailed
For strategic planning is Aggregate

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning.

The algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray. Clearly, it is a greedy approach to sort the array.

Example
arr[] = 64 25 12 22 11
# Placing the minimum element in arr[0...4] in the beginning
11 25 12 22 64

# Placing the minimum element in arr[1...4] in the beginning
11 12 25 22 64

# Placing the minimum element in arr[2...4] in the beginning
11 12 22 25 64

# Placing the minimum element in arr[3...4] in the beginning
11 12 22 25 64

Click on the image to zoom

Binary Search is applied on the sorted array or list of large size. It's time complexity of O(log n) makes it very fast as compared to other sorting algorithms. The only limitation is that the array or list of elements must be sorted for the binary search algorithm to work on it.

Worst-case performance = O(log n)
Best-case performance = O(1)
Average performance = O(log n)
Worst-case space complexity = O(1)

The Fibonacci Sequence is the series of numbers :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The next number is found by adding up the two numbers before it:

• the 2 is found by adding the two numbers before it (1+1),
• the 3 is found by adding the two numbers before it (1+2),
• the 5 is (2+3),
• and so on!

• 3-SAT is NP Complete Problem
• 2-SAT is P Class Problem

Refer this link for more information : http://cstheory.stackexchange.com/questions/6864/why-is-2sat-in-p

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Binary Search is a linear searching algorithm and takes O(log n) when array is sorted.
T(n) = T(n / 2) + k , where k is constant produces a complexity of O(log n)


Recurrence Relation Derivation

Time complexity is - O(log N)
Recurrence relation - T(n)=T(n/2)+1

T(n)=T(n/2) + 1
T(n/2)=T(n/4) + 1 ……
[ T(n/4)= T(n/2^2) ]

T(n/4)=T(n/8) + 1 ……
[ T(n/8)= T(n/2^3) ]
.
.
kth step=> T(n/2^k-1)=T(n/2^k) + 1*(k times)
Adding all the equations we get, T(n) = T(n/2^k) + k times 1 _____eq(final)
=> n/2^k= 1 [So how many times we need to divide by 2 until we have only one element left]
=> n=2^k
=> log n=k [taken log(base 2) on both sides ]
Put k= log n in eq(final)
T(n) = T(1) + log n
T(n) = 1 + log n [we know that T(1) = 1 ,
because it’s a base condition as we are left with only one element in the array and that is the element to be searched so we return 1]
T(n) = O(log n) [taking dominant polynomial, which is n here)

In-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is O(log n), though sometimes anything in o(n) (Smaller than linear) is allowed

Selection Sort is an in-place algorithm having minimum number of swaps. It works on greedy approach and takes O(n) swaps to sort the array of n elements.

Number of swaps in Worst-case scenario

• Quick sort = O(n²)
• Insertion sort = О(n²)
• Selection sort = O(n)
• Heap sort = O(n logn)

Selection sort always performs O(n) swaps, while insertion sort performs O(n²) swaps in the average and worst case.
Selection sort is preferable if writing to memory is significantly more expensive than reading.

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. Because it only uses comparisons to operate on elements, it is a comparison sort.

1 :8,7,22,9,31,5,13
2 :8,7,9,22,31,5,13
3 :8,7,9,22,5,31,13
4 :8,7,9,22,5,13,31 = This will take 4 swaps
5 :7,8,9,22,5,13,31
6 :7,8,9,5,22,13,31
7 :7,8,9,5,13,22,31 = This will take 3 swaps
8 :7,8,5,9,13,22,31 = This will take 1 swaps
9 :7,5,8,9,13,22,31 = This will take 1 swap
10 :5,7,8,9,13,22,31 = This will take 1 swap
Total 10 swaps are required to sort the array.

Prim’s Algorithm : Prim’s Algorithm is used to the Minimum Spanning Tree (MST) of a given graph. To apply Prim’s algorithm, the given graph must be weighted, connected and undirected.
Dijikstra’s Algorithm : Dijikstra’s Algorithm is used to find the shortest path from source to all the other nodes in a weighted graph.
BellmanFord’s Algorithm :BellmanFord’s Algorithm is used to find the shortest distance from source to all other nodes in a graph that can contain negetive weight edges.
Floyd-Warshall’s Algorithm : Floyd Warshall’s Algorithm is used for solving All-pair-shortest path problems. It means the algorithm is used for finding the shortest paths between all pairs of vertices in a graph.

Transitive closure can be found by Floyd Warshall's algorithm in O(n³)

Warshall's Algorithm
Warshall's algorithm uses the adjacency matrix to find the transitive closure of a directed graph.

Transitive closure
The transitive closure of a directed graph with n vertices can be defined as the n-by-n boolean matrix T, in which the element in the ith row and jth column is 1 if there exist a directed path from the ith vertex to the jth vertex, otherwise it is zero.

Foyd Warshall algorithm is used to find All Pairs Shortest Path problem which uses Dynamic Programming to find the shortest path between all the pairs of vertices in a weighted graph. This algorithm works for both the directed and undirected weighted graphs. But, it does not work for the graphs with negative cycles (where the sum of the edges in a cycle is negative).

Floyd-Warhshall algorithm is also called as Floyd's algorithm, Roy-Floyd algorithm, Roy-Warshall algorithm, or WFI algorithm.
-This algorithm follows the dynamic programming approach to find the shortest paths.

Selection sort does the same number of comparisons no matter what the initial order is.That ALWAYS uses n(n-1)/2 comparisons.
So, for length 5,

5*4/2 = 20/2 = 10 Comparisons

Example: 5 4 3 2 1
1st iteration i will compare 4 number with the 5
2nd iteration i will compare 3 numbers with the 4
3rd iteration i will compare 2 number2 with the 3
4th iteration i will compare 1 number with the 2

so the total number of comparisons is 4+3+2+1 = 10
which can be views as the sum of the sequence of the first (n-1) numbers starting by 1
S = ((1+ (n-1) ) * (n-1) ) / 2
S=n(n-1)/2 comparisons.

T(n)=2T(n−1)
T(n) = 2[2T(n−2)]
T(n) =2²T(n−2)
T(n)=2²[2T(n−3)]
T(n)=2³T(n−3)
T(n)= 2^kT(n−k)
n−k=0, n=k, T(0)=1
T(n)=2ⁿ

Strassen matrix multiplication uses Divide and Conquer technique to reduce the complexity of matrix multiplication.

Insertion sort uses decrease and conquer approach as its loop invariant condition is at each step, A[1..j-1] contains the first j-1 elements in sorted order.

Gaussian elimination uses transform and conquer approach to solve set of equations.

Foyd Warshall algorithm is used to find All Pairs Shortest Path problem which uses Dynamic Programming to find the shortest path between all the pairs of vertices in a weighted graph.

Sequential search: Searching an element in an array, the search starts from the first element till the last element.

The average number of comparisons in a sequential search is (N+1)/2 where N is the size of the array.

-If element is at 1 position then it requires 1 comparison.
-If element is at 2 position then it requires 2 comparison.
-If element is at 3 position then it requires 3 comparison.
-Similarly , If element is at n position then it requires n comparison.

Total comparison
= n(n+1)/2

For average comparison
= (n(n+1)/2) / n
= (n+1)/2

Quicksort algorithm based on divide and conquer approach in which the array is split into subarrays and these sub-arrays are recursively called to sort the elements.

Let n=2^m
T(n)=2T(√n)+1
T(2^m)=2T(2^m/2)+1
Let T(2^m)=s(m)
s(m)=2s(m/2)+1

By Using case 1 of master method
S(m)=Θ(m)
S(m) =Θ(logn) [∴ n=2^m]

∴ T(n)=T(2^m)=s(m)=Θ(logn)

Symbol table is implemented as a sequential search table. So, every time one has to search entire table.

In case of unsuccessful search, the element would be searched until the last element and it would be a worst case when number of searches are equal to the size of the table. so it shoulb be L only.

-In sequential search Successful search needs (L+1)/2,
-In sequential search Unsuccessful search needs L

T(n + 1) = 2n + T(n) for all integers n ≥ 1
T(n + 1) = 2n + (2(n-1) + T(n-1)) ∴ [By using substitution method]
T(n + 1) = 2n + (2(n-1) + (2(n-2) + T(n-2)))
T(n + 1) = 2n + (2(n-1) + (2(n-2) + (2(n-3) + T(n-3))))
T(n + 1) = 2n + 2(n-1) + 2(n-2) + 2(n-3)......2(n-(n-1) + T(1))
T(n + 1) = 2n + 2n - 2 + 2n - 4 + 2n - 6 +.... + 10
T(n + 1) = 2[n + n + n + ...] - 2[1 + 2 + 3 +...]
T(n + 1) = 2[n*n] - 2[n(n+1)/2]
T(n + 1) = 2[n*n] - [n*n + n]
T(n + 1) = n*n - n
T(n + 1) = O(n²)

Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being Ο(n log n)

Merge sort first divides the array into equal halves and then combines them in a sorted manner.

According to the question

1. Insertion sort (n) , Quick sort( n logn)
2. Quick sort (n logn), Quick sort(n logn)
3. Quick sort (n logn)), Insertion sort(n²)
4. Insertion sort (n), Insertion sort(n²)

So, we can conclude option(A) is correct

Consider an sorted array of 11 element
1 2 3 4 5 6 7 8 9 10 11
For convenience we are using Binary search tree. Now apply binary search in the given array .
For first element (which is root) array will be
(1  2   3   4   5   )  6  (7   8   9   10   11)

Now binary search continue either in lower or in upper halve for searching .
For lower halve (1   2)  3   (4   5 ).

For upper halve (7   8  )  9  (10   11  ) and continued in same way.


So to search middle element (i.e 6  ) it will take 1 comparison .For 3  or 9  it will take 2 comparison .For 2 , 3 comparison and so on.

Avg No of comparison = ( 1+(2+2)+(3+3+3+3)+(4+4+4+4) ) / 11=3

 Masters theorem
T(n) = a T(n/b) + Θ(n^k log^p n)  where a > = 1,
b > 1, k > = 0 , and p is real number

Case 1: if a > b^k, Then T(n) =Θ(n^(log_ba))

Case 2: a = b^k
a) if p > -1, Then T(n) = Θ( n^(log_ba)log^(p+1)n)
b) if p = -1, Then T(n) = Θ( n^(log_ba)loglogn)
c) if p < -1, Then T(n) = Θ( n^(log_ba))

Case 3: a < b^k,
a)  if p > =0, then T(n) = Θ(n^k log^p n))
b) if p<0 then T(n) = Θ(n^k)


Given 
T(m) = T(3m/4) + 1
T(m) = T(m/(4/3)) + 1

In this problem we use Master’s Theorem:
T(m) = aT(m/b) + n^k log^p n
which is similar to
T(m) = 1 * T(m/(4/3)) + 1 * n⁰ log⁰ n
where a = 1, b = 4/3, k = 0 and p = 0

By using case 2 of Master's Theorem
a = 1 = b⁰ = b^k
∴ a=b^k

p > -1 means apply case 2(a) of Master's Theorem

∴ T(m) = θ( m^(log_ba)log^(p+1)m)
where  a=1, b=4/3, k=0 and p=0
∴ T(m) = θ( m^(log_4/31)log⁽⁰⁺¹⁾m)    (∴  log_4/31 = 0 )
∴ T(m) = θ( m⁰log¹m)
∴ T(m) = θ(log m)

Given Probability  :
A → 0.08
B → 0.40
C → 0.25
D → 0.15
E → 0.12


Now Draw a Huffman tree:


length for each character = no of bits * frequency of occurrence:
Length of A = 1110 = 4 * 0.08 = 0.32
Length of B = 0 = 1 * 0.4 = 0.4
Length of C = 10 = 2 * 0.25 = 0.5
Length of D = 110 = 3 * 0.15 = 0.45
Length of E = 1111 = 4 * 0.12 = 0.48

Now add these length to find Average length:
Average length = 0.32 + 0.4 + 0.5 + 0.45 + 0.48 = 2.15

• If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is called a strictly binary tree.
• A strictly binary tree with n leaves always contains 2n -1 nodes.

• If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary tree are of degree zero or two, never degree one.

Now we have 19 leaves, Therefore (2 x 19) - 1 = 38 - 1 = 37  nodes

• If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is called a strictly binary tree.
• A strictly binary tree with n leaves always contains 2n -1 nodes.

• If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary tree are of degree zero or two, never degree one.

Now we have 19 leaves, Therefore (2 x 19) - 1 = 38 - 1 = 37  nodes

1. 8-Queens‏‏ Problem is ‎Backtracking.
2. Single-Source shortest‏‏‎ Paths‏‏‎ is Greedy‏‏‎ approach.‏‏‎
3. STRASSEN’s Matrix‏‏‎ Multiplication‏‏‎ is ‏‏‎ Divide‏‏‎ and‏‏‎ conquer‏‏‎ technique.‏‏‎
4. Optimal Binary‏‏‎ Search‏‏‎ trees‏‏‎ is Dynamic‏‏‎ programming.

• An octal number is a type of number that is composed of 8 possible values (0 to 7).
• But in this Questions They are saying 5 Digit octal Number possible values (0 to 4) it means Number of Digits is 5

Maximum comparisons = (Digits) x (Type of Number) x (Number of values)
where
  Digits =5,
  Type of Number(Base Value) =8 ,
  Number of values=9

Therefore Maximum Number of comparisons are = 5* 8 * 9 = 360

For an k-ary tree where each node has k children or no children,
following relation holds
L = (k-1)*n + 1

Where
     L is the number of leaf nodes
    n is the number of internal nodes.
since its a complete k tree, so every internal node will have K child

Given
     k = 5
    Number of internal nodes n = 8
    Number of leaf nodes = (k-1)*n + 1
                                           = (5-1)*8 + 1
                                            = 4 * 8 + 1
                                            = 33

Ford-Fulkerson has a complexity of O(|E|.f^* ), where f^∗ is the maximum flow of the network. The Ford-Fulkerson algorithm was eventually improved upon by the Edmonds-Karp algorithm, which does the same thing in O(V²⋅E) time, independent of the maximum flow value

T(n)=2T(n−1)
T(n) = 2[2T(n−2)]
T(n) =2²T(n−2)
T(n)=2²[2T(n−3)]
T(n)=2³T(n−3)
T(n)= 2^kT(n−k)
n−k=0, n=k, T(0)=1
T(n)=2ⁿ

In Binary Max Heap, the smallest element will always be a leaf node either in left subtree or right subtree. So you have to traverse both left and right subtrees In each step you need traverse both left and right sub-trees in order to search for the minimum element. In effect, this means that you need to traverse all elements to find the minimum.

So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n)

Worst case
Worst-case time complexity for Binary Search tree operation occurs when the tree is a Skewed tree.i.e when tree goes only in one direction

In skewed Binary Search Tree (BST), all operations Search,update and delete can take O(n).


Best case,
The binary search tree is a balanced binary search tree.
Height of the binary search tree becomes log(n).
So, Time complexity of BST Operations = O(logn).

• Dijkstra's Algorithm is a single-source shortest path algorithm and aims to find solution to the given problem statement
• This algorithm works for both directed and undirected graphs
• It works only for connected graphs
• The graph should not contain negative edge weights
• The algorithm predominantly follows Greedy approach for finding locally optimal solution.
• The main logic of this algorithm is based on the following formula- dist[r]=min(dist[r], dist[q]+cost[q][r])

Merge Sort — nLogn
Bubble Sort — n²
Quick Sort — n²
Selection Sort — n²

10nlog₁₀n ≤ 0.0001n²
Let n‏‏‎ =‏‏‎ 10​ ^k​ records.‏‏‎ Then Substitute the Values in above condition
10×(10^k)log₁₀10^k ≤ 0.0001(10^k)²
10^k+1k ≤ 0.0001 × 10^2k
k ≤ 10^{2k−k−1−4}
k ≤ 10^k−5
5 doesn't satisfy this but 6 satisfies.
So ,Correct Answer is C

Backtracking is a general algorithm technique that consider searching every possible combination in order to solve an optimization problem.
Back tracking is an approach to problem solving which is usually applied to constraint satisfaction problem like puzzles.
The 4-Queens problem consist of placing four queens on a 4x4 chessboard such that no two queen’s capture the same column and same row and also, they should not be in the same diagonal.

A stable sorting algorithm ensures that items that are equal to each other aren't reordered during the sorting process.

An algorithm is said to be stable if two equal elements appear in the same order in output(sorted objects list) as they appear in input list(unsorted list)
For example - If we have 5 elements - 4, 7, 2, 8, 2
For our understanding, let’s rename sequence as 4, 7, 2(first occurrence), 8, 2(second occurrence) Then after sorting we will get 2, 2, 4, 7, 8 .But which 2 came first? Which 2 is this? 2(first occurrence) or 2(second occurrence) .If they are in the same order as input ,then such algorithms are called stable algorithm else unstable algorithm.

These sorting algorithms are usually stable

• counting sort
• merge sort
• insertion sort
• Bubble Sort
• Binary Tree Sort.

These sorting algorithms are usually unstable:

• quicksort
• heapsort
• selection sort

Refer : https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Bubble sort procedures is the slowest in all 3 cases

Recurrence relation for Towers of Hanoi
T(1)=1
T(n)=2T(n−1)+1

Kruskal’s Algorithm is used for finding the Minimum Spanning Tree (MST) of a given graph only when the given graph must be weighted, connected and undirected.

If the edges are already sorted, then there is no need to construct min heap.
So, deletion from min heap time is saved.
In this case, time complexity of Kruskal’s Algorithm = O(E + V)
where E edges and V vertices

10nlog₁₀n ≤ 0.0001n²
Let n‏‏‎ =‏‏‎ 10​ ^k​ records.‏‏‎ Then Substitute the Values in above condition
10×(10^k)log₁₀10^k ≤ 0.0001(10^k)²
10^k+1k ≤ 0.0001 × 10^2k
k ≤ 10^{2k−k−1−4}
k ≤ 10^k−5
5 doesn't satisfy this but 6 satisfies.
So ,Correct Answer is C

1. You have given n elements from 1 to n.
2. In BST(binary search tree), inorder traversal is always sorted ordered.

Algorithm to build binary tree from inorder and postorder traversal:

1. Take the last element from postorder as root element of binary tree. This takes O(1) time.
2. Perform binary search on given sequence 1 to n to find that element in inorder traversal. This takes O(log n) time.
3. Now divide inorder traversal using that element using pivot selection.
4. Repeat for both split part. This takes T(k) and T(n-k-1) time.

The recurrence relation would be T(n) = T(k) + T(n-k-1) + O(log n) = O(n log n). This is time complexity to build binary tree using inorder and postorder/preorder traversal.

As you have given that tree is binary search tree, so there is no need to perfrom binary search. Simply, we take pivot and split given list from 1 to n element. The recurrence relation would be T(n) = T(k) + T(n-k-1) + O(1) = O(n). O(n) time complexity to build binary search tree using inorder and postorder/preorder travarsal.

you can find Number of connected components in undirected graph by running a DFS or BFS
Its time complexity is Θ(m+n)

For example array {6, 7, 4, 3, 5, 2}, leaders are 7, 5 and 2.

Method 1 (Brute Force)
Use two loops. The outer loop runs from 0 to length – 1 and one by one picks all elements from left to right. The inner loop compares the picked element to all the elements to its right side. If the picked element is greater than all the elements to its right side, then the picked element is the leader.
Time Complexity: O(n*n)

Method 2 (Scan the array from right)
Start Traversing from the right side of the array, and keep the highest element in a variable,if we find any element greater then this variable print it and update the variable with the new value.
Time Complexity: O(n)

Branching factor 
The branching factor is the number of children at each node

Solution depth
The length of the shortest path from the initial node to a goal node.

Maximum depth
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.

Depth limit - The unbounded tree problem appeared in DFS can be fixed by imposing a limit on the depth that DFS can reach, this limit we will call depth limit.

• BFS →  O(b^d) worst case space complexity
• DFS → O(bm) worst case space complexity
• Depth - Limited Search → O(bl)
• Iterative deepening Search → O(bd)

Applying Kruskal's Algorithm then Weight of Minimum Spanning Tree(MST) is 16

2+1+2+1+3+4+2+1=16

 Dijkstra’s algorithm : Time Complexity: O(V²)
Case-1:
This case is valid when-

• The given graph G is represented as an adjacency matrix.
• Priority queue Q is represented as an unordered list.
• A[i,j] stores the information about edge (i,j).
• Time taken for selecting i with the smallest dist is O(V).
• For each neighbor of i, time taken for updating dist[j] is O(1) and there will be maximum V neighbors.
• Time taken for each iteration of the loop is O(V) and one vertex is deleted from Q.
• Thus, total time complexity becomes O(V²).

Case-2:
This case is valid when-

• The given graph G is represented as an adjacency list.
• Priority queue Q is represented as a binary heap.
• With adjacency list representation, all vertices of the graph can be traversed using BFS in O(V+E) time.
• In min heap, operations like extract-min and decrease-key value takes O(logV) time.
• So, overall time complexity becomes O(E+V) x O(logV) which is O((E + V) x logV) = O(ElogV)
• This time complexity can be reduced to O(E+VlogV) using Fibonacci heap.

Kruskal’s algorithm  :  Time Complexity: O(ElogE) or O(ElogV). Sorting of edges takes O(ELogE) time. After sorting, we iterate through all edges and apply find-union algorithm. The find and union operations can take atmost O(LogV) time. So overall complexity is O(ELogE + ELogV) time. The value of E can be atmost V^2, so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV)

 Floyd-Warshall algorithm:The Floyd-Warshall all-pairs shortest path runs in O(n³) time .This is because we have a triple (3) for loop, each with n iterations to make

 Topological sorting: The above algorithm is simply DFS with an extra stack. So time complexity is same as DFS which is O(V+E).

Let's take an Example :
Input : 1 2 3 4 5 6 7 8
output : 2 (2 is the second smallest number)


1 is the smallest, it took n-1 = 7 comparisons.
Now compare all the numbers which 1 was compared to (compare 2,3,5).


2 is the second smallest. It took log(n)-1 = 2 comparisons.

Hence,
N -1 + log(n)-1
= N + log(n)-2
= N + ceil(log n) – 2 ∴ [ when n odd]

If there is match then A[i, j] = A[i – 1, j  – 1] + 1
If there is no match then max(A[i – 1, j], A[i, j – 1])
longest Common Subsequence Table:

	X	0	1	2	1	3	0	1
Y	0	0	0	0	0	0	0	0
1	0	0	1	1	1	1	1	1
3	0	0	1	1	1	2	2	2
2	0	0	1	2	2	2	2	2
0	0	1	1	2	2	2	3	3
1	0	1	2	2	3	3	3	4
0	0	1	2	2	3	3	4	4

Therefore, length of longest common subsequence is 4

T(n)=2T(⎷n)+logn
T(n)=2T(n^1/2)+logn
put n=2^k
T(2^k)=2T((2^k)^1/2)+k
T(2^k)=2T(2^k/2)+k
put T(2^k)=S(k)
So S(k)=2S(k/2)+k
by Master Theorem
S(k)=O(k log k)
Hence T(n)=O(logn log logn)

• Bellman ford algorithm for single source shortest path - Dynamic Programming based
• Floyd Warshall for all pairs shortest paths  - Dynamic programming Based
• 0-1 knapsack problem - Dynamic Programming based
• Prim's Minimum Spanning Tree - Greedy Algorithm.

Maximum Sum Subarray Problem (Kadane’s Algorithm)
Given an array of integers, find contiguous subarray within it which has the largest sum.

Example
Input:  {-2, 1, -3, 4, -1, 2, 1, -5, 4}
 
Output: Subarray with the largest sum is {4, -1, 2, 1} with sum 6.

  We can easily solve this problem in linear time using kadane’s algorithm. The idea is to maintain maximum (positive sum) sub-array “ending” at each index of the given array. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous index.

The time complexity of Kadane’s Algorithm is O(n) and auxiliary space used by the program is O(1)

For each element x in array
Maximum shifts is bounded by O(d)
Therefore for n elements total complexity is bounded above by O(n*d)

Option(A) : False
Every minimum spanning tree of G must contain emin but "may or may not" e_max.
Kruskal's algorithm always picks the edges in ascending order of their weights while constructing a minimum spanning tree of G.First edge could never create a cycle.
Every minimum spanning tree of G "may or may not" contain e_max explained in option(c)

Option(B) : False
If emax is in a minimum spanning tree, then its removal must disconnect G "not always true".
e_max would be included in MST "if and only if , emax is a bridge between two connected components" , removal of which will surely disconnect the graph.

Option(C) : False
No minimum spanning tree contains emax
should be written as "may or may not", to be true.
Refer Case 1 in option (B)

Option(D) : False
G has a multiple minimum spanning trees
G has unique edge weights , so MST will be unique . In case if edge weights were repeating , there could've been a possibility of non-unique MSTs.

Minimum comparison is only possible when 1st and last element of either array are smaller then first element of another
so in such as case at each level we will have n/2 comparisons
In general they are
= n/2 * number of levels
=n/2 * log₂n
=(nlogn)/2
For n=2 only 1 comparison
For n=4 only 4 Comparison and so on

Tarjan's Algorithm is an efficient graph algorithm to find the strongly connected components in a directed graph in linear time by utilizing Depth First Search traversal of a graph. The key idea used is that nodes of strongly connected component form a subtree in the DFS spanning tree of the graph.

Time complexity:
The algorithm is built upon DFS and therefore, each node is visited once and only once. For each node, we perform some constant amount of work and iterate over its adjanceny list. Thus, the complexity is O(|V|+ |E|)
At maximum, the depth of recursion and the size of stack can be n nodes. Thus the complexity is O(|V|)

"If there is an NP-complete language L whose complement is in NP, then the complement of any language in NP is in NP."
This follows from the following three facts.
1)The complement of an NP-complete problem is co-NP-complete;
2)if any co-NP-complete problem is in a class C that is closed under polynomial-time reductions, then every co-NP⊆C;
3)NP is closed under polynomial-time reductions.

T(n) = T(n−1) + 1/n Given
T(n-1)= T(n−2) + 1/(n−1) substitute in above equation
T(n)=T(n-2)+ 1/(n-1) + 1/n
T(n)=T(n-3) + 1/(n-2) + 1/(n-1) + 1/n
T(n)=T(n-4) + 1/(n-3) + 1/(n-2) + 1/(n-1) + 1/n
'
'
'
'
'
T(n) =T(n-k) + 1/n-(k-1) + 1/n-(k-2) + 1/n-(k-3) + .........+1/n
Assume T(1) =1
Substitute k = n-1
T(n) =T(1) + 1/(n-(n-2)) + 1/(n-(n-3)) + 1/(n-(n-4)) + 1/(n-(n-5))+......+1/n
T(n)=1 + 1/2 + 1/3 + 1/4 + 1/5 +...........+1/n [Which is in Harmonic series]
Therefore T(n)=O(logn)

By using pointers we will easily access the large objects or structures and we can easly made any changes to the elements in the array it automatically reflect as these are pointed by the pointers.

Branching factor 
The branching factor is the number of children at each node

Solution depth
The length of the shortest path from the initial node to a goal node.

Maximum depth
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.

Depth limit - The unbounded tree problem appeared in DFS can be fixed by imposing a limit on the depth that DFS can reach, this limit we will call depth limit.

• BFS →  O(b^d) worst case space complexity
• DFS → O(bm) worst case space complexity
• Depth - Limited Search → O(bl)
• Iterative deepening Search → O(bd)

The degree of the tree is the total number of it's children i-e the total number nodes that originate from it. The leaf of the tree doesnot have any child so its degree is zero

It is given that:
The nodes with degree 1 is 4. ( 4 nodes having 1 child,therefore, degree = internal nodes + the root = 1+1=2)
The nodes with degree 2 is 3. ( 3 nodes having 2 child, therefore, degree = internal nodes + the root = 2+1=3)
The nodes with degree 3 is 3. ( 3 nodes having 3 children,therefore, degree = internal nodes + the root = 3+1=4)
1 root node with degree 3(number of children and because ternary and root has no parent --> degree == 3 + 0 = 3)

Let the number of leaf nodes be N. The degree of those leaf nodes is 1 because they are only attached to their parent.

Total number of nodes in tree = internal nodes + leafs node = 4 + 3 + 3 + N = 10 + N.

Therefore, the total number of edges = total number of nodes - 1 = 9+N.

For ternary trees: Sum of degrees of all vertices = 2*total number of edges.
(1*3) + (2*4) + (3*3) + (4*2) + (N*1) = 2(9+N)
3 + 8 + 9 + 8 + N = 18 + 2N
N = 10.

Applying Kruskal's Algorithm then Weight of Minimum Spanning Tree(MST) is 16

2+1+2+1+3+4+2+1=16

Let's take an Example :
Input : 1 2 3 4 5 6 7 8
output : 2 (2 is the second smallest number)


1 is the smallest, it took n-1 = 7 comparisons.
Now compare all the numbers which 1 was compared to (compare 2,3,5).


2 is the second smallest. It took log(n)-1 = 2 comparisons.

Hence,
N -1 + log(n)-1
= N + log(n)-2
= N + ceil(log n) – 2 ∴ [ when n odd]

If there is match then A[i, j] = A[i – 1, j  – 1] + 1
If there is no match then max(A[i – 1, j], A[i, j – 1])
longest Common Subsequence Table:

	X	0	1	2	1	3	0	1
Y	0	0	0	0	0	0	0	0
1	0	0	1	1	1	1	1	1
3	0	0	1	1	1	2	2	2
2	0	0	1	2	2	2	2	2
0	0	1	1	2	2	2	3	3
1	0	1	2	2	3	3	3	4
0	0	1	2	2	3	3	4	4

Therefore, length of longest common subsequence is 4

P: For a line with slope m>1, we should change the outer loop in line (4) to be over y. True
Q: Lines (10) and (12) update the decision variable d through an incremental evaluation of the line equation f.True
R: The algorithm fails if d is ever 0. False beacuse The algorithm works only if d is ever 0

T(n)=2T(⎷n)+logn
T(n)=2T(n^1/2)+logn
put n=2^k
T(2^k)=2T((2^k)^1/2)+k
T(2^k)=2T(2^k/2)+k
put T(2^k)=S(k)
So S(k)=2S(k/2)+k
by Master Theorem
S(k)=O(k log k)
Hence T(n)=O(logn log logn)

• 0/1 knapsack problem belongs to a class of "NP problems", which stands for “nondeterministic polynomial time."
• Fractional knapsack belongs to a class of "P class problem".

In general The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible

Refer : https://en.wikipedia.org/wiki/Knapsack_problem

The running time of the Quick Sort Algorithm depends on how the partition() method will split the input array
Since the partition() method depends on the pivot, we conclude that:
the value of the pivot will affect the performance of Quick Sort.

The Quick Sort algorithm performs the worst when the pivot is the largest or smallest value in the array
Reason:
When the pivot is the largest or smallest value in the array, the partition() step will do nothing to improve the ordering of the array elements

The Quick Sort algorithm performs the best when the pivot is the middle value in the array
Reason:
In the best case, the input array is divided into 2 arrays each containing approximately n/2 element

The performance of an algorithm can be analyzed by two important factors. Those are:

1. Space complexity : The amount of memory space an algorithm needs to run to completion
2. Time complexity : The amount of computer time an algorithm needs to run to completion

Refer : https://academyera.com/time-and-space-complexity

 Masters theorem
T(n) = a T(n/b) + Θ(n^k log^p n)  where a > = 1,
b > 1, k > = 0 , and p is real number

Case 1: if a > b^k, Then T(n) =Θ(n^(log_ba))

Case 2: a = b^k
a) if p > -1, Then T(n) = Θ( n^(log_ba)log^(p+1)n)
b) if p = -1, Then T(n) = Θ( n^(log_ba)loglogn)
c) if p < -1, Then T(n) = Θ( n^(log_ba))

Case 3: a < b^k,
a)  if p > =0, then T(n) = Θ(n^k log^p n))
b) if p<0 then T(n) = Θ(n^k)


Given
T(n) = T(n/2) + n
Which is similar to
T(n) = 1*T(n/2) + n¹ log⁰ n
a=1,b=2,k=1,p=0
Case 3 of master theorm a < b^k i.e,. 1 < 2¹
p > =0, then
T(n) = Θ(n^k log^pn))
T(n) = Θ(n¹ log⁰ n)
T(n) =Θ(n)

• Big O notation is one of the most fundamental tools for computer scientists to analyze the cost of an algorithm.
• Big-O is the upper, Big-Omega is lower-bound, and Big-Theta is bound by both sizes,

Given Weight = 8
as per the algorithms we took item which have high profit/weigh ratio
item 1 have high profit ration therfore we took item1 profit = 3 remaning weight 8-1 = 7
next item 2 high profit ratio therfore we took item2 profit = 5 remaning weight 7-2 = 5

now we have two options item 3 or 5 because they have same profit/weigt ratio but item 5 weight is 8 but our remeaining capacity is only 5 that's why dont pick item 5

if we pick item 3 profit = 9 remaning weight 5-4 = 1 (1 is wasted)
so we pick item 4 therfore item4 profit = 11 remaning weight 5-5 = 0
so we pick item 1,2,4 =3+5+11 =19
total pofit =19