1. Explain how you know that the following decision problems are in P. You don’t need to provide pseudocode, a basic exp
Posted: Sat May 14, 2022 7:13 pm
1. Explain how you know that the following decision problems are in P. You don’t need to
provide pseudocode, a basic explanation will suffice.
(a) Y ∨ N: Given a list with n elements, is it unsorted? [10 pts]
(b) Y ∨ N: Given a list with n elements, is the maximum in a smaller index than the minimum? [10 pts]
(c) Y ∨ N: Given a 1,000,000-D (-D for -dimensional) array of integers, where each array [10 pts]
contains n elements (i.e. it holds n 999,999-D arrays, each containing n 999,998-D arrays,
etc. down to 1-D arrays containing n integers), do any of the 1-D arrays contain a 0?
provide pseudocode, a basic explanation will suffice.
(a) Y ∨ N: Given a list with n elements, is it unsorted? [10 pts]
(b) Y ∨ N: Given a list with n elements, is the maximum in a smaller index than the minimum? [10 pts]
(c) Y ∨ N: Given a 1,000,000-D (-D for -dimensional) array of integers, where each array [10 pts]
contains n elements (i.e. it holds n 999,999-D arrays, each containing n 999,998-D arrays,
etc. down to 1-D arrays containing n integers), do any of the 1-D arrays contain a 0?