ESO207-Assignment 2 Solved

Part 1
 

Problem1Let G = (V,E) be any unweighted directed graph on |V | = n vertices and |E| = m edges with source s ∈ V and destination t ∈ V . Moreover t is reachable from s.

G is said to be 1-connected if there exists a subset E1 ⊆ E such that if we remove any one edge e ∈ E1 then it partitions the vertex set V into two non empty subsets S,T such that there is no path from s ∈ S to t ∈ T in G = (V,E \ {e}).

Consider G to be a given 1-connected unweighted directed graph. Preprocess G in O(n + m) time and build a data structure of size O(n + m) to answer the following 1-connectivity query in O(1) time,

(

                                                                          1       if graph G is still 1-connected after removing e ∈ E

                               1-connectivity(G,e) =                                                                                                    (1)

                                                                          0    otherwise

Give pseudo code for preprocessing step and prove the time and space complexity. Also give the pseudocode and explain how a query, 1-connectivity(G,e) is handled using the constructed data structure in O(1) time.

Problem2. An array A is given with n numbers. A pair (i,j) with 0 ≤ i < j < n is said to be strongly dominated if A[i] 2A[j]. Design an O(nlogn) time algorithm that reports the total number of strongly dominated pairs in A and prove the time complexity of your algorithm.

Problem3. Let P = {p1,p2,...,pn} be a set of n points given in 2D where pi = (x,yi) and yi 6= yj for all i 6= j. Additionally two more points s = (xs,ys) and t = (xt,yt) are given where xs < x and xt x. A path between s and t must contain exactly one point pi ∈ P, (In other words, it is a path of length 2, s 7→ pi 7→ t, where pi ∈ P). Cost of an edge is the Euclidean distance between the pair of points. Hence the cost of a path is the sum of distances of every edge in the path. Your task is to build a compact data structure in O(nlogn) time and O(n) size that will be able to answer the following Min-Cost-Point query in O(logn) worst case time.

Min-Cost-Point(P,s,t) = { pk | pk ∈ P and the cost of path between s and t including pk is minimized.}.

Query outputs an appropriate point pk from P such that the cost of the path between s and t including point pk is minimized, for any given s and t.

Also you are not allowed to sort the points in P. Assume that computing distance between a pair of points takes O(1) time, further computing the cost of a 2-path takes time O(1).

Give the pseudo code for preprocessing step and prove the time and space complexity. You must also give pseudo code or explain how a query is handled using the constructed data structure in O(logn) time.


Part 2
 

Problem4. Given an array A of integers , you have to return an array count where each index i, the array count[i] is the number of smaller elements to the right of A[i].

Give O(nlogn) runtime pseudo code to solve the above problem. Prove the time complexity of your algorithm.

Example :

Input: A = [5,2,6,1] Output: [2,1,1,0] Explanation:

To the right of 5 there are 2 smaller elements (2 and 1).

To the right of 2 there is only 1 smaller element (1).

To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.

Problem5. Give an algorithm that determines whether or not a given undirected graph G = (V,E) contains a cycle. Your algorithm should run in O(V ) time, independent of the number of edges in G. Mention the data structures used in the algorithm. Analyze the time complexity of your algorithm.

Problem6. A knight is a chess piece that moves in an L shape i.e the knight moves 2 units in one direction (i.e., horizontal or vertical) and 1 unit in the perpendicular direction. The figure below shows all the possible moves of knight from position (e,4).

 

You are given a square chess board of size N × N. The knight is initially at source point, (C,D) and destination point of the knight is (E,F). You need to find the minimum number of steps for the knight to move from source to destination. Note that the knight should not move out of the chess board at any point in time.

Give the pseudocode along with the analysis of time complexity and space complexity for the algorithm.

Example :

 

In the above example the knight takes 3 step to reach the target T i.e from (1,4) to (6,1). (1,4)− (4,5)− (5,3)− (6,1).