Consider there are n requests. These requests are labeled 1, 2, · · · , n with each request i specifying a start time si and a finish time fi where si < fi. Two requests i and j are compatible if the requested intervals do not overlap. A subset of requests is compatible if all pairs of requests i, j ∈ A, i != j are compatible. Design an algorithm which will output a compatible subset of requests of maximum possible size. Give the correctness proof of the algorithm and write a code for the same.
Write a code to generate a Gray code of length n ≥ 1 if n is even, else generate an open Gray code.
Let there be n players in a chess tournament. Each player plays a game with every other player. A result can be either win, tie or loss. One can ask a question in the form of “Did ‘i’ win against ‘j’?”. The answer could be either “Yes” or “No”. A player will be given the title of “MAGNUS” if he/she wins against every other player. Design an algorithm that is allowed to ask a question in the form prescribed only. which will output a player who is “MAGNUS”, if exists, else “NO MAGNUS”.
Write a program for the Maximum Consecutive Sum problem (Question 4, Lab 02) using Divide-andConquer paradigm. Provide the correctness proof of your algorithm.
Let f be a map that maps a finite set A into itself (i.e. every element of A is mapped to another element of A). For simplicity, we denote the elements of A by the integers 1 to n. Given a finite set A and a mapping from A to itself, find a subset S ⊆ A with the maximum number of elements, such that (1) the function f maps every element of S to another element of S (i.e., f maps S into itself), and (2) no two elements of S are mapped to the same element (i.e., f is one-to-one when restricted to S).
Write a program for the Skyline problem using Divide-and-Conquer paradigm.