AQA AS/A Level Computer Science 1 - Hodder Education



WORKBOOK ANSWERSAQA AS/A Level Computer Science 1Fundamentals of programmingProgramming1aReal/float (1)bString (1)cDate/time (1)dInteger (1)eBoolean (1)2aA value that does not change throughout the program. (1)bAny one from: (2)If the programmer needs to change the value at a later time (1) they only need to update it once in the program. (1)Makes the code more readable (1) as someone reading the code can more easily understand what the value is for. (1)The same value is used each time (1) so less likelihood of errors (e.g. mistyping one instance of the value). (1)3ScoreMessage displayed25Oh dear… (1)60Not too bad (Note: 60 is not greater than 60) (1)30Not too bad (1)100Well done! (1)4aCondition-controlled loop (1)bCount-controlled loop (1)cWhen the number of times to repeat is not known. (1)5a3 (1)bOne from: (1)LengthWidthHeightcOne from: (1)AreaVolumed0 (1)One from: (1)Because the variable Area in the subroutine CalcVolume is local to that subroutine.Because the variable Area in the second part of the program has different scope to the variable Area in the subroutine CalcVolume.eAny two from: (2)Easier to reuse the subroutine in another program.The subroutine can be included in a library.Code is easier to understand.Makes sure the code is independent of the rest of the program.More memory efficient as the local variable only exists in memory while the subroutine is running.Makes the program easier to debug.fA function returns a value, a procedure does not (you must state both). (1)6a(For each table, correct sequence of values for f (1), correct return statement, at the correct point in the program. (1))iNumberfReturn statement5234TrueiiNumberfReturn statement252345FalsebOne from: (1)Check if a number is prime. Check if a number has no factors other than 1 and itself.7aA subroutine that calls itself. (1)bn <= 2 (1)cCall numbernxyValue returned14233212314112311214252114213Correct value returned by call number 4. (1)n, x, y and value returned given correct values for call number 2. (1)Correct value returned by call number 5. (1)n, x, y given correct values for call number 2. (1)Correct value returned by call number 1. (1)dAny two from: (2)Local variablesParametersReturn addresse3 (1)1, 2, 3 and 1, 2, 4 (1)Exam-style questions8aAny one from: (1)2, 3, 4, 7, 9, 11, 13, 14, 17(Note: Line 5 is an example of declaration, you cannot perform a separate assignment operation to a constant as it cannot be changed while the program is running.)bMAX_OVERS (1)cAny one from: (1)RunsOversBatterBallsScored10 (1)e6 (1)fBecause the number of times to repeat is not known. (1)9aAll correct variable declarations for Denary and Pos. (1)(Note: If using Python (or any language that doesn’t require explicit declaration) then the mark would be given as long as the variable is used and the first value it is assigned if of the correct data type.)Correct variable declaration for Binary. (1)Correct prompt “Enter a whole number between 0 and 15”. (1)Denary assigned the value entered by the user. (1)FOR loop with suitable syntax and the correct number of iterations. (1)Correct assignment of Denary MOD 2 to the correct position in the array (the rightmost unassigned element). (1)Correct assignment of Denary DIV 2 to Denary. (1)Correct output of the completed array, reading left to right. (1)Ignore upper/lower case, typos (as long as variable names consistent) and spacing including prompts. Allow a solution that prints each binary digit on a new line.Example Java solution:AQAConsole console = new AQAConsoleint[] Binary = {0,0,0,0}int Denary = console.readInteger("Enter a whole number between 0 and 15")final int BITS = 4for (int i = 0; i < BITS; i++){ int Pos = BITS - 1 - i Binary[Pos] = Denary % 2 Denary = Denary/2}for (int i = 0; i < BITS; i++){ console.print(Binary[i])}Example Python solution:Binary = [0,0,0,0]Denary = int(input("Enter a whole number between 0 and 15: "))BITS = 4for i in range(BITS): Pos = BITS - 1 - i Binary[Pos] = Denary % 2 Denary = Denaryfor i in range(BITS): print(Binary[i])b(Must match the code from part (a), including the prompts. Code must be sensible. (1))Enter a whole number between 0 and 15: 131101(Allow a test that prints each digit on a new line.)cCould be used on the input to make sure it is an integer. (1)The program could assume a default value or ask the user to enter a new value. (1)Programming paradigms1(Mark in pairs – 1 mark for a relevant point, 1 mark for expansion. [4 max])Code can be called from different points in the program … (1)… reducing the need to duplicate code. (1)ORCode is easier to update/maintain … (1)… because the programmer only needs to update one subroutine no matter how often it is used. (1)OREasier to debug code … (1)… because an error will likely only need to be found and fixed once. (1)2aDisplayRules (1)bPlayOneRound (1)cDecideWinner (1)dOne from: (1)Uses subroutinesUses functionsUses procedures3aOne from: (1)MakeModelEngineSizeFuelTypeFuelLevelbOne from: (1)CarDrivePark(Note: Ignore/allow parentheses and public/private notation.)cOne from: (1)ApplyHandbrakeReleaseHandbrakedGetFuelLevel (1)eCar. The constructor must always have the same identifier as the class. (2)fInstantiation is the process of creating an object based on a class. (1)It is carried out using the constructor providing values for each of the attributes. (1)gOne from: (1)A class relates to a type of real-world object.A class describes a type of object.A class lists the attributes and methods that a type of object will have.One from: (1)An object is a specific instance of that class.An object is an object based on a class.hPublic methods can be accessed/called by any class. (1)Private methods can only be accessed/called by that class. (1)Protected methods can only be accessed by a derived class/subclass (and itself in some languages). (1)(Note: Allow ‘object’ instead of ‘class’.)iOne from: (1)The FuelLevel attribute is private and so can only be accessed within this class.The GetFuelLevel method is public and so can be accessed within other classes.jOne from: (1)This allows classes to maintain control over their own attributes.This allows for the way that the FuelLevel is stored to be changed in the future without having to rewrite or modify code in other classes.4aA class/subclass/child class that shares/can access attributes or methods from a base class/parent class. (1)bCommercialVehicle (1)cOne from: (1)TaxiLorrydThe attributes and methods in the base/parent class can be reused in each sub/child class. (1)One from: (1)Avoids duplication of code.Makes the code easier to maintain or update.5ECycle = Class (Bicycle)Private:MaxCharge: IntCurrentCharge: IntPublic:Function: FullyCharged()Function: IsEmpty()Correct header including name of class (ECycle) and parent class (Bicycle). (1)Defining attributes (accept any numeric data type). (1)(No mark if inherited attributes explicitly included.)Defining methods. (1)(No mark if inherited methods explicitly included.)Correct declaration of public/private. (1)6aOne from: (1)PolymorphismOverridingOne from: (2)The Move() method in the (abstract) Animal class has been overridden in each of the subclasses.The Move() method in the Mammal/Bird classes has been implemented differently to the Move() method in the Animal class.(Note: The question relates to function [what is happening] rather than justification [why has it been done this way].)bBirds and mammals both move in very different ways (allow birds move by flying, mammals move on legs) so need their own implementations of Move. (1)All animals can move so it is appropriate to include this in the base class. (1)c'Encapsulate what varies' means that individual classes should only contain attributes and methods that differ from other classes. (1)Any suitable example of an attribute or method that varies, e.g. only birds have a wingspan. The design in Figure 13 is heavily abstracted so accept responses that fit this abstraction, e.g. only mammals walk on two or four legs, only mammals have different types of diet. (1)7aRoom = Class(Building)Private:Windows: BooleanRent: IntOccupied: BooleanPublic:Function: GetWindowsFunction: GetRentFunction: GetOccupiedProcedure: SetDetails ()Correct header, including name of class and name of parent class. (1)Three correct definitions for functions, labelled as public. (1)Three correct definitions for attributes, labelled as private. (1)Overriding SetDetails procedure. (1)bAssociation aggregation describes a ‘has a’ relationship between two classes where both exist independently. (1)In composition aggregation the parent class is composed (made up) of the child class objects, so if the parent object is destroyed, so are the child objects. (1)cIf the building is destroyed (or removed from the system), then so are the rooms. (1)Exam-style questions8aGetChoices (1)bMakeSandwich (1)cAddMeat (1)dAny two from: (2)Passing values/arguments/parameters to subroutines.Returning values/arguments/parameters back from functions.Using constants/global variables.eAny two from: (2)Code can be reused.Each change to the code only needs to be updated once.Easier to find and debug errors.9aStudent = Class (Person)Private:Tutor: TeacherPublic:Function: GetTutorProcedure: EnrolProcedure: SetupDetails ()Correct header, including name of class and name of parent class. (1)Correct definition for Tutor attribute, including data type, labelled private. (1)Correct definition for Enrol procedure, labelled public. (1)Correct definitions for GetTutor and SetupDetails (overridden), labelled public. (1)bAssociation aggregation (1)cBoth forms of aggregation represent a ‘has a’ relationship. (1)With composition aggregation, if the parent class is destroyed then the child class is destroyed also. (1)In this case, if a student is destroyed, the teacher still exists (so association aggregation is more appropriate). (1)d'Overriding' is creating a method in a subclass that has the same identifier as a method in a parent class … (1)… in order to give the subclass method more/different functionality. (1)In this case, the subclasses have more/different attributes to set and so different functionality/code/algorithm is required. (1)Fundamentals of data structuresData structures1a9 (1)bOne from: (1)4[4]Numbers[4]ciTotalNumbers[0][1][2][3][4]0739126071216328434i column correct. (1)Total column correct. (1)2a8 (1)bR[2,3] (1)cOne from: (1)[1,3]R[1,3]dijTA[0][1][2]00000091162243287100618211312320071152233328Correct sequence for i, only changing after each sequence of j complete. (1)Correct sequence for j. (1)Correct sequence for T, including resetting back to 0 after updating i.(1)Correct sequence for A, only changing after each sequence of T. (1)Correct values for A at the completion of the dry run. (1)eTo calculate the (mean) average for the values in each row/record. (1)3aReduced file size. (1)As only 2 bits are needed to store each dog type. (1)bOnly this program will be able to decode the data/understand which code is which dog type. (1)The file could not be read/opened/understood by general purpose software (e.g. a text editor). (1)Exam-style questions4a1 (1)bTDiV012801281286410322016316144848152454156260170Correct sequence for i. (1)Correct sequence for D. (1)Correct identification of 128, 16, 8 and 4 for V. (1)Correct addition of values from V into T (allow follow on marks). (1)Final value for T correct. (1)cTo convert a binary number into its denary equivalent. (1)5aIn text files all values are stored using a character set/ASCII/Unicode/characters. (1)One from: (1)In binary files data is stored using different data types.In binary files data can only be read by the application that created them.bOne from: (1)The files could be opened in a text editor or other general purpose application.The values in the file would be human readable.cAny one from: (1)Smaller file size.Data more secure/not human readable so cannot be easily altered (must be some context).Developer can maintain more control over the program/data.6aijkOutput111F22T3F4F2112T2F33T44T311F22T3F43T411F22T33T4FCorrect sequence for i, as an outer loop. (1)Correct sequence for j, as an inner loop. (1)Correct sequence for k when i = 1. Must match values of j. (1)Correct sequence for Output when i = 1. Must match values of k. (1)Correct sequence for k and Output when i = 2. (1)Correct sequence for k and Output for remainder of the algorithm. (1)bAL[1][2][3][1]200[2]134[3]240[4]230(Max 2 marks)Table completed correctly (allow blank spaces instead of zeros). (2)Table matches result of part (a) (value of j inserted in position [i,k] when Output is T). (1)Abstract data types1aArray (1)bList (1)cA static data structure has a fixed size/the size of a static data structure cannot be changed. (1)The size of a dynamic data structure can be changed. (1)2aLIFO – the most recently added item/transaction will be the first one to be accessed/carried out (not enough to state Last In First Out). (1)FIFO – the items/transactions will be accessed/carried out in the order they were entered (not enough to state First In First Out). (1)A queue is FIFO. (1)b(Mark in pairs – 1 mark for correct problem, 1 mark for associated solution.)The program could attempt to dequeue an empty queue … (1)… so there should be a check for an empty queue. (1)ORThe program could attempt to add a transaction to a full queue … (1)… so there should be a check for a full queue. (1)cLinear queueOne from: (1)In a linear queue the front of the queue is moved back/up as each item is dequeued.Empty spaces will be left as the front of the queue moves back.One from: (1)In a static data structure this means the queue will eventually be exhausted.In a dynamic data structure this will lead to a large number of empty spaces before the front of the queue, wasting memory.Priority queueOne from: (1)In a priority queue the position or index of each item will be moved up as each item is dequeued.Each item will move one place forward in the queue as the previous item is dequeued.One from: (1)In a static data structure this will prevent the queue from becoming exhausted.This will prevent the inefficient use of memory storing empty spaces in the queue.dLinear queueOne from: (1)In a linear queue the front of the queue is moved back/up as each item is dequeued.Empty spaces will be left as the front of the queue moves back.One from: (1)In a static data structure this means the queue will eventually be exhausted.In a dynamic data structure this will lead to a large number of empty spaces before the front of the queue, wasting memory.Circular queueOne from: (1)In a circular queue, pointers to the front and back of the queue will be moved as items are dequeued and enqueued.The first and last positions in the array will not necessarily mark the front and back of the queue.One from: (1)In a static data structure this will prevent the queue from becoming exhausted.This will prevent the inefficient use of memory storing empty spaces in the queue.ePriority queueOne from: (1)In a priority queue the positions or index of each item will be moved up as each item is dequeued. Each item will move one place forward in the queue as the previous item is dequeued.One from: (1)Though space efficient, there is a large overhead in terms of moving each position up one place in the queue, especially for a large queue.More code/execution time is required to implement a priority queue over a circular queue.Circular queueOne from: (1)In a circular queue, pointers to the front and back of the queue will be moved as items are dequeued and enqueued.The first and last positions in the array will not necessarily mark the front and back of the queue.One from: (1)Two extra variables are required to point to the current front and back of a circular queue.Less space efficient as more variables are needed.Can be harder to identify the front and back of the queue by inspection at runtime.3 aOne from: (1)Hiding/removing unnecessary details.Only including the details that are necessary to solve the problem.b(1)Type of diagramTick one box onlyUnconnected graphDirected graphWeighted graphUndirected graphcThere are cycles/loops in the graph. (1)dADBC, ECB, EDA, EEB, C, D(Max 2 marks)Three correct rows. (1)All rows correct. (2)(Ignore the order of nodes.)eABCDEA00010B00101C01001D10001E01110(Max 2 marks)2 rows correct. (1)All rows correct. (2)fLarge, sparsely populated graphs. (1)Where the edges/arcs/connections don’t need to be examined/updated frequently. (1)4aArrSizeijM[i,j]Append (Y/N)5110N2123N345Y481Y512Y21123N20N334Y482Y5217N3145Y234Y30N4161N551Y4181Y282Y3161N40N526Y5112Y2217N351Y426Y50NCorrect sequence for i as an outer loop. (1)Correct sequence for j as an inner loop. (1)Correct sequence for M[i,j]. (1)Correct sequence for Append based on values in M[i,j] column. (1)bL123451345234312541255134(Max 2 marks)Three rows correct.(1)All rows correct. (2)(Max 1 mark if the sequence is correct but written vertically.)cAny two from: (2)Adjacency matrixGraphDatabasedTo identify which radio towers are less than 100 km apart in order to: (1)One from: (1)identify potential interferencedecide on frequenciesfind the smallest number of frequenciesreference the 'poor cartographer’s problem'.5aC (1)bA (1)cB (1)dOne from: (1)BDeAny two from: (2)Store an ordered list.Represent hierarchical data.Store a list so it is easily searchable.fA tree that has one node designated as the root (1) and all other nodes are directed away from that root. (1)gA tree where each node has a maximum of two child nodes. (1)hOne from: (1)A binary search treeStoring data so that it can easily be searched.in m p o (1)6a3 (1)b5 (1)cOne from: (1)The two names would be written to the same address.The new name would overwrite the old one.(Not enough to say ‘collision’ without explanation.)One from: (1)Store the new name in the next open address in the hash table.Store a pointer that points to a list of values that have the same key.dA larger hash table is created. (1)Each item in the existing hash table has a new key calculated … (1)… according to a new hashing algorithm. (1)eFaster to search than an unsorted array/list/data structure. (1)No need to re-sort/move items when adding new records. (1)fHowAny two from: (2)Complex hashing algorithms are used to generate complex keys.The keys are stored instead of the password.Each time the user enters their password, the hashing algorithm is applied and the key is compared to the value that is stored.WhyAny one from: (1)In the event of a data breach, only the hashed keys can be discovered.A malicious user who is able to access the hashed keys will not be able to log in.7a'is' (1)bOne from: (1)To identify each unique word in the sentence.As part of a text compression algorithm.cTo find the number of occurrences for each word in the sentence. (1)dA key–value pair (1) in which the value is accessed via the associated key. (1)8aArrow goes from [2,6] to [9,9]. (1)Correct labels for u and B. (1)b[2,6] + [7,3] (1) (Evidence of adding first digit with first digit.)[9,9] (1)cArrow goes from [0,0] to [9,9] and is correctly labelled ‘w’. (1)Written answer: [9,9]. (1)dTranslation (1)eScaling (1)fi[21,9] (2) (1 mark per value)ii[–4,–12] (2) (1 mark per value)iii[3.5,1.5] (2) (1 mark per value)gu v = u0v0 + u1v1= 2*7 + 6*3 (1 mark for showing understanding of how to apply the formula)= 14 + 18 (1 mark for correctly calculating each value)= 32 (1 mark for reaching the correct answer)hFinding the angle between two vectors. (1)iOne from: (1)The sum of the coefficients is not 1 0.2 + 0.9 = 1.1 Meaning that the position P cannot be a point in the convex combination of the two vectors. (1)Exam-style questions9 aOne from: (1)Last In First Out structure. (Not enough to say LIFO.)It follows the game description in that the last card placed on the pile is the first card to be drawn back out.bQueue (1)cJack of diamonds (1)dFUNCTION DealCard()IF StackSize > 0 THENTemp DeckStack[StackSize]DeckStack[StackSize] NoneStackSize StackSize – 1RETURN TempENDIFRETURN “Error, no such card”ENDFUNCTIONSelection statement to check if the size is bigger than 0/stack is empty. (1)Returning or reporting an error in the appropriate place. (1)Topmost value stored in a temporary variable and replaced with ‘None’. (1)StackSize variable decremented. (1)Temporary variable returned. (1)10a[7,3] (1)bCorrectly labelled at [7,3]. (1) (Don’t punish twice, give the mark as long as the position is marked according to the answer given in (a).) c[13,–12] (1)d[–4,–1] (2) (1 mark per value)eu v = (–4 * 2) + (–5 * –1) = –8 + 5 = –3Allowed = “No”Clear evidence of applying dot formula method: u1v1 + u2v2 (1)Correct value, –3. (1)Identifying that the value of allowed is “No”. (1) (Allow if no speech marks.)f[5,8] * 0.7 = [3.5, 5.6][7,3] * 0.3 = [2.1, 0.9]D = [5.6, 6.5]Correctly multiplying EITHER vector by the correct scalar value. (1)Correctly calculating the value of D. (1)gAlphaBetaPlotted on line BC?01Yes31No0.10.9Yes0.6–0.4No0.550.45Yes–0.21.2NoAlpha + Beta must equal exactly 1.Alpha and Beta must each be between 0 and 1.(Max 3 marks)Two correct answers. (1)Four correct answers. (2)All correct answers. (3)Fundamentals of algorithmsGraph traversal, tree traversal and Reverse Polish Notation1 aOne from: (1)Navigating a maze.Creating a minimum spanning tree.Detecting a cycle in a graph.bQueue (1)One from: (1)Because a breadth-first search requires the algorithm to record all of the nodes one step away from the starting node, and then revisit each of those nodes again to check for additional nodes, in order.A queue is a first in first out (FIFO) data structure and the nodes will be visited in the order they are found.cA graph may have cycles (but a tree won’t). (1)2VTDiscoveredStack01234567Bottom Top07FFFFFFFF00EmptyT112123312T125512T12412466124T412T127712T1 mark for having the correct value changes in each section, with no incorrect value changes within that section.(Max 6 marks)3ai19 + 3 (1)ii(12 * 4 ) + 6 (1) (Brackets not required.)bStack (1)c3 + 5 ÷ 15 – 11 (1)d3 5 + 15 11 – ÷ (1)eInfix notation (1)fReverse Polish Notation (1)gOne from: (1)Ambiguity/error caused by lack of/need for brackets.More complex for a machine/computer to evaluate.More complex to design an algorithm to evaluate.Need to account for order of precedence/BIDMAS/BODMAS.Exam-style questions4aQueueDiscoveredParentSTFFront BackABCDEFGABCDEFGVAGFATFFFFFFEmptyABTAB CTACBC DTBC D ETBD ECEDE FTDFEF GTET1 mark for each boxed area being correct, with no additional values.(Max 5 marks)bBreadth-first search (1)cDepth-first search (1)Navigating a maze (1)5 aOne from: (1)TreeRooted treeBinary treebPre-order (tree traversal) (1)c(Some) graphs that aren’t trees contain loops. (1)6a4 + 3 * 3 (1)bOrder of precedence/BIDMAS/BODMAS/no brackets/ambiguity. (1)cIn-order (tree traversal) (1)dPost-order (tree traversal) (1)ei2 * 6 (1)ii(4 + 3) – 2 (1) (Brackets not needed, shown for clarity.)iii(7 * 4 + 2)/10 (2) (1 mark for 7 * 4 + 2)(1 mark for accurate answer, including brackets where needed.)Searching, sorting and optimisation algorithms1aFirstLastFoundFailedMidpointOutput07FalseFalse345TrueFound it!Correct sequence for First and Last. (1)Correct sequence for Midpoint. (1)Correct sequence for Found, Failed and Output. (1)(Note: Found and Output must be the last two values to be changed.)bFirstLastFoundFailedMidpointOutput07FalseFalse32122TrueSorry, not foundCorrect sequence for First and Last. (1)Correct sequence for Midpoint. (1)Correct sequence for Found, Failed and Output. (1)(Note: Found and Output must be the last two values to be changed.)cOne from: (1)Faster to search.Fewer comparisons needed.dOne from: (1)List must be sorted first.Linear search is easier/simpler to program.2a[0][1][2][3][4][5]359411212 at the far right. (1)All other values correct. (1) bAnswer 1iEven if the list is fully sorted before the bubble sort is complete, it will continue to run unnecessarily. (1)iiAny two of: (2)A flag can be used inside the outer loop to check whether any swaps were needed – set to False/0.If a swap is needed then the flag should be set to True/1.A WHILE loop based on the value of the flag will repeat while the flag is True/1.iii(2)FUNCTION Bubble (Scores)Length Scores.LENGTH()Swaps TrueWHILE Swaps = True DOSwaps FalseFOR j 1 TO LENGTH – 1 DOIF Scores[j] > Scores [j+1] THENTemp Scores[j]Scores[j] Scores[j+1]Scores [j+1] TempSwaps TrueENDIFENDFORENDWHILERETURN ScoresENDFUNCTION(Also accept an answer with the reverse logic, e.g. a flag called Finished, a WHILE loop that repeats while Finished = False and the flag logic reversed throughout.)Answer 2iAt the end of the first pass, the last item in the array is guaranteed to be in the correct place. (1)iiOn the second pass (and subsequent passes), the inner loop should be run fewer times. (1)The number of steps in the FOR loop should be decremented by the current value of the counter in the outer loop. (1)iiiFUNCTION Bubble (Scores)Length Scores.LENGTH()FOR i 1 TO LENGTH – 1 DOFOR j 1 TO LENGTH – i DOIF Scores[j] > Scores [j+1] THENTemp Scores[j]Scores[j] Scores[j+1]Scores [j+1] TempENDIFENDFORENDFORRETURN ScoresENDFUNCTIONClear attempt at implementation of a valid solution. (1)Correct implementation. (1)3center422052700-24447383603500aUVAltDistPreviousQABCDEFGABCDEFGABCDEFG∞∞∞∞∞∞∞0ABCDEFGB55AG33AGBCDEFB9F1010GBCDEFC1717BF99BFCDEE1111FECDC1616ED2121ECDD2020CDEmpty1 mark per boxed section (max 6)bABCDEFGAECFBAAll correct (1)cA, B, F, E, C, D (1)(Allow the mark if A is excluded.)Exam-style questions4aNot sorted/not in order. (1)bLinear search (1)cGerman, Computer Science, Maths, Media Studies (1)dGerman, Computer Science and Maths (1)Art, English and Media Studies (1)e3 (1)fGerman, Computer Science, English (1)5aijTempArray[1][2][3][4][5][6]2161243652115312911216124216233652113654365533655365129365i and j columns correct. (1)Temp column correct. (1)Correct swaps in the array columns. (1)bBubble sort (1)c[1][2][3][4][5][6]12453129211216365211, 216 and 365 in the correct places. (1)Completely correct. (1)Theory of computationAbstraction and automation1(It may help to draw a Venn diagram to help visualise the logic.)aiv (1) (No conclusions can be drawn.)biii (1) (The two conclusions are opposite, so one must be true.)Regular and context-free languages1aInput stringAccepted by FSM?aaaacYES (1)abcNO (1)abaacdbYES (1)bAny three from: (3)Strings that:start with a number of ‘a’smay or may not be followed by a ‘b’ and any number of ‘a’s are followed by a ‘c’ may or may not be followed by any number of ‘ab’. 2aS8 (1)bA subset of S1 is any set that contains only values from S1 (1), e.g. S2/S7/S9. (1)One from: (1)A proper subset of S1 is any set that contains only values from S1, but does not contain all values from S1.A proper subset of S1 is any set that contains some but not all values from S1 and nothing else.For example: S2 or S9. (1)cS4 or S5 (1)dS10 (1)eOne from: (1)S2 = S1 – S9S2 = S7 – S9S1 – S9S7 – S9{m,n,p} – {p}fOne from: (2: one mark for each cartesian value){ (r,m) , (r,n) }{ (m,r) , (n,r) }3a0 or more (1)b1 or more (1)cInputAcceptedacdYES (1)bcccccdYES (1)accccNO (1)abccdNO (1)d0 or 1 (1)eInputRegular expressionAcceptedcolorcolou*rYEScolourcolou*rYEScolouurcolou*rYEScolorcolou?rYEScolourcolou?rYEScolouurcolou?rNOAll responses for colou*r correct. (1)All responses for colou?r correct. (1)4a<name> (1)bOne from: (1)A non-recursive case.A case that doesn’t include an example of the definition within the definition.cRule numberCould be defined using a regular expression1YES2YES3NO4NO5NO6NO7YESAll correct (1)dDefinitions involving recursion cannot be defined using a regular expression. (1)eKCnameAcceptedYpres Prince Hektor – Miniature SchnauzerYESSpike – DaschundNOShergar Bernhard T – DobermanNOKilcullen Rocky – SpanielYESAll correct (1)Exam-style questions5aThe hairdryer is set to on, and hot. (1)bOriginal stateInputNew stateS2ColdS1S2OnS4S4ColdS3S4OffS2Both rows for S2 correct. (1)Both rows for S4 correct. (1)Ignore order of responses.c2 (1)(The FSM would now need states for Off–Cold, Off–Hot, Slow–Cold, Slow–Hot, Fast–Cold, Fast–Hot: a total of six states, where there are currently four.)6aInputOutput01100011 (1)1001 10100100 1101 (1)0101 01010010 1010 (1)bLogical shift right (1)7aRegistration plateAcceptedRRM55GNOG55RRMYESF612RTNOL731PRMFNOT527QHIYESAll correct (1)bThe registration is for a kit car or a rebuilt car. (1)cAny of:\l\d\d?\d?\l\l\l|\l\l\d\d\l\l\l \l\d?\d?\d\l\l\l|\l\l\d\d\l\l\l \l\d?\d\d?\l\l\l|\l\l\d\d\l\l\l Allow [A-Z] for \l and [0-9] for \dAllow second half|first halfRule 1: number plate starts with one letter. (1)Rule 1: number plate has one required and two optional digits. (1)Rule 1: number plate ends with three letters. (1)Rule 2: number plate has two letters, two digits, three letters. (1)Classification of algorithms1aO(n) (1)bO(n2) (1)cO(logn) (1)dO(nlogn) (1)eO(1) (1)fO(n!) (1)gO(logn) (1)2 aOne from: (1)Space complexityMemory requirementsbOne from: (1)O(1)O(logn)O(n)O(nlogn)O(n2)O(n+m)Any time complexity <= polynomial timecOne from: (1)O(kn)O(n!)Any time complexity >= exponential time.dOne from: (1)A problem that can be solved.An algorithm exists.One from: (1)But it cannot solve the problem in polynomial or less time.But it cannot be solved quickly enough to be useful.eAny two from: (2)Use a heuristic algorithm. OR Example of heuristic algorithm (e.g. greedy, hill climbing, local improvement, etc.)Accept a sub-optimal/non-optimal/imperfect solution.Use an estimate based on experience.Relax some of the constraints of the problem. OR Solve a simpler version of the problem. OR Reduce the complexity of the problem.fProblemClassificationFinding an item in an ordered listTractable (1)The travelling salesman problemIntractable (1)The Halting problemUnsolvable (1)Sorting a list into orderTractable (1)Checking every combination of letters in an anagram solverIntractable (1)gIt is impossible to know (1) whether a program will eventually stop if given a particular input. (1)A model of computation1aStatementTrue or FalseIf an algorithm exists to solve a computational problem then a Turing machine can be designed to solve the problemTrueIf no algorithm exists to solve a computational problem then no Turing machine can be designed to solve itTrueSome computational problems which can be solved by an algorithm cannot be solved by a Turing machineFalseAll values correct (1)bStep 2 correct (1)Steps 3 & 4 correct (1)Steps 5 & 6 correct (1)cOne from: (1)Logical shift rightRight shiftExam-style questions2aStep 2 correct (1)Step 3 correct (1)Step 4 correct (1)Steps 5 & 6 correct (1)Steps 7–9 correct (1)Step 10 correct (1)bOne from: (1)Convert between positive and negative binary numbers.Carry out 2s complement conversion. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download