9-12 marks Paper2

Compare the use of a breadth-first traversal and a depth-first(post-order) traversal on the binary search.[9]

• Breadth-first takes the first value then visits all nodes connected to it.

• It then takes all nodes connected to those nodes.

• Depth first goes to the left node, this becomes a new tree.

• It continues going to the left until a leaf

• It then returns this, then goes right and repeats from the start.

• Follow left, follow right, take root.

• Breadth will return …….

• Post-order returns …..

• Breadth is more efficient when the data searched for is closer to the root.

• Breadth in general is better time complexity.

• Depth= more efficient when data is to be search for is further down.

Compare the use of a breadth-first traversal and a depth-first (post-order) traversal on the binary search tree.

You should include the following in your answer:

• how each traversal works

• the order of the return values for each traversal.[12]

• Merge sort splits data into individual lists and merges .

• Insertion makes first value sorted list, then inserts each item into the sorted list.

• Bubble sort looks through each item in turn, number of items times.

• Merge uses more memory as new lists are needed. Insertion and Bubble need constant memory.

• Bubble and Insertion have the best best times, both O(n) because they run through the data once. merge sort requires a minimum number of stages so best case is longer (O(n log(n)).

• Merge average is the same as best. Insertion and Bubble has average o(n^2).

• Worst time merge has same has best and average because same number of stages are needed.

• Bubble sort and insertion all have worse O(n^2).

• There are a small number of elements (10) therefore a bubble sort of insertion would be better space wise because no further space is needed.

• Merge would not need excessive amounts of more memory as there are only a small number of elements.

• Time complexity, there is a small number of elements therefore Bubble and Insertion may be preferable. Differences are unlikely to be significant, so either would be more appropriate.

Discuss the use of object-oriented programming and procedural programming to create and manipulate the queue data structures.

You should include the following in your answer:

• the features of object-oriented programming

• the features of procedural programming

• the benefits of using object-oriented instead of procedural programming when creating several queue structures.[9]

• OOP defines an object as an independent entity •

• OOP defines the attributes of the object and the methods that can be applied to it

• attributes could be private to restrict accidental changes

• Procedural the statements are executed in the order they are written.

• OOP allows for an object to be created from the queue.

• Many instances of this queue can then be declared in the main program.

• Procedural will need each queue to be declared individually.

• Procedural will need to make use of subroutines where the queue will need to be sent and returned each time.

• OOP you can create multiple instances of the queue as required by the program without having to re-write all of the declarations etc. In procedural you would have to write separate code for each new stack.

• OOP reduces amount of code needed therefore fewer errors are likely as code is written once and then used multiple times

• OOP can reduce mistakes because the subroutines are self-contained in procedural it would need to make sure the correct values are passed and returned, or global variables may be required which uses excess memory

Evaluate how Taylor can use data mining to inform future changes to improve his circus game.[9]

• Data mining searched large amounts of data.

• Searches for relationships between facts that may not be obvious.

• May include pattern matching algorithms

• May involve anomaly detection algorithms

• Used for business modelling

• Used to plan for future eventualities.

AO2:

• Can look for how people use the website e.g. visiting times, what they click on, how long they spend on certain features, what they do first, which elements are used leat.

• Give recommendations for future changes to the game e.g. features to add or remove.

AO3:

• Can use to introduce new features.

• Increase use form users

• Increase revenue by selling features used more often

• Make the game more appealing.

  • Remove features don't use, etc.

Discuss the benefits of Anna using an IDE to write and test her program rather than using a text editor.[9]

IDE is software that includes an editor, compiler, run-time environment

Creating:

• Autocorrect

• Autocomplete

• Pretty printing

  Testing

• Breakpoints

• Stepping

• Variable watch window

AO2:

• Tell you when you make a syntax error

• Allows you to write and run the code in one piece of software

• Suggests code so you don’t have to remember code, or autocorrect spelling mistakes

• Helps you trace the program so you can see what happens when values change without having to manually insert print statements etc.

• Autogenerate boilerplate code.

AO3:

• Reduce errors through autocorrect and suggestions

• Reduce time to write the program because features help you spot errors before running the code, some errors will be corrected so you don’t have to

• Write and test in one environment so you don’t have to close and run elsewhere, then re-open etc.

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.[9]

AO1:

Local variables:

• Scope within the module defined within

• Cannot access externally unless passed as parameter, or returned from function

• When module is exited, memory of variable is freed.

Global variables:

• Scope within the entire program

• Can access from anywhere

• Retained in memory permanently

ByRef Points to location of variable

ByVal Sends the value

AO2

• If global the arrays can be accessed from all modules by direct reference.

• If local to the main, the arrays will need to be passed as parameters by reference.

• Can send ByVal- but nit always possible with arrays in some languages.

• Modules are self contained an then can be reused in other programs he wants to create without the need to take the global variables with them.

AO3:

• +ve Local = memory efficient

• +ve Global = easier programming, simpler to follow, easier to debug

• -ve Global = memory inefficient, not good programming technique

• -ve Local = more difficult to trace/debug/follow where the values are passed

• Relatively small program – don’t know about overall plan for it, it might not be memory intensive, unlikely anyone else is going to access/amend e.g. use as a library – therefore global would not waste significant resources

Discuss the use of an IDE in the developemnt of this program (text editor) [9]

Tools to aid writing:

• Coloured font

• Predictive text

• Auto-correct

Tools to aid de-bugging

• stepping

• breakpoints

• variable watch window

AO2:

• Can write subroutines for the program and it will tell you what parameters are needed.

• Allow you to run the program without exiting the software / having to load a separate compiler.

• Integrates other tools such as version control.

• Can reduce spelling errors

• Can use to fix errors that might occur / debug

AO3:

• User friendly for novices.

• Increase speed of writing

• Fewer mistakes

• Increase speed of testing / finding errors

• Collaborative team working facilitated

Evaluate the use of data mining to help Benedict enhance and improve this social networking website.[9]

• Extracting data from databases

• Using large data sets

• Looking for patterns/specific occurrences of data

• Gathering data that can be analysed and used to inform decisions

AO2:

• Use to find out what his users do

• Find features that are used most often

• Find features that are not used

• Find out what people in his target age group do on other sites

• Find out characteristics of people who use the site

A03:

• Can identify areas to focus attention

• Save time and money by identifying areas that are not popular/used

• New features targeted at specific groups could bring in new business e.g. advertising

• But care would need to be applied to privacy issues / GDPR and potential impact on the users

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

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

A01:

Caching:

• Data that has been used is stored in cache/RAM in case it is needed again

• Allows faster access for future use

Reusable components:

• One piece of code can be used in multiple places / called many times.

• Use of subroutines / procedures / functions.

• Use of classes.

• Use of external libraries

A02:

• Store items in cache.

• Store requirements in cache

• Store garden layout in cache

• Reuse shapes / designs

• The use of a class allows replication.

A03:

• Faster development

• Faster/easier future adaptation

• Better performance of program

• Takes more time to plan/design to make use of both

Barney would like his linked list to be a part of a base program that is saved in a library. This means that it can be reused and changed by other programs.

Discuss the benefits of using different object-orientated techniques that Barney that could use to achieve this.[9]

A01:

• Classes, this a template. It will define what attributes and methods an object should have.

• Objects, when you create an instance of a class. Each object that is instantiated from the same class will share the same attributes and methods.

• Inheritance, when a sub class takes on the attributes and methods from a superclass/parent class. It can also have its own extra attributes/methods.

• Overriding, when a method name is the same in a parent and sub class, then the method in the parent/super class will be overridden

• Encapsulation, this protects attributes of an object by making them private so that they can’t be accessed or altered accidentally by other objects.

A02:

• A class can be used to declare the attributes and methods for the linked list. These will initialise the nodes and join them.

• Objects can then be used be used to instantiate the class each time a new linked list is needed. Each can be given a different identifier by the other programs.

• Further subclasses may be used by other programs. These can therefore take on the attributes and methods from the base class. These can also be changed or overridden depending on the purpose of the other programs.

• Encapsulation can be used by using set and get methods to ensure that the nodes in the linked list are changed in a way that is intended.

A03:

• Use of OPP techniques will allow for code reusability. His linked list can be saved as library and then reused many times leading to less code.

• OOP also allows programs to be easier to modify and maintain.

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

AO1:

• O(1)

  • Constant space, does not change.

• O(n)

  • Linear

  • Same as number of elements

  • As number of elements increases so does the time/space.

• O(n2)

  • polynominal

  • As number of elements increases, time/space increases by *n

• O(n log(n))

  • Linearithmic

AO2:

• Space: Merge sort will require more memory usage as the number of elements increases. Insertion will not require any more space than original. Quick will increase but not as much as merge.

• Best time: Insertion increases at the same rate as the number of elements. Quick and merge increase at greater rate

• Worst time: insertion and quick increase significantly by n for each additional item. Merge sort increases less per element.

• Log more appropriate for large number of elements

AO3:

• Small array – space is not important. Few number of elements. Look for consistency

• Large array therefore memory important – could remove merge as inappropriate. Logarithmic more efficient.

Discuss the need for concurrent processing in OCR-”Ticket’s system and the benefits and drawbacks of using this.[9]

AO1:

• Processes are happening at the same time/at overlapping times

• One process may need to start before a second has finished

• Individual processes are threads, each thread has a life line

• One request will be sent to the server, this will have a thread

AO2:

• Multiple requests to the server can be made at the same time

• Programming on server will need to allow multiple threads to manipulate a list of requests

• Programming will need to restrict access to the database of seats/sales etc.

• Will allow those reading and writing to manipulate at the same time

• Record locking will need implementing – more complex programming

• May be selling alongside other systems, therefore needs to communicate with external systems that will also use record locking to avoid two different external companies accessing and selling the same tickets.

Ao3:

• Will allow for multiple access to the website at the same time by different customers – as it would happen in real life.

• Will allow for multiple ticket sales for the same event without selling the same seat twice