Standard searching algorithms

2* A shopping website requires customers to create a username and password.

The usernames and passwords are stored securely in a file. The file contains the username and passwords for 50 million users which are sorted in alphabetical order by username.

The file can be searched using a linear search or a binary search.

The big-O complexities for a linear search and a binary search are given in the table:

Compare the use of a linear search and a binary search in this scenario.

You should include the following in your answer:

• the features and preconditions of a linear and binary search

• the benefits and drawbacks of each search in this scenario

• a conclusion justifying which search algorithm should be used in this scenario.

You should make reference to the big-O complexities in your answer.

The website collects data from customers’ activities once they log on. For example, the items they view and purchase. The company that owns the website would like to use data mining to improve their website and customer experience.

Describe what data mining means.

Explain how the company can make use of data mining to improve their website and customer experience.

The following strings are stored in an array.

Explain how a linear search would search the array for the index that stores "clouds".

State why a binary search cannot be used in this example.

Show how an insertion sort will sort the given data into ascending alphabetical order.

A sorting algorithm has a best time complexity of O(n).

Describe what is meant by the best time complexity O(n) for a sorting algorithm.

Another sorting algorithm has a worst space complexity of O(log(n)).

Describe what is meant by the worst space complexity O(log(n)) for a sorting algorithm.

Identify the time complexity that means the time will not change even when the number of items increases.

Identify the space complexity that means the amount of memory (space) used will double each time a new item is included.

A computer program stores data in an array named words.

The data in the array needs to be searched for a value that the user inputs.

One example of a searching algorithm is a binary search.

Identify the precondition for a binary search.

A second example of a searching algorithm is a linear search.

Describe how a linear search works.

The array words is defined as a global variable and contains these values:

The pseudocode function useWords() here uses the global array words.

The number of words in the array words is passed as a parameter.

Identify two variables in the function useWords().

numberOfWords is a parameter passed by value.

Describe the difference between passing a parameter by value and by reference.

Rewrite the function useWords() to use a while loop instead of a for loop.

The function header and close have been written for you.

Write your answer using pseudocode or program code.

function useWords(numberOfWords: byVal)

endfunction

Give one benefit and one drawback of declaring the array as a global variable instead of a local variable.

Describe one feature of an Integrated Development Environment (IDE) that can be used to help write the program and one feature that can be used to help test the program.

Functions and procedures are reusable components.

Give two benefits of writing a program with reusable components.

The pseudocode function binarySearch() performs a binary search on the array dataArray that is passed as a parameter. The function returns the array index of searchValue within the array, and-1 if it is not in the array.

The pseudocode binary search algorithm is incomplete.

Complete the algorithm by filling in the missing statements.

The algorithm uses a while loop.

State a different type of loop that could be used instead of the while loop in the given algorithm.

The tables below show possible Big O complexities for the worst-case space, best-case space and average time for search algorithms.

Tick the worst-case space complexity for a binary and linear search.

Tick the best-case space complexity for a binary and linear search.

Tick the average time complexity for a binary and linear search.

Identify one situation where a linear search is more appropriate than a binary search.

Hugh has written a recursive function called thisFunction() using pseudocode.

The function DIV calculates integer division, e.g. 5 DIV 3 = 1

State the name of the standard algorithm thisFunction() performs.

Hugh could have written thisFunction() using iteration instead of recursion.

Compare two differences between recursion and iteration.

The recursive function thisFunction() is printed again here for your reference.

Rewrite the function thisFunction() so that it uses iteration instead of recursion.

You should write your answer using pseudocode or program code.

A computer program stores data input on a stack named dataItems. The stack has two sub-programs to add and remove data items from the stack. The stack is implemented as a 1D array, dataArray.

The current contents of dataItems are shown:

The main program asks a user to push or pop an item from the stack. If the user chooses ‘push’, the data item is added to the stack. If the user chooses “pop”, the next item is removed from the stack, multiplied by 3 and output.

The main program is shown:

Before the sub-programs, push() and pop(), can add or remove items from the stack, a selection statement is used to decide if each action is possible.

Describe the decision that needs to be made in each sub-program and how this impacts the next process.

The algorithm does not work when the user enters "PUSH" or "Push". The algorithm needs to be changed in order to accept these inputs.

Identify the line number to be changed and state the change that should be made.

The stack is implemented as a 1D array, dataArray.

Describe how a 1D array can be set up and used to push and pop items as a stack.

As an array, the data in dataArray is sorted and then searched for a specific value.

The data in dataArray is sorted into ascending order using an insertion sort.

The current contents of dataArray are shown:

Show the steps of an insertion sort on the current contents of the array dataArray.

The array dataArray can now be searched using a binary search.

Describe the stages of a binary search on an array of size n.

The array has 50 items.

The function, searchItem(), performs a linear search for a data item.

Rewrite the function using a while loop.

A programmer is developing an ordering system for a fast food restaurant. When a member of staff inputs an order, it is added to a linked list for completion by the chefs.

Explain why a linked list is being used for the ordering system.

Order 158 has been made, and needs adding to the end of the linked list.

Add the order, 158, to the linked list as shown in Fig. 2.1. Show the contents of the linked list in the following table.

Order 159 has been made. This order has a high priority and needs to be the second order in the linked list. Add the order, 159, to the original linked list as shown in Fig. 2.1. Show the contents of the linked list in the following table.

The linked list is implemented using a 2D array, theOrders:

• Row 0 stores orderNo

• Row 1 stores next

The data now stored in theOrders is shown in Fig. 2.2.

The following algorithm is written:

Outline why nodeNo does not need to be stored in the array.

Complete the trace table for procedure x, for the data shown in Fig. 2.2.

Describe the purpose of procedure x.

A new order, 190, is to be added to theOrders. It needs to be the third element in the list. The current contents of the array are repeated here for reference:

Describe how the new order, 190, can be added to the array, so the linked list is read in the correct order, without rearranging the array elements.

The user needs to be able to search for, and find, a specific order number.

State an appropriate search algorithm that could be used, and justify your choice against an alternative Search algorithm.

Appropriate Search Algorithm........

The programmer is writing the program using an IDE.

Identify three features of an IDE that the programmer would use when writing the code and describe how the features benefit the programmer.

(f*) The programmer is considering using concurrent programming.

Discuss how concurrent programming can be applied to the food ordering system and the

benefits and limitations of doing so.