IFN564 Data Structures and Algorithms Assignment

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

We will see later in the semester how to handle a customer object. For now, we assume the only information you have about these customers are names, so we treat the collection as a collection of strings. For simplicity, we will also assume that all names are unique.

You are trying to decide how to store and manage the customer data.

In the first instance, you are considering using an array to store the customers. For now, we assume that you have allocated the array to a maximum size N_max, that you hope will be large enough to accommodate all your customers.

You are evaluating two options:

1. You always insert customers at the end, not caring about
2. You always keep your structure sorted, by inserting any new customer at their correct

This leads you the consider the following algorithms:

Option A

Algorithm InsertOptionA(A[0..N_max-1], n, new_customer)

if n < N>

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>

i ? i+1

if i = n

print “This customer is not in the array”

else

while i < n>

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>

while A[i] < new>

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>

A[m] ? A[m+1]

m ? m + 1 n ? n – 1

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
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
2. Verifying whether the execution time matches your efficiency analysis from 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.