U.G.C. NET Exam. 24 June, 2019 Paper–II (COMPUTER SCIENCE & APPLICATIONS)

Prim's Algorithm :-It is used to find the minimum spanning tree for a weighted undirected graph. It uses greedy approach to find the MST for a graph. Unlike the Kruskal's algorithm, we add vertex to growing spanning tree in this. It there are v vertices and E edges in the graph. Then time complexity to for MST is O(E log V)

Dijkstra's Algorithm :-
It is used to find the shortest path from source vertex to all other vertices in a graph. Initially, distance from source to source is considered as O and to all other vertices is infinity. It uses the condition "current vertex distance edge weight < next vertex distance" to find shortest distance. Time complexity for this is O(v² )

Faster all pair shortest path : It finds shortest the distance from a vertex to all other vertices in a graph. It there are E edges and V vertices in a graph, then it takes
O (v² log v) time to find the shortest path.

Edmonds-Karp algorithm :- It is used to find the maximum flow in a network. It uses BFS in ford fulkerson method. It time complexity is O(V.E² )

The question asks specifically for inplace sorting algorithms, which means the algorithms in which only O(1) space is used.
Insertion sort :
In insertion sort, the worst case takes O(n₂) time, worst case of insertion sort is when elements are sorted in reverse order. It is in place sorting algorithms. In that case the number of comparison and be like.
Merge Sort –
In merge sort, the worst case takes O(n logn) time. Merge sort is based on the divide and conquer approach. It is out of place sorting algorithms. Recurrence relation for merge sort will become
T(n) = 2T (n/2) + O(n)
T(n) = n + O(n)
T(n) = n × Log n
Quicksort : In Quicksort, the worst case takes O(n₂) time the worst case of quicksort is when the first or the last element is chosen as the pivot element.

Sort the integers in the range from O to n² – 1 If we take any comparision - based sorting algorithms for this, it will take O (nLogn) time. Radix sort is used for sorting this range integers. Radix sort takes O(n) time for this. Algorithm : For any digit in the integer, varies from least significant digit to the most significant digit of the number. Sort the input array using count sort algorithm according to the digit. Note : Radix sort depends on digits. It is more flexible than comparison based sorting algorithm It solve the given problem in Linear time.

Depth first search: Depth first search algorithm is used to traverse the vertices of a graph. It uses the concept of back tracking.
Depth first search uses a data structure for its implementation. Which is known as stack. Application of depth first search :
1) It is used to find the strongly connected components.
2) It helps in topological sorting
3) To check the bipartiteness of a graph.
4) It helps in detecting cycles in a graph.
5) To find articulation points in a graph.

Data

NP Complete problems :
They are those for which no polynomial time algorithm exists. We can say a problem is NP complete if it is NP and belongs to NP hard.

Both Dynamic Programming and greedy algorithms find optimal substructure in the problem but only dynamic programming uses the bottom up approach.

Flow for a real valued function f : v × v → R should satisfy following two properties :
1) skew symmetry property : i.e f (u, v) = -f(v u)
2) capacity constraint means how should be less than the capacity of the It can not exceed the capacity i.e. f (u, v) < = c(u, v)
3) Flow conservation : It means no vertex except the source and destination creates or store the flow. Net flow should be O.
i.e for all u ∈ v – {s, t}, ∑ v ∈ v f(u, v) = 0