Sub programs: functions and procedures

A student is writing a program in a high-level programming language.

The student writes the program using an Integrated Development Environment (IDE).

Complete the table by identifying and describing three features of an IDE that the student can use to debug their program.

The program the student is developing includes both global and local variables.

Explain the difference between a global variable and a local variable.

Describe one drawback of using global variables in a program.

Describe one drawback of using local variables in a program.

A variable can be passed as a parameter into a function by value or by reference.

Describe what parameter passing by value means.

An algorithm is needed to count how many times each of the numbers from 1 to 9 appear in an array called myArray. Another array called checked is used to store each number found in myArray and the number of times it appears. For example, the contents of myArray are:

Based on these contents in myArray, the contents in checked would be:

–1 indicates an unused space in the array as the numbers 1, 4, 8 and 9 have not been found.

The student has written the following pseudocode for this program.

The pseudocode contains several errors.

Identify the line number of any four errors and write the corrected line for each error.

Error 1

Error 2

Error 3

Error 4

A linked list data structure is designed using object-oriented programming.

The design includes two classes called node and linkedList.

Describe the features of a linked list data structure.

The class design for node is shown here.

new() is the constructor method. The constructor method takes a parameter and assigns this to the value attribute.

The method getNextNode() returns the attribute nextNode.

Write the method getNextNode() using pseudocode or program code.

The method setValue() takes an integer as a parameter and assigns this to the attribute value

Write the method setValue() using pseudocode or program code.

The class design for linkedList is shown here.

new() is the constructor method. The constructor initialises the attribute headNode to a null value.

Write the constructor method using pseudocode or program code.

The class design for node and linkedList are shown again here for your reference.

The method getValue() will return the value of a node. The method getNextNode() will return the next node to be accessed in the linked list.

The method outputList() traverses the linked list starting at the node headNode. The method joins the data in each node and returns it.

Complete the method outputList() using pseudocode or program code.

The method insertNode() will insert a new node into the linked list.

The method accepts an integer as a parameter, creates a new node with that data and inserts it into the linked list, e.g. insertNode(8) creates a node object with the data 8 and adds it to the linked list.

The program needs to store the following data items in the linked list in the order they are given: 10 25 39

The program then needs to output all of the data in the list using the appropriate method.

Write an algorithm using pseudocode or program code to:

• create a new linkedList object with the identifier createList

• insert each of the data items into the linked list (10, 25, 39)

• output the content of the linked list.

A new method is needed to remove a node from the linked list. The method needs to take the data to remove as a parameter and then find this data in the linked list before removing the node.

Describe the steps that this method will need to follow and the decisions that need to be made in the method to remove the correct node.

The program developer made use of computational methods when designing the object-oriented programming solution. One computational method is divide-and-conquer.

Identify three other computational methods that the program developer could have used.

* This program uses classes and objects to create a linked list.

An alternative method is creating a 2-dimensional array. In this design the first index stores the data and the second element stores the index of the next data item. Array elements not currently used are also linked together to form a chain of empty values to identify where the next data item can be inserted.

Compare the two different methods of creating a linked list that have been described.

You should include the following in your answer:

• the features of both methods including the reusability of program components

• benefits and drawbacks of both methods in this program

• a conclusion evaluating the efficiency of both methods when designing a program that needs

a linked list.

The contents of a stack are stored in the 1-dimensional array called numbers.

topStack stores the index of the next free space in the stack.

The array is declared with space for 100 elements.

The function pop() returns the next item from the stack and updates the appropriate pointers.

Describe the steps in the function pop().

The function push() inserts its parameter called dataValue onto the stack and updates the appropriate pointers.

Complete the function push() using pseudocode or program code.

Write an algorithm, using pseudocode or program code, to call the function push() with the value 15 and output a message saying "Added" if the value was successfully inserted onto the stack or "Not Added" if the stack is full.

A game is being written that makes use of object-oriented programming. A prototype for one part of the game is being designed that includes a character, a road and a prize to collect.

The road will have 50 spaces that a character can move along. Each space on the road will store a null value or a prize object for the user to collect. Each space is numbered sequentially from the first space (position 0) to the last space (position 49) and will not change during the game. As the player travels down the road, the position the player is on the road will be output.

The road is designed to be a 1-dimensional array with the identifier road.

Explain why an array is a suitable data structure to represent the road.

The characters and prizes are designed as separate classes. 10 of the spaces on the road will contain an instance of the class Prize. The other spaces will be empty.

The class design for Prize is here.

new() is the constructor method. The name, type and value are passed to the constructor as parameters which then assigns these to the attributes.

The method getName() returns the data in the attribute name.

Write the method getName() using pseudocode or program code.

A global 1-dimensional array, allPrizes, stores 10 objects of type Prize.

The prize in index 3 has the name "Box", the type is "money" and the value is 25.

Write pseudocode or program code to create a new object for this prize and store it in index 3 of allPrizes.

The game starts with 10 prizes. Each prize is allocated to one space on the road.

An algorithm needs designing that will generate a random space on the road for each prize. Each road space can only store one prize.

Describe the decisions that will need to be made in this algorithm and how these will affect the program flow.

The class design for Character is here.

The four get methods return the associated attribute.

The number of moves is passed to changePosition() as a parameter. The method adds this value to the character’s position on the road.

The type and value of an object are passed to updateValues() as parameters. If the object is money the value is added to the character’s money. If the type is experience the value is added to experience. If the type is neither money or experience no changes are made.

new() is the constructor method. The name of the character is passed into the constructor as a parameter. The constructor then initialises both the experience and road position of the character to 0 and initialises the amount of money to 5.

Write the constructor method for Character using either pseudocode or program code. You do not need to declare the class, the attributes or any other methods.

The type and value of a prize are passed as parameters to the method updateValues. If the type is money the value is added to the character’s money. If the type is experience then the value is added to the experience. If the type is neither money or experience no changes are made.

For example, for the Character player1:

player1.updateValues("money",10) updates player1’s money by 10

player1.updateValues("experience",5) updates player1’s experience by 5

player1.updateValues("foo",9) has no effect on player1.

Write pseudocode or program code for the method updateValues().

This incomplete pseudocode algorithm:

• creates a new character with the name Jamal

• loops until the character reaches the end of the road

• generates a random number of spaces to move between 1 and 4 (including 1 and 4)

• moves the character and checks if the new space has a prize

• updates the character attributes if there is a prize

• outputs the character’s new attribute values.

Complete the pseudocode algorithm.

The procedure displayRoad() outputs the contents of each space in the road. The number of each space is output with either:

• the word "empty" if there is no prize

• the name of the prize if there is a prize.

The algorithm contains errors.

Give the line number of four different errors and write the corrected line for each error.

Error 1

Error 2

Error 3

Error 4

* A programmer is going to create a prototype for one small part of the game. Both road and allPrizes will be needed throughout the whole prototype. The programmer is considering making these global arrays as she thinks it will reduce the development time. Another programmer has suggested that doing this may create some problems when the rest of the game is created at a later stage.

Compare the use of global and local variables in this program.

You should include the following in your answer:

• the use of local and global variables

• alternative methods to using global variables

• the appropriateness of each to this program design.

A programmer has designed a program that includes a reusable program component.

The reusable program component is a function called isInteger(). This will take a string as an argument and then check that each digit is between 0 and 9. For example if 103 is input, it will check that the digits 1, 0 and 3 are each between 0 and 9.

The asc() function returns the ASCII value of each digit. For example asc("1") returns 49.

The ASCII value for 0 is 48. The ASCII value for 9 is 57.

Identify one identifier used in the function isInteger().

Give the line number where the branching (selection) construct starts in the function isInteger().

Give the line number where the iteration construct starts in the function isInteger()

Describe the purpose of the following lines in the function isInteger().

Line 03........

Line 04........

Line 09........

Give two reasons why reusable program components are used in programs.

A text-based computer game allows a user to dig for treasure on an island. The island is designed as a grid with 10 rows and 20 columns to store the treasure. Each square is given an x and y coordinate. Some of the squares in the grid store the name of a treasure object. Each treasure object has a value, e.g. 100 and a level, e.g. "Bronze."

The computer game makes use of abstraction.

Describe what is meant by the term abstraction and give an example of how abstraction can be used in the treasure game.

Give three benefits of using abstraction when writing a program.

The treasure game is being programmed using an object-oriented paradigm.

A class, Treasure, is used to store the treasure objects.

The design for the Treasure class, its attributes and methods is shown here.

The constructor method takes a value as an integer, e.g. 100, and a level, e.g. "bronze", as parameters and assigns these to the attributes.

Write pseudocode or program code to declare the class Treasure.

You should define the attributes and constructor method in your answer.

You do not need to write the get methods.

The get method getLevel() will return the appropriate attribute.

Write the method getLevel() using either pseudocode or program code.

Describe the object-oriented programming technique being used in part 9(b)(ii).

A class, Board, is used to store the 10 row (x coordinate) by 20 column (y coordinate) grid.

The design for the Board class, its attributes and methods is shown here.

The constructor initialises each space in the grid to a treasure object with value as-1 and level as an empty string.

Complete the following pseudocode for the constructor method.

A procedure, guessGrid():

• takes a Board object as a parameter

• accepts the row (x) and column (y) coordinates from the user

• outputs "No treasure" if there is no treasure found at the coordinate (level is an empty string)

• if there is treasure at that coordinate, it outputs the level and the value of the treasure in an appropriate message.

Write the procedure guessGrid() using either pseudocode or program code.

Describe two benefits of using an object-oriented paradigm rather than a procedural paradigm.

* The main program initialises a new instance of Board. The programmer is considering declaring this as a global variable or as a local variable and then passing this into the subroutines that control the game.

Compare the use of variables and parameters in this game.

You should include the following in your answer:

• what is meant by a local variable and global variable

• how local and global variables can be used in this program

• the use of passing parameters by value and by reference.

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.

A card game uses a set of 52 standard playing cards. There are four suits; hearts, diamonds, clubs and spades. Each suit has a card with a number from; 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13.

The card game randomly gives 2 players 7 cards each. The unallocated cards become known as the deck.

The players then take it in turns to turn over a card. A valid move is a card of the same suit or the same number as the last card played.

The winner is the first player to play all of their cards.

One component of the game is checking if a move is valid.

Identify three other components of the game.

A function, checkValid(), takes the card the player has selected, and the last card played as parameters.

It returns true if the player’s move is valid and returns false if the player’s move is not valid.

State the reason why checkValid() is a function and not a procedure.

The programmer will use a branching (selection) construct to make decisions.

Describe the decisions that will be made in the checkValid() function and how these change the return values.

The cards are held in the 2D array cards. The first index stores the card number and the second index stores the suit, both as strings.

Write a pseudocode statement or program code to declare the array cards.

Juan is creating a structure diagram to design the game.

A structure diagram is one method of showing the decomposition of a problem.

Explain why decomposing a problem can help a developer design a solution.

Identify one input, one process and one output required for the game.

Juan uses the structure diagram to create a modular program with a number of subroutines. The program will use two integer 2-dimensional arrays to store the puzzles:

• puzzle(5,5) stores the solution

• answerGrid(5,5) stores the user’s current grid.

A 0 represents a white box and a 1 represents a black box.

Explain the purpose of line 03 in the function countRow.

Describe the purpose of branching and iteration in the function countRow.

The function checkWon() takes answerGrid and puzzle as parameters and compares each element in the grids. If they are identical, it returns true, otherwise returns false.

There are three logic errors in the function checkWon.

State the line number of each error and give the corrected line.

Error 1 line number........

Error 1 correction........

Error 2 line number........

Error 2 correction........

Error 3 line number........

Error 3 correction........

* Juan passed the two arrays as parameters, but he did consider making them globally accessible.

Compare the use of global and local variables and data structures in this program. Include the use of parameters and program efficiency in your answer.

Juan wants to create a program that will generate new Nonograms with different grid sizes. For example a Nonogram with a 10 × 10 grid or a 5 × 20 grid.

Describe how the program could be written to automatically generate a new Nonogram.

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 recursive function, GCD, is given in pseudocode.

The function uses branching.

Identify the type of branching statement used in the function.

Explain the difference between branching and iteration.

Identify the two parameters in the function.

1

2.

State whether the parameters should be passed by value, or by reference. Justify your answer.

Describe the arithmetic operation of MOD. Use an example in your answer.

Trace the recursive function when it is called by the statement GCD(250, 20). Give the final value returned.

Final return value:.

The function has been rewritten using iteration instead of recursion.

State one benefit and one drawback of using iteration instead of recursion.

Benefit.

Drawback.

Complete the missing statements in this iterative version of the function.

The programmer will use abstraction to produce the program interface to represent the garden.

Give two different examples of how abstraction has been used to produce the layout of the garden.

Explain the need for abstraction in the production of this program.

The user needs to input data into the program to set up their garden layout.

Identify three pieces of data that the user may input into this program.

The program is to be built using object oriented programming.

All items that can be added to the garden are declared as instances of the class GardenItem

The class has the following attributes:

The constructor method sets the attributes to values that are passed as parameters.

Write pseudocode or program code to declare the class GardenItem and its constructor. All attributes should be private and initialised through the constructor (e.g. daisies =

new GardenItem("Flowerbed",2,1)

The trees in the garden layouts are defined by the class Tree. This class inherits from GardenItem.

The class Tree has the additional attributes: height, sun, shade.

If sun is true then the tree can grow in full sun, if it is false then it cannot.

If shade is true then the tree can grow in full shade, if it is false then it cannot.

The length and width of a tree are the same. Only one value for these measurements is passed to the constructor.

Write an algorithm, using pseudocode or program code, to declare the class Tree Declare all attributes as private.

The Common Oak is a type of tree. It has a maximum height, length and width of 40 m. It can grow in sun and shade.

Write a statement, using pseudocode or program code, to declare an instance of tree for the Common Oak. Give the object the identifier firstTree.

The classes GardenItem and Tree use get and set methods to access and alter their private attributes.

Write the get method getItemName and set method setItemName for class GardenItem. The set method takes the new value as a parameter.

Do not write any other methods, or re-declare the class.

* The programmer is designing the program to make use of caching and re-useable components.

Explain and evaluate the use of caching and re-useable components in the design of the garden program.

A recursive function, generate, is shown.

Trace the algorithm to show the value returned when generate(7) is called. Show each step of your working.

The parameter, num1, is passed by value.

Explain why the parameter was passed by value instead of by reference.

* Parameters can be used to reduce the use of global variables.

Compare the use of parameters to global variables in recursive functions.

A student called Jason writes a recursive algorithm. The recursive algorithm uses more memory than if Jason had written it as an iterative algorithm.

Explain why the recursive algorithm uses more memory than the iterative algorithm.

An encryption routine reads a line of text from a file, reverses the order of the characters in the string and subtracts 10 from the ASCII value of each letter, then saves the new string into the same file.

The program is split into sub-procedures. Three sub-procedures are described as follows:

• Read string from file

• Push each character of the string onto a stack

• Read and encrypt each character message

Identify one further sub-procedure that could be used in the program.

Describe two advantages of splitting the problem into sub-procedures.

A function, readMessage:

• takes the file name as a parameter

• reads and returns the line of text

Complete the pseudocode algorithm for readMessage:

A function, push, can be used to add a character to a stack. For example:

theStack.push("H")

places the character H onto the stack, theStack.

A procedure, pushToStack, takes a string as a parameter and pushes each character of the message onto the stack, messageStack.

Complete the procedure below.

Add comments to explain how your code works.

procedure pushToStack(message)

endprocedure

Describe the steps that the program would have to take in order to encrypt the characters stored in the stack, and save them in a single variable.

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.