Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Computer Science > Paper 2 > Flashcards

Paper 2 Flashcards

1
Q

variable

A

named locations that store data in which the contents can be changed during program execution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

local variable

A

declared inside a function. They can only be accessed and used in that function.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

global variable

A

declared outside of all the functions, they can be used throughout the whole program including inside functions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

advantages of functions

A

easier to create and test

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

subprogram

A

self-contained units of code that perform some well-defined purpose.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

function

A

a subprogram that ALWAYS returns a single value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

procedure

A

a subprogram that returns one or many values.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

parameter

A

the data that is supplied to a subprogram so that they can be reused

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

passing by reference

A

the address of the variable is passed to the subprogram.

if the variable is changed it stays changed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

passing by value

A

a copy of the variable is passed to the subprogram. The original variable is unchanged no matter what the subprogram does.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

binary search precondition

A

the list needs to be sorted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Insertion sort

A

works by dividing a list into two groups: sorted and unsorted. Elements are inserted one by one into their correct position in the sorted section.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

thinking abstactly

A

represents reality by recognising what is important and blocking out other details

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

thinking ahead

A

planning input and outputs e.g. caching

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

caching

A

a temporary store where data and instructions or data that are likely to be needed are stored.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Thinking procedurally

A

writing in modules to split a problem up into manageable tasks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Thinking Logically

A

inferring things from what you already know and understanding where decisions need to be made and their consequences

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Thinking concurrently

A

thinking about how a job might be done better if some parts were performed at the same time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

features of an IDE

A
  1. Auto-complete
  2. colour coding/ syntax highlighting
  3. stepping
  4. breakpoints
  5. watch window
  6. error diagnostics
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

features of an IDE: Auto-complete

A

recognises identifiers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

features of an IDE: colouring syntax

A

identifies different features making the code easier and quicker to check

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

features of an IDE: stepping

A

runs one line at a time to check the result, good for error checking

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

features of an IDE: breakpoints

A

stops the code at set points to check the value of variables, good for error checking

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

features of an IDE: watch window

A

tracks how variables change during the execution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

features of an IDE: error diagnostics

A

locates and reports errors

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

IDE

A

Integrated Development Environment

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is an IDE

A

contains all the tools needed to write, develop and debug and program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

IDE three main tools

A
  1. editor
  2. build facility (automates the process of constructing a program from its component parts)
  3. a debugger
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Three programming constructs

A

sequence
selection
iteration

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

sequence

A

a series of statements that are executed one after the other

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

selection

A

a decision is made based on the state of a boolean expression

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

Iteration

A

where a section of code is repeated

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Selection cause

A

IF statement/ CASE statement

branch in assembly

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Iteration cuase

A

FOR loop / WHILE loop / REPEAT UNTIL loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

repeat until loop

A

Condition tested at the end of the loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

While loop

A

condition tested at the start of the loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

for loop

A

countrolled - repeats a set number of times

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Recursion

A

A procedure calls itself.
alternative way of producing iteration.
causes stack overflow is no terminating condition is built in.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Source code

A

The code written by the user

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

Compiler

A

translates high level language.

produces an object-code file. This can be run directly from the operating system,

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

Interpreter

A

Translates high level language.

translates and executes the program line by line.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

Modularity

A

separates the programs functionality into independent, interchangeable modules.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

constant

A

named locations that store data in which the contents stay the same during program execution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

object orientated programming

A

allows a program to solve problems by programming objects which interact with each other.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

class

A

a template used to define an object. It specifies the methods and attributes an object should have.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

object

A

an instance of a class

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

method

A

a subroutine associated with an object

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

new

A

a specific method called a constructor

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

constructor

A

a method that defines how an object is created

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

attribute

A

variables contained within and associated to an object

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

Encapsulation

A

ensuring private attributes can only be amended through public methods. Stops attributes being manipulated in unintended ways.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

inheritance

A

the ability for a class to inherit the methods and attributes of a parent class. The child class can have its own methods and attributes and override the inherited methods and attributes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

polymorphism

A

the ability for objects of different classes to be treated in the same way.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

polymorphism example

A

the same method may be applied to objects of different classes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

overriding

A

The method in the child class can be different to the method in its parent class whilst still having the same name and parameters etc

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

examples of abstraction

A
  • variables
  • objects
  • layers
  • data structures
  • entity-relation diagrams
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
57
Q

well-defined problems

A

problems that are clear to understand and the solution has defined expectations.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
58
Q

ill-defined problems

A

messy problems which are not clear how to solve.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
59
Q

Stages of problem solving

A
  1. Understand the problem
  2. Devise a plan
  3. carry out the plan
  4. Review your work
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
60
Q

Why do algorithms help

A
  • helps understand the problem
  • executed more quickly
  • possible to resort to trial and error
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
61
Q

problem recognition

A

The ability to recognize and acknowledge that an issue exists or that a situation needs attention in an existing process or program. The ability to define a problem and know exactly what it is.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
62
Q

Computable

A

a problem is computable is we can come up with an algorithm that will solve every instance of the problem in a finite number of steps.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
63
Q

intractable problem

A

a problem which cannot be completely solved.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
64
Q

problem decomposition

A

the process of taking a big problem and breaking it down into smaller problems until you fully explored the problems. Each of these smaller problems translate into one task which is more easily programmable as an individual module, function or procedure.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
65
Q

Top-down Problem solving

A

an approach to solve a problem that involves breaking down the main problem into sub-problems.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
66
Q

divide and conquer

A

a technique based around reducing the size of a problem with successive iterations. You look at a problem, apply some rules and discard any data that does not match then repeat the process with any information which is left. E.g. binary search.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
67
Q

divide and conquer advantages

A
  • efficient

- short runtime

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
68
Q

linked list

A

ordered data structure that uses pointers to sort and order the data items

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
69
Q

linked list node two parts

A
  1. to store the actual data

2. to store the reference to the next node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
70
Q

benefits of linked lists

A

efficient at adding/removing data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
71
Q

drawbacks of linked lists

A

slow to search

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
72
Q

adding data to linked lists

A
  • input the data in the location indicated to by the free storage pointer
  • update the free storage pointer to next free location
  • update the pointer for the new node to point to the next free storage spot
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
73
Q

removing data from linked lists

A
  • find the data item you want to delete
  • update the previous pointer to point to the next data item
  • the node for the deleted item can be added to the free storage list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
74
Q

Trees

A

Hierarchical data structure with data related to the data above it in the tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
75
Q

Binary tree

A

tree structure where each node can only have 0,1 or 2 child nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
76
Q

What doe each node contain in a tree?

A
  • pointers to the next data items

- data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
77
Q

preorder

A
  • start at root node
  • traverse the left sub tree
  • traverse the right subtree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
78
Q

inorder

A
  • traverse the left sub-tree
  • visit the root
  • traverse the right sub tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
79
Q

postorder

A
  • traverse the left sub-tree
  • traverse the right sub-tree
  • return to the root node
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
80
Q

preorder dot

A

left

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
81
Q

postorder dot

A

right

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
82
Q

inorder dot

A

under

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
83
Q

what does preorder do

A

selects roots before leaves

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
84
Q

what does inorder do

A

sorts the nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
85
Q

what does postorder do

A

slects leaves before roots

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
86
Q

graph

A

a set of edges/arcs connecting vertices/nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
87
Q

digraph

A

has one or more edges that have an arrow indicating you can only go in one direction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
88
Q

thinking ahead example process

A
  • what answers do we need?

- What do we need to know to get what we need?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
89
Q

Thinking procedurally process

A
  • divide the problem into sub-problems
  • do solutions already exist for any of the sub-problems
  • how do the sub-problems interact with each other
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
90
Q

Backtracking

A

the process of incrementally building up towards a solution, abandoning a partial success when the solution can’t be completed and then going back to a previously successful match.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
91
Q

When does a backtracking algorithm end

A

when there are no more possible solutions to the first problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
92
Q

backtracking advanatges

A

more effective than brute force as a large number of solutions can be eliminated with a single test

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
93
Q

concurrent programming

A

where one computation advances without waiting for all the other computations to complete.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
94
Q

data mining

A

where vast amounts of unconnected data is searched through, patterns are found and correlations are calculated.
There may be no predetermined matching criteria and a brute force approach may be used (alot of processing power)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
95
Q

Uses of data mining

A
  • targeting ads/marketing campaigns
  • Anticipating resource demands
  • Detecting fraud and cybersecurity issues
  • Finding connection between seemingly unconnected events
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
96
Q

positives of data mining

A
  • improves marketing
  • improves the estimate of stock quantities
  • ensure demands are met
  • increase sales
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
97
Q

negatives of data mining

A
  • alot of processing power required
  • privacy concerns
  • misuse of information
  • inaccurate data can cause a negative effect
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
98
Q

Big data

A

very large amounts of data on a particular topic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
99
Q

Parallel Computing

A

algorithm tasks are executed concurrently on a cluster of machines or supercomputers, is fundamental to managing big data tasks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
100
Q

Heuristics

A

making use of experience to find an acceptable solution, for example, using ‘rules of thumb’, educated guesses, intuitive judgements or common sense.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
101
Q

how are heuristics derived

A

derived from previous experiences with similar problems.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
102
Q

Why are Heuristics used/ what is the solution like?

A

Heuristic methods are used to rapidly find a solution that is ‘good enough’, even though it might not be the optimal solution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
103
Q

Heuristic method example

A

when analysing data only analyse and gather the data which is most likely to help

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
104
Q

performance modelling

A

process of carrying out mathematical approximations of how well models perform

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
105
Q

What does performance depend upon

A

complexity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
106
Q

performance modelling example

A
  • how efficient a program is

- whether a computing can cope with the strain

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
107
Q

pipelining

A

the process of taking a task and splitting it into smaller tasks and then overlapping the processing of each sub task to speed up the overall process.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
108
Q

pipelining example

A

the fetch decode execute cycle: For example, when one instruction is being fetched, another instruction is being decoded and the last is being executed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
109
Q

Visualisation

A

The ability to picture a problem and its solution in a visual way. It is easier to understand structures in a visual way

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
110
Q

Visualiation example,

A

flow diagrams

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
111
Q

5 methods of problem solving

A
  1. enumeration
  2. simulation
  3. theoretical approach
  4. trial and error
  5. creative solution
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
112
Q

enumeration (method of problem solving)

A

Designing an algorithm that performs an exhaustive search

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
113
Q

enumeration example

A

find the solution to an anagram by testing every permutation of letters

114
Q

simulation (method of problem solving)

A

The process of designing a model of a real system in order to understand the behavior of the system, and to evaluate various strategies for its operation

115
Q

simulation examples

A
  • Financial risk analysis
  • Amusement park rides
  • Population predications
  • Managing inventory systems
  • Queueing problems
116
Q

Theoretical approach (method of problem solving)

A

the problem be broken down into pure theory and be represented by mathematics

117
Q

Trial and error (method of problem solving)

A

If you don’t know how to solve a problem using trial and error may help the process/ completely solve the problem depending on its complexity.

118
Q

creative solution (method of problem solving)

A

Finding a solution to a problem which doesn’t follow the expected algorithms and rules but still provides an alternative solution

119
Q

Stack

A

Last in First Out data structure

120
Q

Queue

A

First in First Out data structure

121
Q

How do stacks work

A
  • data is push to the top of the structure

- data is popped from the top of the structure

122
Q

stack pointers

A

a single pointer points to the top of the tack and increments/decrements as data is added/removed

123
Q

algorithm for PUSHING onto a stack

A 
IF stack pointer = max THEN 
    report stack full
ELSE  
    set stack pointer = stack pointer + 1
    set stack[stack pointer] = data
END IF
124
Q

algorithm for POPPING off a stack

A 
IF stack pointer  = min THEN
    report stack empty
ELSE 
    set data = stack[stack pointer]
    set stack[stack pointer] = null
    set stack pointer = stack pointer -1
END IF
125
Q

How do Queues work

A
  • data is pushed to the end of the structure

- data is popped from the start of the structure

126
Q

Queue pointers

A

two pointers one pointing to the start the other pointing to the end. both increment as data is added/removed.

127
Q

circular queues

A

the newest data to be added in stored in the location which is vacated by popped data at the start of the queue

128
Q

algorithm for PUSHING onto a queue

not circular

A 
IF start pointer =1 and end pointer = max THEN
    report queue full
ELSE
    set queue (end pointer + 1) = data
    set end pointer = end pointer + 1
END IF
129
Q

algorithm for PUSHING onto a queue

circular

A 
IF start pointer =1 and end pointer = max THEN
    report queue full
ELSE IF start pointer = end pointer +1 THEN
    report queue full
ELSE
    set queue (end pointer + 1) = data
    set end pointer = end pointer + 1
END IF
130
Q

algorithm for POPPING off a queue

A 
IF start pointer = 0 THEN
    report queue empty
ELSE 
    set data = queue [start pointer]
    set start pointer = start pointer - 1
131
Q

computational thinking

A

Thinking about how a problem can be solved through formulating the problem and constructing the algorithm to solve it.

132
Q

Abstraction within programming / why is it abstraction

A

programmers use high level language commands.

The complexity of the machine code behind it has been removed

133
Q

advantages of thinking ahead/ preconditions

A
  • the user knows what they have to do
  • makes clear documentation easier to maintain
  • user can be confident that necessary checks have been carried out
134
Q

benefits of caching

A

instructions and data can be fetched alot quicker

135
Q

drawbacks of caching

A
  • algorithms choosing which data to be cached my chose wrong data
  • if algorithms are inefficient it can make the performance worse
136
Q

advantages of thinking concurrently

A
  • increased program throughput

- time is never wasted on user input

137
Q

disadvantages of thinking concurrently

A
  • if too many programs are running it takes a long time to process
138
Q

Advantages of recursion

A
  • suited to some problems (some functions are naturally recursive)
  • reduces the size of the problem (divide and conquer)
139
Q

Disadvantages of recursion

A
  • can run out of stack space due to too many function calls which causes stack overflow
  • more difficult to trace
  • requires more memory than iteration
  • slower than iteration
140
Q

Breakpoints

A

a set point which stops the program at that line

141
Q

step through

A

executes each line of code when you click

142
Q

purpose of testing

A

uncovered undetected errors

143
Q

procedural programming examples

A

Python, Pascal, Basic

144
Q

Object orientated examples

A

Java, Delphi, C+

145
Q

Instantiation

A

The creation of a new object

146
Q

Complexity

A

how well the performance of an algorithm scales as the size of data sets increase.

147
Q

time complexity

A

the number of steps/line of code executed in an algorithm.

148
Q

space complexity

A

the memory requirement for an algorithm

149
Q

efficiency

A

time complexity and space complexity

150
Q

BigO

A

a complexity notation. remove all coefficiants and just write the value of n with the largest exponent e.g. O(n)

151
Q

O(1)

A

constant complexity

152
Q

constant complexity

A

An algorithm that always executes in the same time regardless of the size of the data set. Best Algorithms.

153
Q

O(log n)

A

Logarithmic Complexity

154
Q

Logarithmic Complexity

A

An algorithm that halves the data set in each pass. Efficient with large data sets. Good algorithms.

155
Q

O(n)

A

Linear Complexity

156
Q

Linear Complexity

A

An algorithm whose performance is proportional to the size of the data set and declines as the data set grows. Fair algorithms.

157
Q

O(n^a)

A

Polynomial complexity (quadratic, cubic etc)

158
Q

Polynomial complexity (quadratic, cubic etc)

A

An algorithm whose performance is proportional to the square of the size of the data set. Significantly reduces efficiency with increasingly large data sets. Poor algorithms.

159
Q

O(2^n)

A

Exponential Complexity

160
Q

Exponential Complexity

A

An algorithm that doubles with each addition to the data set in each pass. Inefficient. Extremely poor algorithms that should be avoided.

161
Q

O(n log N)

A

Algorithms that divide a data set but can be solved using concurrency on independent divided lists.

162
Q

complexity order

A

O(1) -> O(logn) -> O(n) -> O(nlogN) -> O(n^2) -> O(2^n)

163
Q

Linear search best

A

O(1)

164
Q

linear search average

A

O(n)

165
Q

linear search worst

A

O(n)

166
Q

binary search best

A

O(1)

167
Q

binary search average

A

O(logn)

168
Q

binary search worst

A

O(logn)

169
Q

Binary search tree best

A

O(1)

170
Q

Binary search tree average

A

O(logn)

171
Q

Binary search tree worst

A

O(n)

172
Q

Hashing best

A

O(1)

173
Q

Hashing average

A

O(1)

174
Q

Hashing worst

A

O(n)

175
Q

Breadth/Depth first best

A

O(1)

176
Q

Breadth/Depth first average

A

O(V+E)
V = no. vertices
E = no edges

177
Q

Breadth/Depth first worst

A

O(V^2)

178
Q

Bubble sort best

A

O(n)

179
Q

Bubble sort average

A

O(n^2)

180
Q

Bubble sort worst

A

O(n^2)

181
Q

Bubble sort space complexity

A

O(1)

182
Q

Insertion sort Best

A

O(n)

183
Q

Insertion sort Average

A

O(n^2)

184
Q

Insertion sort Worst

A

O(n^2)

185
Q

Insertion sort Space complexity

A

O(1)

186
Q

Merge sort best

A

O(nlogn)

187
Q

Merge sort average

A

O(nlogn)

188
Q

Merge sort worst

A

O(nlogn)

189
Q

Merge sort Space complexity

A

O(n)

190
Q

Quick Sort best

A

O(nlogn)

191
Q

Quick Sort average

A

O(nlogn)

192
Q

Quick Sort Worst

A

O(n^2)

193
Q

Quick sort space complexity

A

O(logn)

194
Q

how to get the bigO expression

A
  • remove all terms except the one with the largest exponent

- remove all constant factors

195
Q

linear search

A

starts at the beginning of a list and checks each item in turn until the desired item is found

196
Q

Binary search

A

divides a list in two each time until the item being searched for is found

197
Q

Four sorting algorithms

A

Bubble, Insertion, Quick, Merge

198
Q

Insertion sort words

A

Make the first item in the list the sorted list. The remaining items are the unsorted list.
While there are items in the unsorted list take the first item of the unsorted list.
While there is an item to the left of it which is smaller than itself swap with that item. End while.
The sorted list is now one item bigger.
End while

199
Q

Merge sort

A

splits a list of size n into n lists of size 1. Each pair of lists are merged together in order until there is only one list of size n.

200
Q

Why does merge split down into unit lists

A

because a list of length one is sorted

201
Q

Merge algorithm

A
  1. If the sub-list is 1 in length, then that sub-list has been fully sorted
  2. If the list is more than 1 in length, then divide the unsorted list into roughly two parts. (An odd numbered length list can’t be divided equally in two)
  3. Keep dividing the sub-lists until each one is only 1 item in length.
  4. Now merge the sub-lists back into a list twice their size, at the same time sorting each items into order
  5. Keep merging the sub-lists until the full list is complete once again.
202
Q

Quick Sort Algorithm

A
  1. If the list to be sorted is length 1, then finish - job complete
  2. Pick an item within the list to act as a ‘pivot’. The left-most item is a popular choice.
  3. Split the list into two parts - one list with items equal to or larger than the pivot item and the other list contains items smaller than the pivot
  4. Repeat this process on the two halves
203
Q

Quick sort

A

The basic idea is to keep splitting a list into two smaller lists, sort those lists using the same quick-sort rules, then split the sub-lists and sort again, until there are only lists of 1 item or less left.

204
Q

Where can the pivot be applied

A

The pivot can be applied to any item in the unsorted list.

205
Q

advantages bubble

A
  • simple
206
Q

disadvantages bubble

A
  • long time to run
207
Q

advantages insertion

A
  • Simple to code
  • Good performance with small lists
  • memory efficient
  • good with sequential data
208
Q

disadvantages insertion

A
  • poor performance with larger lists

- not as quick as merge/quick sort

209
Q

disadvantages quick

A
  • difficult to implement
  • if a bad pivot is picked the runtime is slow
  • worst case efficiency is bad
210
Q

advantages quick

A
  • very efficient

- no additional storage required/ less stack memory

211
Q

advantages merge

A
  • Good for sorting slow access data
  • Good for sorting sequential data
  • if there are two equal values then positions are conserved, which is quicker
212
Q

disadvantages merge

A
  • It needs twice then length of memory space than the list
  • If recursion is used, it used twice the stack memory as a quick-sort
  • quick sort is faster
213
Q

advantages Linear search

A
  • Good Performance
  • List does not need to be ordered
  • Not affected by insertions and deletions
214
Q

disadvantages linear search

A
  • May be too slow over large lists
215
Q

advantages binary search

A
  • Works well with larger lists

- Quicker

216
Q

disadvantages binary search

A
  • Small lists simpler to use linear search

- Cannot deal with unordered lists

217
Q

Depth first traversal

A
  • uses a stack to store the visited nodes
  • visits all the nodes attached to a node connected to a starting node before visiting a second node attached to a starting node
218
Q

Depth first Algorithm

A 
PUSH first node onto stack
mark as visited
Repeat 
     visit the next uninvited node adjacent to the node on top of the stack
     mark as visited
     PUSH this node onto the stack
     if no node to visit POP node off the stack
UNTIL stack is empty
219
Q

Breadth first Traversal

A
  • uses a queue to store the visited nodes

- visit all the nodes attached directly to a starting node first

220
Q

Breadth first algorithm

A 
PUSH first node into the queue
mark as visited
REPEAT 
     visit unvisited nodes connected to the first node 
     PUSH nodes into the queue
UNTIL all nodes visited
REPEAT 
     POP next node from queue
     REPEAT 
            visit unvisted nodes connected to current node
            PUSH nodes onto queue
      UNTIL all nodes visited
UNTIL all nodes visited
221
Q

Shortest path algorithms

A

Dijkstra’s and A*

222
Q

Dijkstras table columns

A

visited, vertex, shortest distance from start node, previous vertex

223
Q

What are all the shortest distances filled with at the beginning (Dijkstras)

A

infinity, except for the vertex your measuring from which is zero

224
Q

Dijkstras

A

Finds the shortest distance between one node and any other node in a network

225
Q

A*

A

A variation of Dijkstras that uses a heuristic to try and get the correct solution sooner

226
Q

A* table

A

visited, vertex, shortest distance from start node, heuristic distance, sum, previous vertex

227
Q

Advanatges of Dijkstras

A
  • doesn’t need to know the target node before

- good for multiple target nodes

228
Q

Disadvanatges of Dijkstras

A
  • doesn’t work for negative edge weights

- slower than A*

229
Q

Advantages of A*

A
  • faster
  • always find a solution if it exists
  • can be morphed into other path finding algorithms by changing the heuristic
230
Q

Disadvanatges of A*

A
  • no good if you have many target nodes

- not good if you have no prior knowledge of the network

231
Q

time complexity vs performance

A

even if the complexities are the same one algorithm may still perform better than another

232
Q

Why are linked lists good for ordering list?

A
  • dynamic data structure allows data to be added/removed

- data can be added/deleted from any point in the list

233
Q

advantages of subprocedures

A
  • can split between programmers (can specialize in their areas)
  • speeds up completion time (multiple procedures are worked on concurrently)
  • Easier to maintain/ test (can test each module invidiually)
  • reuse modules saving time
234
Q

What does depth first traversal use?

A

stack

235
Q

What does breadth first traversal use

A

queue

236
Q

Depth first traversal words

A

Depth-first goes to left child node when it can if there is no left child it goes to the right child when there are no child nodes the algorithm ‘visits’ it’ and backtracks to the parent node.

237
Q

Breadth first traversal words

A

first visits the root. Breadth-first visits all nodes connected directly to start node then visits all nodes directly connected to each of those nodes (and then all nodes directly connected to those nodes and so on…)

238
Q

how is backtracking used in depth first traversal

A

when there are no nodes to visit the algorithm goes back to the previous node to check for further nodes to visit

239
Q

process of decomposition

A

splitting a problem down into its component parts

240
Q

for loop pseudocode

A

for i=0 to 7
print(“Hello”)
next i

241
Q

while loop pesudocode

A

while answer!=”computer”
answer=input(“What is the password?”)
endwhile

242
Q

do until loop pseudocode

A

do
answer=input(“What is the password?”)
until answer==”computer”

243
Q

MOD

A

gives the remainder of a division

244
Q

DIV

A

integer division (rounds down)

245
Q

if/else Pseudocode

A 
if/else
if entry==”a” then
print(“You selected A”)
elseif entry==”b” then
print(“You selected B”)
else
print(“Unrecognised selection”)
endif
246
Q

switch/case pseudocode

A 
switch/case
switch entry:
case “A”:
print(“You selected A”)
case “B”:1
print(“You selected B”)
default:
print(“Unrecognised selection”)
endswitch
247
Q

get the substring

A

stringname.subString(startingPosition, numberOfCharacters)

248
Q

by default how are parameters passed?

A

by value

249
Q

reading from a file

A

myFile = openRead(“sample.txt”)
x = myFile.readLine()
myFile.close()

250
Q

writing to a file

A

myFile = openWrite(“sample.txt”)
myFile.writeLine(“Hello World”)
myFile.close()

251
Q

procedure OO pseudocode

A

public procedure setAttempts(number)
attempts=number
endprocedure

252
Q

Inheritance OO pseudocode

A

class Dog inherits Pet
attributes
methods
endclass

253
Q

create an instance of a class OO

A

objectName = new className(parameters)

254
Q

COmputable

A

if we can come up with an algorithm that will solve every instance of the problem in a finite number of steps it is computable.

255
Q

Intractable problem

A

A problem that cannot be completely solves

256
Q

Methods of problem solving:

A
  • Enumeration
  • Simulation
  • Theoretical approach
  • Trial and error
  • creative solution
257
Q

problem recognition

A

The ability to recognize and acknowledge that an issue exists or that a situation needs attention in an existing process or program. The ability to define a problem and know exactly what it is.

258
Q

Problem decomposition

A

the process of taking a big problem and breaking it down into smaller problems until you fully explored the problems. Each of these smaller problems translate into one task which is more easily codeable as an individual module, function or procedure.

259
Q

Thinking ahead

A

planning inputs and outputs which may be used in a computer program.

260
Q

Thinking procedurally

A

Dividing a problem into a series of sub problems are tackling each problem individually. Some will already have solution written which you can copy.

261
Q

Thinking logically

A

inferring things from what you already know. Understanding where a decision needs to be made and knowing its consequences.

262
Q

benefits of caching

A
  • speeds up access times and therefore improves performance
  • uses less physical resources
  • increases throughput
263
Q

drawbacks of caching

A
  • it may not store the correct data, the data may no longer be relevant
  • very complex trying to deal with data to be cached
  • the physical memory is expensive
264
Q

Why are reusable program components good?

A
  • saves time and memory

- saves memory space

265
Q

three types of error

A
  • logical error
  • systematic error
  • run time error
266
Q

logical error

A

An error that causes the program to perform something unintended

267
Q

systematic error

A

Statement that break the rules of the programming language

268
Q

run time error

A

Error that occurs due to an unexpected event/causes

the program to stop working (crashes)

269
Q

advantages of writing in modules

A
  • Work can divided between a team, saves time as work takes place in parallel
  • each team must only know what values to go into their subroutine and their expected functionality
  • breaks problem down, easier to understand/test/debug/read
  • Modules can be given to teams with specific expertise
  • each subroutine can be tested individually before its combined to the main program
  • code can be reused
270
Q

scope

A

The section of code where a variable can be accessed and used

271
Q

local variables with the same name as global variables…

A

overwrite/ take precedence of global variables

272
Q

modular design

A

program is split into self contained tasks which can be written and tested individually. Modules can be subdivided into smaller modules.

273
Q

concatination

A

joining two strings together

274
Q

Benefits of using recursion over iteration

A
  • more natural to read
  • Quicker to writes/ less lines of code
  • Some functions are naturally recursive
  • can reduce the size of the problem with each call
275
Q

Drawbacks of using recursion over iteration

A
  • can run out of stack space (due to too many function calls, causes it to crash)
  • more difficult to trace/follow as each frame on the stack has different variables
  • requires more memory
  • Usually slower than iterative methods due to stack maintenance
276
Q

Why are global variables sometimes used

A

When a variable needs to be accessed throughout the whole program and not just in one subroutine. e.g. a date variable

277
Q

Why is the use of global variables usually avoided

A
  • makes it difficult to integrate modules
  • increases the complexity of a program
  • easy to change the value by accident, leading to errors
278
Q

non user defined function examples

A

int, input, print

279
Q

function (inline)

A

a named section of code that performs a specific task and always returns a value.

280
Q

what is more common: functions or procedures

A

function

281
Q

Example rules for writing functions

A
  • only allow functions to be of a certain length
  • Suitably named variables
  • functions must have a single entrypoint
  • no/ few global varaiables

Computer Science (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions