Imagine that you are working for a software development company, and your client is a shop owner

Fantastic news! We've Found the answer you've been seeking!

Question:

Imagine that you are working for a software development company, and your client is a shop owner who wants a new system to store customer data.

In the first instance, you are considering using an array to store the customers. For now, we assume that you have already allocated the array to a maximum size N_max, which you hope will be large enough to accommodate all your customers. You are evaluating two options: A) You always insert customers at the end, not caring about order. B) You always keep your structure sorted, by inserting any new customer at their correct position. This leads you the consider the following algorithms: Option A Algorithm InsertOptionA(A[0..N_max-1], n, new_customer) if n < N_max A[n] ← new_customer n ← n+1 else print “The array is already full” Algorithm SearchOptionA(A[0..N_max-1], n, customer) for i ← 0 to n − 1 do if A[i] = customer return i return -1 Algorithm DeleteOptionA(A[0..N_max-1], n, customer) i ← 0 while i < n and A[i] ≠ customer do i ← i+1 if i = n print “This customer is not in the array” else while i < n – 1 do A[i] ← A[i+1] i ← i+1 n ← n – 1

Option B Algorithm InsertOptionB(A[0..N_max-1], n, new_customer) if n < N_max i ← 0 while i < n and A[i] < customer do i ← i+1 j ← n – 1 while j ≥ i do A[j+1] ← A[j] j ← j – 1 A[i] ← new_customer n ← n+1 else print “The array is already full” Algorithm SearchOptionB(A[0..N_max-1], n, customer) l ← 0; r ← n – 1 while l ≤ r do m ← ⌊(l+r)/2⌋ if A[m] = customer return m else if A[m] > customer r ← m – 1 else l ← m+1 return -1 Algorithm DeleteOptionB(A[0..N_max-1], n, customer) l ← 0; r ← n – 1 while l ≤ r do m ← ⌊(l+r)/2⌋ if A[m] = customer while m < n – 1 do A[m] ← A[m+1] m ← m + 1 n ← n – 1 return 0 else if A[m] > customer r ← m – 1 else l ← m+1 print “This customer is not in the array”

Question 1 Separately for each algorithm in option A, discuss their efficiency. Make sure to follow the steps covered in class and detail your thinking:

1. What is the problem size?

2. What is the basic operation?

3. Does the algorithm have a best case and a worst case?

4. Calculate the exact efficiency function, using a summation formula or recurrence relation as appropriate and showing all steps in the calculation. If the best and worst cases are different, calculate both functions.

5. What is the efficiency class? (or classes, if the best and worst cases are different).

Question 2 Same question, for the algorithms in option B.

Question 3 Which option do you think is best? How much does that depend on the relative number of insertions, deletions, and searches?

Question 4 Implement both options in the programming language of your choice, and run suitable tests to achieve two goals:

1. Ensuring that the algorithms are working as expected.

2. Verifying whether the execution time matches your efficiency analysis from q.1-3. Make sure to justify the tests you are running and to clearly show and discuss your results.

Question 5 You realise that the number of customers may get quite large, and that it is quite difficult to estimate it. You decide to use a linked list instead of an array. Without going through the first three questions again in detail, discuss what would change in your approach if using a linked list, and what the impact on efficiency would be.