1. Let G-(V, E) be a directed graph where V 1,2, ,n). Given a vertex vlet S denote the set of vertices that have a path from v (excluding v), and let T, be the set of vertices from which there is a path to v (excluding v). A vertex v is (1/3,2/3) critical, if the size of S, is (n -1)/3 and the size of T, is 2(n 1)/3 and S and T, are disjoint. Given a graph (where n - 1 is divisible by 3), give an algorithm that outputs a (1/3,2/3) critical, if one exists. Prove the correctness and derive the runtime. Part of the grade depends on efficiency. 2. We are given an information network where the edges represent sender-receiver relationship L.e., if there is an edge from r to y, then r sends information to y. Any information received or originated by a node x will be received by all y such that there is an edge from x to y For example if there is an edge from x to y, edge from y to z. Any information originated at r is received by y, which in turn is received by z. Given a network of n entities and m edge relationships, . give an algorithm that checks whether there exists an entity, which is capable of sending information to all other entities. Prove correctness of your algorithm. Derive the runtime of your algorithm. Part of the grade depends on efficiency . Give an algorithm that checks whether there exists a group of entities (of size 2 2), who can exchange messages among each other but cannot send messages to anyone outside the group. If such a group exists, find the entities of that group. Prove the correctness of your algorithm. Derive the runtime of your algorithm. Part of the grade depends on efficiency 3. Let G be a friendship social network, Le, G is undirected. Given two people r and y from the network, relationship strength between x and y is the number of shortest paths between r and y. Give an algorithm that gets a friendship social network and two entities r and y and calculates the relationship strength between r and y. Prove the correctness of your algorithm, derive the run time. Part of the grade depends on efficiency 1. Let G-(V, E) be a directed graph where V 1,2, ,n). Given a vertex vlet S denote the set of vertices that have a path from v (excluding v), and let T, be the set of vertices from which there is a path to v (excluding v). A vertex v is (1/3,2/3) critical, if the size of S, is (n -1)/3 and the size of T, is 2(n 1)/3 and S and T, are disjoint. Given a graph (where n - 1 is divisible by 3), give an algorithm that outputs a (1/3,2/3) critical, if one exists. Prove the correctness and derive the runtime. Part of the grade depends on efficiency. 2. We are given an information network where the edges represent sender-receiver relationship L.e., if there is an edge from r to y, then r sends information to y. Any information received or originated by a node x will be received by all y such that there is an edge from x to y For example if there is an edge from x to y, edge from y to z. Any information originated at r is received by y, which in turn is received by z. Given a network of n entities and m edge relationships, . give an algorithm that checks whether there exists an entity, which is capable of sending information to all other entities. Prove correctness of your algorithm. Derive the runtime of your algorithm. Part of the grade depends on efficiency . Give an algorithm that checks whether there exists a group of entities (of size 2 2), who can exchange messages among each other but cannot send messages to anyone outside the group. If such a group exists, find the entities of that group. Prove the correctness of your algorithm. Derive the runtime of your algorithm. Part of the grade depends on efficiency 3. Let G be a friendship social network, Le, G is undirected. Given two people r and y from the network, relationship strength between x and y is the number of shortest paths between r and y. Give an algorithm that gets a friendship social network and two entities r and y and calculates the relationship strength between r and y. Prove the correctness of your algorithm, derive the run time. Part of the grade depends on efficiency