A regular language is a language that can be defined by a regular expression. 0 2 . 1 Complete the unshaded cells of Table 1 to show which of the statements about regular languages are true and which are false. Table 1 Statement True or False? All regular languages can be represented using a finite state machine without outputs. The set of strings defined by a regular language is always finite in size. There are some languages which can be represented in BackusNaur Form (BNF) that are not regular languages. Copy the contents of the unshaded cells in Table 1 into the table in your Electronic Answer Document. [2 marks] Figure 2 shows a set of Backus-Naur Form (BNF) rules that are used to define a language. Figure 2 ::= ::= ::= ::= human | dog | cat | baby ::= a | the ::= ate | slept | drank | cuddle ::= and | but | or 0 2 . 2 There are two rules in Figure 2 with on the left-hand side that are used to define what a valid sentence is in the language. deaft a single rule that could replace these two rules. Your new rule must not change what a valid sentence is.3 Complete the unshaded cells of Table 2 to show which of the strings are valid sentences for the language defined by the BNF rules in Figure 2 Table 2 String Valid sentence (Y/N)? cuddle the cat drank a human the cat slept cat or dog Copy the contents of the unshaded cells in Table 2 into the table in your Electronic Answer Document. [1 mark] 0 2 . 4 The sentence dog slept is not currently valid in the language defined in Figure 2 Change the language defined in Figure 2 by either adding or modifying exactly one rule so that dog slept is a valid sentence. You must not use the terminals dog or slept directly in the rule you write/change. [1 mark] The sentence the cat slept but the dog drank is not currently valid in the language defined in Figure 2. To allow this to be a valid sentence either one of the following two additional BNF rules could be used. ::= ::= 0 2 . 5 State the number of different sentences defined by the rule: ::= You should only use the rules in Figure 2 when working out your answer to this question. Do not include any additional sentences that your answer to question 02.4 would make valid. You can get full marks for this question for stating either the number of valid sentences or the full calculation needed to work out the number of valid sentences. You should show your working. 6 State how many more sentences are defined by the rule: ::= than by the rule: ::= [1 mark] 0 3 . 1 There are four athletes taking part in a race. Each athlete is allocated a lane that they run in. There can only be one athlete in each lane and there are four lanes available. How many different permutations are there for allocating athletes to lanes? [1 mark] 0 3 . 2 If there are n athletes taking part in a race and n lanes available, with each athlete being allocated to one lane and each lane only used by one athlete, how many different permutations are there for allocating athletes to lanes? [1 mark] 0 3 . 3 An anagram of a string is another string that contains exactly the same number of each character as in the original string but the characters may not all be in the same positions as in the original string. The original string is also an anagram of itself. If there are n characters in a string, why will the number of anagrams of the string not always be the same as your answer to question 03.2? [1 mark] 0 3 . 4 The travelling salesperson problem (TSP) is when a salesperson has to visit every city in a set of cities and needs to find the shortest route that does this without visiting any city more than once before finally returning to the city that they started from. The TSP is an example of an intractable problem. Explain what is meant by an intractable problem.3 lists some time complexities, where n is the size of the problem input and k denotes a constant. Figure 3 O(1) O(nk ) O(kn ) O(n) O(log n) O(n log n) 0 3 . 5 Assuming that the time complexities in Figure 3 are for the most time efficient algorithm that solves a problem, how many of the time complexities in Figure 3 are for intractable problems? [1 mark] 0 3 . 6 State which of the time complexities shown in Figure 3 is the time complexity of the linear search algorithm and explain why it has that time complexity. [2 marks] 0 3 . 7 State which of the time complexities shown in Figure 3 is the time complexity of the binary search algorithm and explain why it has that time complexity. [2 marks] 0 4 Priority queues and linear queues are examples of data structures. 0 4 . 1 A data structure can be implemented as a dynamic data structure or as a static data structure. Discuss the advantages and disadvantages of dynamic data structures compared to static data structures. [4 marks] 0 4 . 2 Describe the steps involved in adding an item to a linear queue that has been implemented as a static data structure using an array. Your answer should include a description of how any pointers are used and changed. [3 marks] 0 4 . 3 For a priority queue, the process to determine where a new item should be added is more complex than it is with a linear queue. Describe the steps involved when adding an item to a priority queue, implemented as a static data structure using an array, that were not required when adding an item to a linear queue.

You are advised to spend no more than 20 minutes on this section. Enter your answers to Section B in your Electronic Answer Document. You must save this document at regular intervals. The question in this section asks you to write program code starting from a new program/project/file. You are advised to save your program at regular intervals. 0. draft program that asks the user how many numeric digits they would like to enter and then gets the user to enter that number of numeric digits. The program should calculate and display the number of times the most frequently entered numeric digit was input. If more than one numeric digit had the same frequency and was the most frequently entered then instead of displaying the frequency, a message saying "Data was multimodal" should be displayed. A numeric digit is 0, 1, 2, 3, 4, 5, 6, 7, 8 or 9 You may assume that the number that the user enters to state how many numeric digits there will be and the numeric digits entered by the user are all valid. Evidence that you need to provide Include the following evidence in your Electronic Answer Document. 0 5 . 1 Your PROGRAM SOURCE CODE. [12 marks] 0 5 . 2 SCREEN CAPTURE(S) showing the result of testing the program by entering: the number 6 then the numeric digits 0, 1, 2, 1, 2 and 1 the number 5 then the numeric digits 0, 1, 2, 2 and 1. This question is about the method GetIndexOfCompany in the Simulation class. 0 6 . 1 What does a return value of -1 indicate? [1 mark] 0 6 . 2 Some of the program code in this method is unnecessary. Identify which code is not necessary and explain why. [2 marks] 0 7 This question is about the Outlet class. 0 7 . 1 State the name of a method in the Outlet class that uses string concatenation. [1 mark] 0 7 . 2 State the name of a local variable in a method in the Outlet class. [1 mark] 0 7 . 3 The Outlet class contains some protected attributes. Explain the difference between protected and private attributes. [1 mark] 0 7 . 4 In the Outlet class the constant value 100 has been used when calculating the initial value of DailyCosts in the constructor method. Explain what problem will occur if this value in the constructor is changed and no other changes are madel.

Figure 4 shows a partially completed class diagram that describes the relationships between some of the classes used in the Skeleton Program. Figure 4 0 8 . 1 State the identifier of the class that has been labelled (3) in Figure 4. [1 mark] 0 8 . 2 State the identifier of the class that has been labelled (4) in Figure 4. [1 mark] 0 8 . 3 State the identifier of the class that has been labelled (5) in Figure 4. [1 mark] 0 8 . 4 Aggregation, composition and inheritance are three different types of relationship that can exist between classes. Which of these three types of relationship is not shown in Figure 4? [1 mark] 0 9 This question is about the ProcessDayEnd method in the Simulation class. Explain how the program decides which company an individual household has decided to use when eating out.

This question refers to the method AddCompany in the Simulation class. The program is to be changed so that it checks that the company name entered is valid. The company must have a name and it cannot be the same as the name of an existing company. The program should keep doing these checks until a valid name for the company has been entered. What you need to do Task 1 Modify the method AddCompany so that an appropriate error message is displayed if the user presses the Enter key without entering a company name when they are asked to enter the name of the company. Task 2 Modify the method AddCompany so that an appropriate error message is displayed if the user enters the name of a company that is already being used for a company in the simulation when they are asked to enter the name of the company. You may use the method GetIndexOfCompany to find out if a company name has already been used, though you do not have to use this method in your answer. Task 3 Test that the changes you have made work: run the Skeleton Program choose to use a normal size settlement choose to use the default companies choose the option to add a new company from the menu press the Enter key without entering a name for the new company type in the name AQA Burgers and press the Enter key type in the name In Jest and press the Enter key. Note: you will get three marks for your program code if either Task 1 or Task 2 has been successfully completed and you will get five marks if both Task 1 and Task 2 have been successfully completed. What you need to do Task 1 Create a new class called AffluentHousehold that inherits from the Household class. The constructor for this new class should make a call to the constructor of the Household class and then set the value of ChanceEatOutPerDay to 1 Task 2 Modify the AddHousehold method in the Settlement class so that it creates an AffluentHousehold object instead of a Household object if the randomlygenerated value for X is less than 100 Task 3 Test that the changes you have made work: run the Skeleton Program choose to use a normal size settlement choose to use the default companies then choose the menu option to display the details of the households and check that there is a mixture of both types of household in the settlement. Evidence that you need to provide Include the following evidence in your Electronic Answer Document. 1 1 . 1 Your PROGRAM SOURCE CODE for the amended method AddHousehold and the new class AffluentHousehold. [7 marks] 1 1 . 2 SCREEN CAPTURE(S) showing the requested test.

This question extends the Skeleton Program by adding the facility for a company to obtain a loan to increase their balance. When a company chooses to get a loan, 10 000 is added to their balance. The company should only be allowed to get a loan if they do not already have a loan that has not been paid back. The user will be asked to specify the daily interest rate for the loan. The company can pay back all or part of the loan at any time. The program should keep track of the amount of the loan that the company still needs to pay back. Each time the simulation is advanced by a day, the company will have their balance reduced by an amount equivalent to the interest rate applied to the amount of the loan minus any repayments that have been made. Figure 5 shows an example of the calculation. To get full marks on this question you will need to make use of encapsulation to hide attributes in the Company class. What you need to do Task 1 Add attributes to the Company class named LoanBalance and InterestRate. LoanBalance should be used to track the amount of the loan that the company needs to pay back. InterestRate should be used to store the interest rate at which the loan was taken. Task 2 Modify the ModifyCompany method in the Simulation class so that there are options on the menu to get a loan and to pay back a loan. Task 3 Modify the Skeleton Program so that if a company has a loan balance of 0 then it can take out a loan. When it does: 10 000 should be added to Balance and LoanBalance InterestRate should be set to the value specified by the user. Task 4 Modify the Skeleton Program so that when a company chooses to pay back a loan the user is asked how much to pay back and the values of LoanBalance and Balance are reduced by this amount. You do not need to check that the value entered is sensible or that the company has a loan to pay back.

Currently, the Skeleton Program creates a delivery route for a company based on the order in which a company's outlets have been created - the route starts with the oldest outlet, then goes to the second oldest outlet and so on until all the outlets have been included in the route. The route produced specifies the order in which the outlets are visited when making deliveries - the longer the route, the higher the delivery cost for the company. This question extends the Skeleton Program by using a greedy algorithm to try to reduce the total distance of the delivery route. A greedy algorithm is one that takes the choice which seems to be the best each time; it is not guaranteed to find the optimal solution. Figure 6 shows how the greedy algorithm should work. Figure 7 shows how the delivery cost is arrived at for the company Paltry Poultry which has four outlets. The outlet numbers (0-3) refer to the index of an outlet within the Outlets data structure for that company. This example may help you check your code works correctly. Figure 6 The greedy algorithm should: 1. start by adding the oldest outlet (the one in position 0 in Outlets) to the route 2. then find the company's outlet that is nearest (has the smallest distance) to the outlet that was last added to the route, and which has not yet been added to the route, and add this to the end of the route 3. repeat step 2 until all the company's outlets have been added to the route. Figure 7 The oldest outlet (outlet 0) is at coordinates (800,390) within the settlement; this will be the first outlet on the route. From this outlet the closest outlet is outlet 2 which is at (820,370) so outlet 2 will be added as the second outlet on the route. From outlet 2 the closest outlet not yet in the route is outlet 3 which is at (800,600) so outlet 3 will be added as the third outlet on the route. From outlet 3 the closest outlet not yet in the route is outlet 1 which is at (400,390) so outlet 1 will be added as the fourth outlet on the route. The correct order that the outlets should be visited is 0, 2, 3, 1 The delivery cost would be 6.96708