Postcodes are used to aid the sorting of mail and help to ensure…

Question Answered step-by-step Postcodes are used to aid the sorting of mail and help to ensure… Postcodes are used to aid the sorting of mail and help to ensure that mail being sent arrives at the correct destination as quickly as possible. The format of a UK postcode (ignoring any spaces) is shown in Figure 2. Figure 2 • 1 or 2 letters • followed by: o 1 numeric digit or o 2 numeric digits or o 1 numeric digit then 1 letter • followed by 1 numeric digit • followed by 2 letters When a post box is emptied in the town of Ipswich the mail in the post box is taken to a central sorting office. Each item is looked at and placed in one of three vans depending upon the postcode written on the envelope. Postcodes that begin with IP1, IP2, IP3 or IP4 followed by one numeric digit and two letters, eg IP2 8QY, are for mail being sent to an address in the town of Ipswich and go in Van A. Other postcodes that begin with IP, eg IP5 3QW, are fo…r areas not in the town but near to Ipswich and go in Van B. Postcodes that start with anything other than IP, eg CO3 5FN, are not for the Ipswich area and go in Van C. IP postcodes do not use the full range of formats available for UK postcodes. A finite state machine (FSM) could be used to sort mail using postcodes. Figure 3 shows a state transition diagram for an FSM used at the Ipswich sorting office. In Figure 3, if a transition is not defined from a state for a particular input symbol then the FSM will stop processing the input and it will be rejected.If the FSM in Figure 3 reaches state S12 what does it mean?If the FSM in Figure 3 finishes at state S11 what does it mean?Assuming that the FSM in Figure 3 can be used to recognise any valid IP postcode, state one format used for UK postcodes that IP postcodes do not use.Image transcription textFigure 3 51 Letter (except !) 814 Letter (except P) Letter Numericdign $13 Numeria 112134 digit 567189 Numeric digit $16 54 55Numeric Letter Numeric cigit digit Numeric Numeric Gig… Show more… Show moreFigure 2 • 1 or 2 letters • followed by: o 1 numeric digit or o 2 numeric digits or o 1 numeric digit then 1 letter • followed by 1 numeric digit • followed by 2 letters.The language recognised by an FSM can also be represented by a regular expression. When writing regular expressions d is used to represent any numeric digit and a is used to represent any alphabetic character. For example, the regular expression d d a d describes the language of all strings that contain two numeric digits followed by one letter and then one numeric digit. Write a regular expression that represents a valid UK postcode as described in Figure 2. In your answer you should only use the | metacharacter once.Table 2 lists some well-known algorithms. Table 2 Algorithm Linear search Merge sort Binary search Post-order tree-traversal 0 3 . 1 Which of the algorithms listed in Table 2 has ??(?? log ??) time complexity? How many of the algorithms listed in Table 2 are algorithms used to solve tractable problems?State the time complexity for the bubble sort algorithm in terms of ??, where ?? is the number of items in the list to be sorted. Explain why the bubble sort algorithm has the time complexity stated in your answer to o  3. 3. Figure 4 shows the data Norbert, Phil, Judith, Mary, Caspar and Tahir entered into a binary search tree. Figure 5 contains pseudo-code for a recursive binary tree search algorithm. Figure 4 Norbert Judith Phil Caspar Mary Tahir Figure 5 FUNCTION TreeSearch(target, node) OUTPUT ‘Visited ‘, node IF target = node THEN RETURN True ELSE IF target > node AND Exists(node, right) THEN RETURN TreeSearch(target, node.right) ELSE IF target < node AND Exists(node, left) THEN RETURN TreeSearch(target, node.left) ENDIF RETURN False ENDFUNCTION The subroutine Exists takes two parameters - a node in the binary tree and a direction (left or right). It returns a Boolean value indicating if the node given as a parameter has a child node in the direction specified by the second parameter. For instance, Exists(Mary, left) will return a value of False as there is no node to the left of Mary in the binary tree. node.right evaluates to the child node to the right of node, eg Judith.right is Mary. node.left evaluates to the child node to the left of node, eg Judith.left is Caspar. What is meant by a recursive subroutine? [1 mark] 0 4 . 2 There are two base cases for the subroutine TreeSearch. State one of the base cases. [1 mark] 0 4 . 3 Complete the unshaded cells of Table 3 to show the result of tracing the TreeSearch algorithm shown in Figure 5 with the function call TreeSearch(Olivia, Norbert). You may not need to use all of the rows. Function call Output TreeSearch(Olivia, Norbert) Copy the contents of the unshaded cells in Table 3 into the table in your Electronic Answer Document.  The hero is going to move. The current position of the hero can be described by the vector [5, 2]. The movement of the hero can be described by the vector [3, 1]. To process the movement the game updates the screen using the following operation: new position = current position vector + movement vector The dot product can be used to calculate if the enemy can see the hero by using the algorithm given in Figure 7. Figure 7 u ? [1, 1] v ? [position of hero] - [position of enemy] IF u.v > 0 THEN EnemyCanSee ? True ELSE EnemyCanSee ? False ENDIF 0 5 . 2 Perform vector addition to calculate the new position of the hero. [1 mark] 0 5 . 3 Complete the unshaded cells of Table 4 to work out if the enemy can see the hero in this new position.Calculation Result u [1, 1] v = [position of hero] – [position of enemy] u.v EnemyCanSee Copy the contents of the unshaded cells in Table 4 into the table in your Electronic Answer DocumentTwo frequently completed actions when using a particular piece of software are undo and repeat. The undo action results in the state changing from the current state to the state previous to the user’s most recent action, eg if the last action the user completed was to change the font of a selected piece of text from Courier New to Chiller then if the undo action is selected the result will be to change the font of that text back to Courier New. The user is able to keep using the undo action to go back through all previous states. The repeat action results in the user’s most recent action being applied again, eg if the last action the user completed was to change the font of a piece of text to Chiller then if the repeat action is selected the result will be to change the font of the currently selected text to Chiller. The user is able to keep using the repeat action to apply the most recent action multiple times. The repeat action will only work when there is a most recent action that can be applied again. 0 6 . 1 Explain how a single stack can be used in the implementation of the repeat action and the undo action. [5 marks] 0 6 . 2 State the type of error that occurs if the user tries to complete an undo action before they have completed any other actions.One method that can be used to compress text data is run length encoding (RLE). When RLE is used the compressed data can be represented as a set of character/frequency pairs. When the same character appears in consecutive locations in the original text it is replaced in the compressed text by a single instance of the character followed by a number indicating the number of consecutive instances of that character. Single instances of a character are represented by the character followed by the number 1. Figure 9 and Figure 10 show examples of how text would be compressed using this method. Figure 9 Original text: AAARRRRGGGHH Compressed text: A 3 R 4 G 3 H 2 Figure 10 Original text: CUTLASSES Compressed text: C 1 U 1 T 1 L 1 A 1 S 2 E 1 S 1 What you need to do Task 1 Write a program that will perform the compression process described above. The program should display a suitable prompt asking the user to input the text to compress and then output the compressed text. Task 2 Test the program works by entering the text AAARRRRGGGHH. Task 3 Test the program works by entering the text A.Evidence that you need to provide Include the following in your Electronic Answer Document. 0 7 . 1 Your PROGRAM SOURCE CODE. [12 marks] 0 7 . 2 SCREEN CAPTURE(S) for the test showing the output of the program when AAARRRRGGGHH is entered. [1 mark] 0 7 . 3 SCREEN CAPTURE(S) for the test showing the output of the program when A is entered. Computer Science Engineering & Technology Java Programming Science JAVA412 Share QuestionEmailCopy link Comments (0)