Administrators at CoRec would like to make sure their entry-exit tally is working correctly. Given a sequence of user entries and exits, they want to find out whether the sequence is valid. A sequence of entries and exits is valid if (1) The sequence contains an equal number of entries and exits. (2) There exists no prefix of the sequence that has more exits than entries. (A prefix of the sequence is a subsequence starting at position 1 and ending at a position i.) Representing the sequence by an array of ls for entries and Os for exits, the following sequence is valid: (1, 0, 1, 1, 1, 0, 0, 1, 0, 0] while the following two are not valid: (1, 0, 1, 1, 1, 0, 0, 1, 0] (1, 0, 1, 1, 1, 0, 0, 0, 0, 1] as they violate constraint (1) and (2) respectively. (a) Given is a sequence of entries and exits represented by an array of ls for entries and Os for exits. Design and describe an O(n) time non-divide-and-conquer algorithm that decides whether the sequence is valid. Address the running time of your algorithm and its correctness. (b) In a big data distributed environment, one may not be able to use the algorithm developed in (a) as the input data is distributed. In such an environment, subproblems need to be solved in parallel. Divide and conquer algorithms provide a natural parallelism. Develop and describe an O(n) time divide-and-conquer algorithm that identifies whether the sequence is valid. No points will be given if the algorithm is not divide-and-conquer. Address the running time of your algorithm and its correctness. (Hint: Consider a combining strategy similar to the one used in the max sum subarray divide-and-conquer algorithm.) Administrators at CoRec would like to make sure their entry-exit tally is working correctly. Given a sequence of user entries and exits, they want to find out whether the sequence is valid. A sequence of entries and exits is valid if (1) The sequence contains an equal number of entries and exits. (2) There exists no prefix of the sequence that has more exits than entries. (A prefix of the sequence is a subsequence starting at position 1 and ending at a position i.) Representing the sequence by an array of ls for entries and Os for exits, the following sequence is valid: (1, 0, 1, 1, 1, 0, 0, 1, 0, 0] while the following two are not valid: (1, 0, 1, 1, 1, 0, 0, 1, 0] (1, 0, 1, 1, 1, 0, 0, 0, 0, 1] as they violate constraint (1) and (2) respectively. (a) Given is a sequence of entries and exits represented by an array of ls for entries and Os for exits. Design and describe an O(n) time non-divide-and-conquer algorithm that decides whether the sequence is valid. Address the running time of your algorithm and its correctness. (b) In a big data distributed environment, one may not be able to use the algorithm developed in (a) as the input data is distributed. In such an environment, subproblems need to be solved in parallel. Divide and conquer algorithms provide a natural parallelism. Develop and describe an O(n) time divide-and-conquer algorithm that identifies whether the sequence is valid. No points will be given if the algorithm is not divide-and-conquer. Address the running time of your algorithm and its correctness. (Hint: Consider a combining strategy similar to the one used in the max sum subarray divide-and-conquer algorithm.)
