questions on paper 2 Flashcards

Question

What makes a problem computable

Answer 1

If it can be solved by an algorithm - impractical when resources or time needed is too much

Answer 2

An abstract data type that can be used to represent complex non linear relationships between objects

Answer 3

Both consist of node Connected by edges Non linear Dynamic data structures

Answer 4

Tree = 1d, graph = 2d Tree has root node, graph has no clear root Trees are not weighted whereas graphs can be Graphs can have cycles whereas trees cannot

Answer 5

A path that starts and ends on the same node

Answer 6

When there is no direction associated with an edge

Answer 7

Start node for the traverse

Answer 8

Graphs can be used to represent connections between real life objects e.g. towns and roads

Answer 9

Breaking down large, complex problems into smaller subproblems

Answer 10

Makes it easier to manage Can be divided between a team

Answer 11

Each task is given a slice of processor time to make it appear as if tasks are being completed simultaneously One processes does not have to finish before the other starts

Answer 12

number of tasks completed in a given time increases + less time wasted waiting for user input/ interaction as other tasks can use processor while waiting

Answer 13

Can take tasks longer to complete when large numbers of users or tasks are involved Overhead in coordinating and switching between processes reduces program throughput Not all tasks are suited to being broken up

Answer 14

Different tasks developed in parallel, faster project delivery Commonly used in risc processor (fde simultaneously) Output of one process is the input of another

Answer 15

Checks every item one at a time O(n)

Answer 16

Divide and conquer O(logn) 0nly works in sorted lists Find middle element Compare If smaller use left sub list If bigger use right sub list Repeat until item is found or the are no more elements to check

Answer 17

Shortest path between 2 nodes Implemented using priority queue

Answer 18

Improvement of Dijkstra's Two cost functions – actual cost and heuristic (approximate cost) Heuristic added to actual cost to determine which node is visited Efficiency of algorithm depends on accuracy of heuristics

Answer 19

When a program calls itself during its execution, continuing until a stopping condition is met

Answer 20

+ can be represented in fewer lines of code + easier to express some functions recursively e.g. factorials Risk of stack overflow if memory runs out Difficult to trace

Answer 21

address of parameter is given to subroutine, value updated at given address

Answer 22

copy of value is passed to subroutine and discarded at end, value outside of subroutine remains unchanged

Answer 23

Divide and conquer Splits list in half until all sub lists have length 1 Merge puts them back together so they are in order O(nlogn)

Answer 24

Select an element (often middle) called pivot Divides input around pivot Smaller than pivot = added to left list Bigger than pivot = added to right list Repeated recursively until all elements in input are old pivots or list length = 1 O(n^2)

Answer 25

Compare item to later ones in list an insert it in correct place In the nth iteration, the first n numbers are sorted (this doesn’t mean they are the smallest numbers) Must go through whole list O(n^2)

Answer 26

Constant - same time regardless of data set Logarithmic - halves data set in each pass – good with large sets Linear - performance proportional to data Polynomial - performance proportional to square of size of data set Exponential - time doubles with each addition to the data set

Answer 27

= Big O The time is takes for the algorithm to solve the problem – worst case scenario To reduce, reduce the number of embedded for loops

Answer 28

= amount of storage the algorithm uses to run – stores extra data whenever it makes a copy of data To reduce, perform all changes on the original data

Answer 29

Evaluates pairs of items O(n^2) Comparisons and swaps between pairs To improve efficiency, a flag recording whether a swap has occurred can stop it having to loop through all the data items

Answer 30

OOP – problem divided into smaller parts called objects - systems are built around objects - objects don’t share data Procedural – problem divided into smaller parts called procedures Systems are built by combining procedures Procedures share data between them through global variables

Answer 31

A program which provides a set of tools to make it easier for programmers to write, develop and debug code Stepping Variable watch Debugging tools Break points

Answer 32

Limit the length of a function to less than 1 page to aid readability and reduce complexity Variable identifiers must conform to standard convention – helps other understand the code, reduces the likelihood of duplication, makes maintenance easier Each function must have a single entry point to reduce complexity and makes the search for bugs more straightforward Variables must not be set up outside the scope of a function, sets a limit where to look for bugs and reduces likelihood of problems spreading across many modules

Answer 33

The ability of a method to exhibit different behaviors depending on the object on which the method is involved e.g. how the plus sign changes from meaning concatenation when working with strings and mathematical addition when working with integers

Answer 34

Maks it possible to create a new child class that take on (inherits) the attributes and methos of the original (parent) class. Means that attributes and methods don’t need to be redefined + reduces repeated code +if implementation details need to change, it only needs to happen in one place May have unintended consequences (someone may extend the base class or make the bass class inherit from another class) meaning acquiring attributes and methods you’re not aware of

Answer 35

An instance of a particular class Collaborate with each other by sending and receiving messages All of the data and procedures and functions belong to one or more objects

Answer 36

# define every operation that is allowed to be carried out on an attribute Getters (accessors) – returns the value of an attribute Setters (mutators)– let you change the value of an attribute If no setters are provided there is no way that a value can be changed Public methods are used to access or modify attributes

Answer 37

data stored inside the class regarding the state or quality of the class or instance Should be private so hidden withinga class

Answer 38

data stored within a class regarding the state or quality of the class or object Should be private so hidden withing a class

Answer 39

Specify which properties can be accessed from outside the class Private - wont allow you to assign a value Public Protected

Answer 40

A blueprint that defines the properties of all objects of the same type

Answer 41

Happens automatically when you call a method from an object that shares the same name as a method further up the class tree. The overriding method takes precedence and replaces the method from the superclass

Answer 42

The inner workings ad details of the class don’t need to be understood by anyone other than the class designer. Classes often provided as part of software libraries.

Answer 43

Making an object from the class definition

Answer 44

Binds together the attributes and the methods that manipulate the data Form of data hiding Doesn’t allow unintended alterations by other objects

Answer 45

Filo structure Single pointer “top” points to element at top, initialised at –1 Size(), isempty(), peek(), push(element), pop()

Answer 46

Fifo 2 pointers, front = first element, back = next available space Size(), isempty(), peek(), enqueue(elements), dequeue()

Answer 47

An approach to systems development that focuses on objects and the way that they interact

Answer 48

Easier for us to think in terms of objects rather than procedurally Prewritten classes support code reuse Classes can easily be extended by creating a child Highly modular so can be split between teams Encapsulation provides protection

Answer 49

Result in larger, more complex systems Relies on high volume of message passing so can be detrimental to performance Objects can take up a large amount of memory

Answer 50

executing code a single line at a time | - allows you to monitor the effect of each line

Answer 51

observe how the contents of a variable change in real time through the execution of a program

Answer 52

set a point where the program will stop | - helps pinpoint errors

questions on paper 2 Flashcards

(76 cards)