Algorithm efficiency and Big O notation

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.

7* (a) A program designer needs to decide on an algorithm to use from a choice of three. The table shows the worst-case Big O complexities for each algorithm.

The program will be used to analyse data that can range from 2 items to 2 billion items.

Compare the use of all three algorithms and suggest which the programmer should use.

You should include the following in your answer:

• the meaning of constant, logarithmic, linear and exponential complexity

• how well each algorithm scales as the amount of data increases

• which algorithm is the most suitable for the given task.

The program designer is investigating the use of concurrent processing.

Describe what is meant by the term ‘concurrent processing’.

Give two benefits of using concurrent processing.

The programmer needs to use a merge sort in one part of the problem to sort items in ascending order.

Describe how a merge sort works.

Give one benefit and one drawback of the programmer using a merge sort instead of a bubble sort.

The programmer uses an Integrated Development Environment (IDE).

Complete the table by identifying and describing three IDE features that can help the programmer to develop, or debug a program.

A bubble sort will sort an array of 50 integer values called numberArray.

State why the integer values are stored in an array instead of separate variables.

This bubble sort algorithm is written to sort numberArray into ascending numerical order.

Complete this bubble sort algorithm.

One section of numberArray is shown here.

A second sorting algorithm that could be used to sort this data is a merge sort.

Show how a merge sort will sort this section of the array numberArray into ascending numerical order.

* Another sorting algorithm is insertion sort.

The number of values stored in the array numberArray has been reduced to 10.

Compare the use of bubble, merge and insertion sorts on the array numberArray.

You should include the following in your answer:

• how each algorithm works

• the Big O complexities for each algorithm

• the suitability of each algorithm for sorting the 10 values.

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.

The following pseudocode procedure performs an insertion sort on the array parameter.

Explain why dataArray is passed by reference and not by value.

State whether the procedure insertionSort sorts the data into ascending or descending order and explain your choice.

* Two other sorting algorithms are merge sort and quick sort.

Compare the use of merge sort, quick sort and insertion sort on an array with a small number of elements, and on an array with a very large number of elements.

You should make reference to the time complexities of each algorithm using the Big O notation in your answer.

A fourth sorting algorithm is a bubble sort.

Describe how a bubble sort will sort an array of 10 elements.

The temperatures of an ocean are input into a computer system. They are recorded, and will be accessed, in the order in which they arrive. The data for one week is shown:

5, 5.5, 5, 6, 7, 6.5, 6

The data is to be stored in a data structure. The programmer stores the data in a queue.

Explain why a queue is used instead of a stack.

The data is processed. After processing, the value for the first day is stored as 0. The value for each following day is stored as an increase, or decrease, from the first day.

For example: if the first day was 7, the second was 6 and the third was 9, after processing it would be stored as 0, –1, 2.

The queue uses dequeue() to return the first element of the queue.

dequeue() is a function.

Explain why dequeue() is a function, not a procedure.

The contents of processedData are shown.

The data needs to be sorted into ascending order.

Explain how a bubble sort algorithm sorts data. Use the current contents of processedData in your explanation.

A 1-dimensional array stores the following data:

The array needs sorting into descending order.

Describe how a merge sort would sort the given array into descending order.

An insertion sort can be used to sort the array instead of a merge sort.

Explain why an insertion sort might use less memory than a merge sort.

A programmer needs to sort an array of numeric data using an insertion sort.

The following, incomplete, algorithm performs an insertion sort.

Complete the algorithm.

Show how an insertion sort would sort the following data:

Using Big-O notation state the best case complexity of insertion sort.

Explain what your answer to part (b)(i) means.

(c*) The number of data items in the array is continually increasing.

Insertion sort has a worst case time complexity of O(n²) and space complexity of O(1).

An alternative sorting algorithm that could be used is bubble sort which also has a worst case time complexity of O(n²) and space complexity of O(1).

Briefly outline how the bubble sort algorithm works. Discuss the relationship between the complexities and the two sorting algorithms and justify which of the two algorithms is best

suited to sorting the array.

A software developer is creating a Virtual Pet game.

The user can choose the type of animal they would like as their pet, give it a name and then they are responsible for caring for that animal. The user will need to feed, play with, and educate their pet.

The aim is to keep the animal alive and happy, for example if the animal is not fed over a set period of time then the pet will die.

• The game tells the user how hungry or bored the animal is as a percentage (%) and the animal’s intelligence is ranked as a number between 0 and 150 (inclusive).

• Hunger and boredom increase by 1% with every tick of a timer.

• When the feed option is selected, hunger is reduced to 0.

• When the play option is selected, bored is reduced to 0.

• When the read option is selected, the intelligence is increased by 0.6% of its current value.

An example of the game is shown:

Fig. 1.1

Identify three inputs that the user will have to enter to start, and/or play the game.

The developer is using decomposition to design the game.

Describe the process of decomposition.

The developer needs to write procedures for the options play and read. Each of the options changes its corresponding value, and outputs the results to the screen.

Write a procedure, using pseudocode, to reset bored and output the new value in an appropriate message.

Write a procedure, using pseudocode, to increase intelligence by 0.6% and output the new intelligence in an appropriate message.

The developer is extending the game to allow users to have multiple pets of different types. The developer has written a class, Pet.

The attributes and methods in the class are described in the table:

Part of the class declaration is given:

Write a line of code that creates a new instance of Pet for a Tiger called “Springy”.

The method outputGreeting for the superclass is written as follows:

A class is needed for Tiger. The class needs to:

• inherit the methods and attributes from pet

• in the constructor, set type to Tiger, intelligence to 10, hunger to 50 and bored to 10

• extend the method outputGreeting, by outputting an additional line that says “I like to eat meat and roar”

Write, using pseudocode, the class Tiger.

(e*) The developer made use of abstraction when creating the Virtual Pet game.

Discuss the need for and purpose of abstraction and how abstraction will be used in the

development of the game.

The developer is storing the user’s pets in a 1-dimensional array. At each timer interval, the array is searched, using a linear search, to check if any pets’ hunger or bored values are greater than 90%. If they are, an alert is displayed to the user.

State the complexity of searching the pets in Big-O notation.

A given computer takes 4 milliseconds (ms) to search an array of 20 pets. Calculate an estimate of how long the computer will take to search an array of 100 pets.

Show your working.