cs paper 2 Flashcards
(133 cards)
1
Q
What is Dijkstras algorithm?
A
a shortest path algorithm used to find the shortest distance between 2 nodes in a network
2
Q
How is Dijkstras algorithm implemented?
A
use a priority queue which has the shortest lengths at the front of the queue
3
Q
What is the A* algorithm?
A
a general path-finding algorithm which has 2 cost functions: 1. actual cost 2. approximate cost
4
Q
How does the A* algorithm differ from Dijkstras algorithm? ( 2 things)
A
A* algorithm has 2 cost functions: 1. actual cost 2. approximate cost
5
Q
Why are heuristics used in the A* algorithm? (2 things)
A
- to calculate an approximate cost from node x to the final node 2. this aims to make the shortest path finding process more efficient
6
Q
What data structure can be used to implement Dijkstras algorithm?
A
priority queue
7
Q
What is an advantage of using the A* algorithm?
A
the speed of the algorithm is constrained by the accuracy of the heuristic
8
Q
What searching algorithm reuqires data to be sorted before starting?
A
binary search
9
Q
A
C
10
Q
Perform a linear search for 9 on the values: 1, 3, 6, 7, 9, 12, 15
A
11
Q
What is the time complexity of binary search?
A
O(log n)
12
Q
A
B
13
Q
Perform a binary search for 6 on the values: 1, 3, 6, 7, 9, 12, 15
A
14
Q
What searching algorithm has a time complexity of O(n)?
A
linear search
15
Q
What sorting algorithm makes comparisons and swaps between pairs of elements?
A
bubble sort
16
Q
A
B
17
Q
A
C
18
Q
A
19
Q
Perform the first pass of bubble sort on the values: 4, 2, 3, 5, 1
A
20
Q
What sorting algorithm can be improved by adding a flag record to record whether or not a swap has occured?
A
bubble sort
21
Q
A
22
Q
What are the 2 functions in merge sort?
A
MergeSort() Merge()
23
Q
In what sorting algorithm is the largest element in place after the first pass?
A
bubble sort
24
Q
What sorting algorithm uses pivots?
A
quick sort
25
What is the most efficient sorting algorithm?
merge sort
26
Perform merge sort on the values: 4, 2, 3, 5
27
Are stacks FIFO or LIFO?
LIFO
28
What 2 pieces of informations allow you to analyse an algorithm?
1. time complexity 2. space complexity
29
What is meant by the time complexity of an algorithm?
the amount of time required to solve a particular problem
30
What is the notation for time complexity?
big-O-notation
31
What does big-O notation show?
the effectiveness of an algorithm
32
What is big-O notation good for?
predicting the amount of time taken to solve an algorithm given the number of items input
33
What does a linear time complexity mean?
the amount of time taken to complete an algorithm algorithm is directly proportional to the number of items input
34
What does a constant time complexity mean?
the amount of time taken to complete an algorithm is independent of the number of items input
35
What does a polynomial time complexity mean?
the amount of time taken to complete an algorithm is proportional to the number of items input, to the power of n
36
What does an exponential time complexity mean?
the amount of time taken to complete an algorithm is proportional to 2 to the power of the number of items input
37
What does a logarithmic time complexity mean?
the amount of time taken to complete an algorithm will increase at a smaller rate as the number of items input increases
38
What is a logarithm?
how many times a certain number (base) is multiplied by itself to reach another number
39
What is space complexity?
the amount of storage an algorithm takes up
40
What is an algorithm?
a series of steps that complete a task
41
How do you reduce the space complexity?
complete all operations on a single data set
42
How do you reduce the time complexity of an algorithm? (2 steps)
1. reduce the amount for loops 2. reduce the amount of items, operations are completed on
43
What is the big-O notation of a linear search algorithm?
O(n)
44
What is the big-O notation of binary search algorithm?
O(log(n))
45
What is the big-O notation of a bubble sort algorithm?
O(n2)
46
What function adds an item to a stack?
push
47
What function removes an element from a stack?
pop
48
What does the back pointer do, in the array representation of a queue?
holds the location of the next available space in the queue
49
What function returns the item at the front of a queue without removing it?
peek
50
What does the front pointer in the array representation of a queue do?
holds the location of the first item in a queue
51
What value is the top pointer initialised to, in the array representing a stack?
-1
52
What is the pseudocode for the function which adds new elements to stacks?
53
What is the pseudocode for the function which adds new elements to queues?
54
What function returns the item at the top of the stack without removing it?
peek
55
What is representational abstraction?
where excessive details are removed to arrive at a representation of a problem consisting of only key features
56
What is abstraction by generalisation?
where similarities within a probelm are grouped together, to identify what kind of problem it is
57
What is meant by data abstraction?
where details about how data is being stored is hidden
58
What kind of problems make use of multiple levels of abstraction?
large, complex problems
59
How does abstraction allow non experts to make use of a system?
it hides complex and irrelevant information in abstract models
60
What are 3 advantages of using abstraction in software development?
1. easier for programmers to focus on important elements 2. reduces time spent on a project 3. prevents a program from becoming unnecessarily large
61
What are 2 applications of layers in abstraction?
1. networking (TCP/IP layer) 2. programming languages
62
What are 2 advantages of using abstraction in programming languages?
1. easier to remember syntax in high level languages as it is closer to natural language 2. coding becomes accessible to beginners
63
How does object-orientated programming use abstraction with objects?
objects are an abstraction for real world entities
64
How do object-orientated programming use abstraction with attributes?
attributes are an abstraction for object characteristics
65
How does object-orientated programming use abstraction with methods?
methods are an abstraction for actions a real-world object can perform
66
What is the difference between abstraction and reality?
abstraction is a simplified representation of reality
67
What is the first stage of thinking procedurally?
breaking a problem defined by a user, into its constiuent parts
68
What is the purpose of decomposition?
to make more complex problems more manageable and easier to solve by dividing tasks between a group of people based on individual skill sets
69
What is the other name given to a top-down design?
stepwise refinement
70
What are 2 benefits of using a top-down design?
1. problems can be solved by different people 2. tasks can be tested separately as modules are self contained
71
What type of problems are top-down design suited to?
large, complex problems
72
What is the second stage of thinking procedurally in software development?
identifying components of a solution
73
What can the lowest level subproblems in top-down design be made as in code?
a self contained module of subroutine
74
What 2 things does a software developers need to consider when recombining components of a solution?
1. the order in which the subroutines are executed 2. how they interact with each other
75
What must a software developer do before designing a subroutine to solve a particular problem?
identify if an existing subroutine or module can be used
76
What is a decision?
a result reached after consideration
77
What is the shape given to a decision icon in a flow chart?
a diamond
78
In a flowchart, how many options stem from a decision?
2 - yes or no / true or false
79
What is concurrent thinking?
completing more than one task at any given time
80
Is concurrent processing and concurrent thinking the same thing?
no
81
What is parallel processing?
where multiple tasks are completed simultaneously at any given time, utilising multiple cores
82
What is concurrent processing?
the process of giving a slice of processor time to tasks to give the illusion of parallel processing
83
What are 2 benefits of concurrent processing?
1. more tasks can be completed in a given time 2. other tasks can be completed whilst waiting for an input or user interaction
84
What is a negative of concurrent processing?
if many users are requesting for tasks to be completed, it takes longer for everyone to complete their task
85
What is the purpose of thinking ahead?
to make programs easy and intuitive for users to use
86
What is the definition of an input?
data that is required to solve a problem, usually entered into the system by the user
87
What is the definition of an output
results passed back when inputs have been processed and the problem is solved
88
What 3 considerations do programmers need to make about inputs and outputs when thinking ahead?
1. data structures used 2. data types used 3. method of input/output (device)
89
What are preconditions?
requirements which must be met before a program can be executed
90
What 2 places can preconditions be defined?
within the code or documentation
91
What are 2 examples of where preconditions are required?
1. stack functions 2. factorial function
92
What 2 ways does a stack function make use of preconditions?
1. checks that a stack is not empty when popping an element from a stack 2. checks that a stack is not full when pushing an element onto a stack
93
How does a factorial function make use of preconditions?
checks the number passed into the function is not negative
94
What are 3 conditions of including preconditions within the documentation accompanying a subroutine?
1. reduces complexity of the program 2. reduces time needed to debug and maintain a large program 3. makes the subroutine more reusable
95
What is the definition of caching?
the process of storing instructions or values in cache memory after they have been used, as they may be used again
96
How is caching used in storing web pages?
web pages that a user frequently accesses are cached, so next time they are accessed, content can be loaded without delay
97
What are 3 advantages of caching web pages?
1. content can be loaded without delay 2. images and text do not have to be downloaded multiple times 3. bandwidth is freed for other tasks on a network
98
What is prefetching?
where algorithms are used to predict what instructions are likely to be be used soon
99
What are 2 limitations of caching?
1. size of the cache 2. effectiveness of algorithms managing the cache
100
What are 2 advantages of using reusable program components?
1. more reliable than new components as they have already been tested 2. time, money and resources are saved as developing from scratch is not required
101
What are 3 examples of useable program components?
1. abstract data structures eg queues and stacks 2. classes 3. subroutines
102
What is meant by a computable problem?
a problem that can be solved using an algorithm
103
What are 3 limiting factors to computable problems?
- time - computer memory - processing power
104
What are 2 factors which may be considered during the problem definition phase?
1. strengths and weaknesses to the current solution 2. types of inputs/outputs and stored data
105
What is the name given to the process where problems are continually broken down until each subproblem can be represented as a subroutine?
problem decomposition
106
What are 3 purposes of problem decomposition?
1. sections can be developed in parallel 2. to identify sections which can make use of pre-coded modules or libraries 3. to simplify testing and maintenance
107
How does divide and conquer technique work? (3 steps)
1. the problem size is halved with every iteration 2. each individual subproblem is then solved recursively 3. the solutions to the subproblem are then recombined to form the final solution to the problem
108
What are 3 applications of divide and conquer?
- merge sort - quick sort - binary search
109
What type of programming construct do many problems using divide and conquer use?
recursion
110
What type of abstraction is used to group together sections of problems based on their functionality?
abstraction by generalisation
111
What are 3 problem solving techniques?
- pipelining - abstraction - divide and conquer
112
How does the backtracking algorithm work? (2 steps)
- by methodically visiting each path and building a solution based on the paths to be correct - if a path is found to be invalid at any point, it backtracks to the previous stage and visits an alternate path
113
When might heuristics be used in problem solving?
when the standard way to solve the problem is unreasonably time-consuming or resource-intensive
114
What are 3 advantages of using performance modelling?
- safe - relatively inexpensive - less time-consuming
115
What is pipelining? (2 things)
- a process where tasks are developed in parallel, - in pipelining, the output of one process becomes the input of another, resembling a production line
116
What are the 3 programming constructs?
sequence selection iteration
117
What are the 2 catagroies of loop iteration is split up into?
- count controlled - condition controlled
118
How does the selection programming construct work?
a certain block of code is run if a specific condition is met, using IF statements
119
What is recursion?
a programming construct where a subroutine calls itself during its execution until the base case is met
120
What is the base case in recursion?
a condition that must be met in order for the recursion to end
121
What are 2 advantages of recursion?
1. can be represented in fewer lines of code 2. easier to express some function recursively than iteratively
122
What are 3 disadvantages of using recursion?
- inefficient use of memory - danger of stack overfow - difficult to trace
123
What are 3 peices of information that are stored on the call stack?
- parameters - return adresses - local variables
124
What is the defenition of scope?
the section of the program where a variable can be accessed
125
What are 3 advantages of using local variables over global variables?
- less memory is used - self contained, so unaffected by code outside of the subroutine - takes precedence over global variables with the same name
126
What is a top-down design? (2 things)
- a technique used to modularise programs where the problem is continually broken down into sub-problems, - until each can be represented as an individual, self contained module that performs a certain task
127
What are 3 advantages of a modular design?
1. greater reusability 2. makes a problem easier to understand and approach 3. testing and maintenance simplified as modules are self-contained
128
What is the difference between procedures and functions?
functions must always return a value whilst a procedure does not
129
What does it mean to pass a parameter to a subroutine by reference?
the memory address of the parameter is passed to the subroutine, so its value outside of the subroutine will be updated
130
What are 3 features of IDE's?
- debugging tools - source code editor - variables watch
131
What does IDE stand for?
integrated development environment
132
What is encapsulation in object-orientated programming?
where attributes are declared as private so can only be accessed and edited by public methods
133
What is the purpose of encapsulation in object-orientated programming?
to reduce program complexity by protecting data from being accidentally edited by other parts of the program
