Consider the following problem: You are given a number n and an array A of n num
ID: 3747631 • Letter: C
Question
Consider the following problem: You are given a number n and an array A of n numbers, indexed from 1 to n. Design an algorithm that decides if A contains the numbers 1, 2, 3,..., n, arranged in any order. For example, suppose that n=5, and A = [4, 1, 5, 2, 3], then the answer would be yes, but if A= [1, 2, 3, 4, 10] the answer would be no. Remember that you will be marked on the clarity and time efficiency of your algorithm.
a) [9 marks] Describe the main ideas of your algorithm in words, then describe your algorithm in pseudocode (try to use pseudocode which is similar to that in the textbook).
b) [4 marks] Do a worst case analysis of your algorithm, counting both the comparison of the numbers in A with anything, AND counting the number of times you write a number to an array. Use n as your input size. Be sure to explain your analysis.
Explanation / Answer
A simple algorithm will be:
As indices are from 1 to n only, and elements also are from 1 to n only, what we can do is, whenever we encounter a number in array, we go to number index and make the value negative there..
Like for A = [4, 1, 5, 2, 3], we encountered 4 first, hence we will go to index 4 and make the element negative.
So A become: A = [4, 1, 5, -2, 3]
then 1 is visited and same process is repeated.. After processing all the elements, we again scan the array once.. If there is any element in the array, which contain positive value, then Answer is False, else true.
==========
we will not be doing any comparison in first round. in second round, there can be maximum n comparions. We will be writing n times to the array, as for each element, we change the sign of the element.