A group of n guests shows up to a house for a party, but some pairs of guests are enemies. There are two rooms in the house, and the host wants to distribute guests among the rooms, breaking up as many pairs of enemies as possible. The guests are all waiting outside the house and are impatient to get in, so the host needs to assign them to the two rooms quickly, even if this means that it's not the best possible solution.
(a)We constructed a greedy 1/2-approximation algorithm for this problem that runs in time O(V +E) prior. Now give a randomized algorithm that achieves (in expectation) the same approximation guarantee in time O(V ).
(b) Your solution in part (a) probably had to flip O(V ) random coins, but coins are expensive, use hashing to give an algorithm that only flips O(logV) random coins.

You need to design a circuit that implements the functions in the following table: s0 s1 function0 0 a + 10 1 a – b1 0 a + b1 1 a – 1s0 and s1 are 1-bit control inputs to select the function of the circuit. inputs a and b are 4-bitnumbers in 2s complement form. the output is also a 4-bit number in 2s complement form.you are allowed to use only one ttl 7483 4-bit adder to implement all the functions. but anynumber of other components (except the adder) can be used.hint: design a combinational logic circuit to modify the input b and the “carry input” of theadder depending on the control inputs s0 and s1.important: lab grade will depend on the working of the circuit & will be checked of by your labinstructor.1. is the output valid for the following input combinations: a. s0 = 0, s1 = 0, a = 7, b = 3? b. s0 = 0, s1 = 1, a = 7, b = 3? c. s0 = 1, s1 = 0, a = -4, b = -5? d. s0 = 1, s1 = 1, a = -8, b = 6? 2. what is the range of inputs (for both a and b) that will produce the valid output for all the functions?