1. You are applying for a job at a new software technology company. Your interviewer asks you to identify which of the following tasks are possible (P), impossible (I), or unknown or intractable (U). Choose the correct letter for each task. a) Given a undirected graph, determine if there exists a path of length V - 1 with no repeated vertices in time proportional to EV in the worst case. b) Given a digraph, determine if there exists a directed path between every pair of vertices in time proportional to E+V in the worst case. c) Given a digraph, design an algorithm to determine whether it is a rooted DAG (i.e., a DAG in which there is a path from every vertex to some root r) in time proportional to E + V in the worst case. d) Given a digraph where each edge is colored black or orange and two vertices s and t, find a path from s to t that uses the fewest number of black edges in time proportional to E+ V in the worst case. e) Given an array of N integers in the range [O... R-1), stably sort them in time proportional to N+R in the worst case. f) Determine how many times a pattern string of length M appears as a substring in a text string of length N in time proportional to M+N in the worst case. For simplicity, assume the binary alphabet. g) Given N symbols, print all permutations of these N symbols in time proportional to N. h) Given a large integer N, find the prime factorization of N in time proportional to N. (A prime factorization means the prime numbers that can be multiplied together to make N). i). Given an array a of N 64-bit integers, determine whether there are two indices i and j such that ai = -a; in time proportional to N in the worst case. j). Given an array a of N 64-bit integers, determine the median of these integers in time proportional to N in the worst case