Algorithms and Programming Flashcards
1
Q
Algorithms
A
unambiguous series of instructions needed to create a task that is language neutral and not in code
2
Q
Annotation
A
add comments to explain function of each section of the code
3
Q
Arbitrage Opportunity
A
converting between currencies to generate profit
4
Q
Arithmetic Efficiency
A
used to describe the efficiency of an algorithm based on standard mathematical functions, with O standing for Order
5
Q
Auto-Completion of Statements
A
gives suggestions in a drop-down menu when the user is typing, saving time and minimising bugs
6
Q
Auto-Completion of Statements
A
gives suggestions in a drop-down menu when the user is typing, saving time and minimising bugs
7
Q
Automatic Formatting
A
may also include automatically indenting code, saves time and reduces chance of bugs
8
Q
BNF
A
Backus-Naur Form
used by the developers of programming languages to specify the syntax rules of a language
9
Q
Base Condition
A
a requirement in recursive functions, without which the function will continue to execute in an infinite loop
10
Q
Basic Operation
A
the operation which contributes most to the total running time
11
Q
Big O Notation
A
tells you the number of operations an algorithm will make
12
Q
Constant Time
A
O(1)
this takes the same amount of time to complete regardless of the amount of input data
13
Q
Exponential Time
A
O(2^n)
where the time taken to complete will double with every extra data item, such as a recursive Fibonacci algorithm
14
Q
Factorial Time
A
O(n!)
where the time taken to complete will grow much faster than the exponential time, for example, in password cracking programs
15
Q
Linear Time
A
O(n)
where the time taken to complete the algorithm grows in direct proportion to the number of data items, for example, a linear search in an array
16
Q
O Growth Time
A
O(n log^2 n)
where the time complexity depends on n, such as in a recursive quicksort algorithm
17
Q
Polynomial Time
A
O(n^2)
where the time taken to complete the algorithm is directly proportionate to the square of the number of data items, for example, in an algorithm using two nested loops, such as a typical sort routine
18
Q
Block Code
A
putting code into blocks where each block deals with one task
19
Q
Blue Screen of Death
A
signifies a fatal error with the operating system
20
Q
Bracket Matching
A
automatically adds a bracket after an opening bracket has been added, saves time and reduces chance of bugs
21
Q
Branches
A
links nodes together in a tree structure
22
Q
Breakpoint
A
causes program to run up to a point and then pause, allowing for variable inspection
23
Q
Bubble Sort
A
involves iterating through the list, beginning by comparing the first and second items and swapping them if they are out of order and continuing to compare until the end of the list after which the process will be repeated until no more swaps are made
24
Q
Colour Coding Key Words
A
an automatic function in the IDE, helps with preventing bugs
25
Compression Algorithm
process that reduces a file’s size for efficient storage or transmission
26
Dictionary Compression
a lossless compression technique that relies on finding patterns in data and substituting them for a shorter code. Codes and their meanings are stored in a dictionary or code list
27
Dynamic Allocation
memory space is only allocated when required at runtime
28
Huffman Coding
a form of lossless compression which makes files smaller using the frequency with which characters appear in a message
29
Lossless Compression
a way of compressing data without removing parts, such as ZIP files
30
Lossy Compression
a way of compressing data by removing parts, permanently changing it, using this equation: compression ration = original file size / compressed file size
31
RLE Compression
Run-Length Encoding Compression
a form of lossless compression that looks at the data in a file for consecutive runs of the same data, storing data as one item of data, instead of many
32
Condition
a Boolean test which can either be true or false
33
Condition Controlled Loop
where code statements are repeated whilst a condition is met
34
Constant
hold a fixed value, stored in memory, have an identifier, data type and value and cannot change during execution of the program
35
Constant Declaration
involves specifying the identifier, data type and value
36
Constant Growth Rate
most iterative algorithms will have a constant growth rate of O(1), for example, in an iterative sorting algorithm
37
Context Sensitive Help
provides help based on a specific dialogue box or control in a program, enabling users to get specific information about the part of the program they are using at any given moment
38
Control Flow
the order in which statements, instructions or function calls of an imperative program are executed or evaluative
39
Control Operations
where instructions don’t have to be carried out in order
40
Conditional Operations
a control structure that checks if a condition is true or false then executes an instruction based on the answer
41
Iterative Operations
a control structure that repeats a set of instructions until a condition is met using loops
42
Count Controlled Loop
where code statements are repeated a specific amount of times
43
Current Pointer
position in the array of the current node
44
Data Type
indicates size of variable and enforces some rules about the nature of the variable
45
Debugging Tools
a software tool in the IDE that helps the user identify errors in the code
46
Breakpoint
causes program to run up to a point then pause, allowing for variable inspection
47
Step Thru'
steps through program one statement at a time, allowing faults in program logic to be identified
48
Variable Inspection
allows variables stored in a program to be watched as the program runs
49
Variable Watch
the act of observing a specific variable whilst the program runs, which the programmer can do whilst using variable inspection
50
Declarative Program
used in programs such as Chat GPT, involves telling the computer what needs to be done instead of how to do it
51
Defensive Programming
a form of defensive design intended to develop programs that are capable of detecting potential security abnormalities and make predetermined responses
52
Digit
a symbol that can be used with other digits to represent a number
53
Dijkstra's Algorithm
involves assigning every node a temporary value, setting it to zero for the initial node and to infinity for all other nodes, adding all nodes to a priority queue sorted by current distance and whilst the queue is not empty, removing the current node from the front of the queue; for each unvisited neighbour of the current node, add up the distances and find the shortest one
54
Emulator
simulates a physical device, such as a mobile phone or games console, to allow apps to be tested on the computer rather than that device
55
Error
problems in the program
56
Linking Error
an error that occurs when the program calls a library that has not been linked to the program
57
Logical Error
when the code runs, but does not do what you want it to do
58
Rounding Error
when a number is rounded when it shouldn’t be, for example 4.5 is rounded to 5, causing a rounding error of +0.5
59
Runtime/Execution Error
an error that occurs when a program requests more memory than is available
60
Semantic Error
error in the meaning of the code
61
Syntax Error
an error that occurs when a program does not follow the expected syntax of the code
62
Truncation Error
when a number is truncated when it shouldn’t be, for example, 3.7 is truncated to 3, creating a truncation error of 0.7
63
Error Trapping
refers to the prediction, finding and fixing of programming errors
64
Exception Handler
the process of responding to anomalous or exceptional conditions requiring special processing
65
Explorer's Problem
a problem in which the solution finds a route that traverses each road exactly once before returning to the starting point
66
Exponential Function
a function with the form f(x)=ax where a is a constant value. The result of the function becomes very big very quickly
67
Factorial Functions
an operation that describes taking any whole number and multiplying it by every lesser value until you get to one, denoted by an exclamation mark which grows very quickly
68
Complexity
how big an executable file is
69
Compression Ratio
how much space it saves
70
Latency
how long you have to wait until it starts streaming
71
Portability
whether files are readable by any standard compression utility
72
Space
how much RAM the algorithm needs to run
73
Speed
how fast it is
74
Flag
a specific symbol such as a dollar sign that designates RLE
75
Free Pointer
points to the next free space in the list
76
Function
self contained modules of code that accomplish a specific task, and can be recalled several times in the program
77
Graph
a non-linear data structure that comprises a set of connected nodes
78
Head Pointer
points to beginning of list
79
Heuristic
an approach that uses experience to make informed guesses that assist in finding a polynomial time solution to an intractable algorithmic problem; the solution may be non-optimal
80
Huffman Trees
a compression technique used to reduce the number of bits needed to send or store a message that is based on the frequency of occurrence of a data item. The principle is to use a lower number of bits to encode data that appears more frequently. Characters are arranged into a binary tree and each character is assigned a code by traversing the tree. More frequently used characters have shorter codes allowing for data compression
81
Hyperlocal Variable
a variable used in extreme isolation
82
Identifier
allows program to retrieve the value stored in the variable for memory
83
Illegal Operation
an operation that cannot be run by the system
84
IDE
Integrated Development Environment
an integrated set of tools used in software development
85
Imperative Program
involves giving the computer a clear set of instructions, which it then follows exactly
86
Indentation
shows the structure of the program
87
Instruction Set
the complete set of all the instructions in machine code that can be recognized and executed by a central processing unit, size of instruction set is dependent on the hardware design of the processor
88
Intractable Problem
a problem that cannot be solved because it takes up too much memory
89
ADD
add one number to another
90
AND
Boolean algebra function
91
DEC
decrement a number by 1
92
INC
increment a number by 1
93
JMP
jump to another section of code
94
JNZ
jump to another section of code if the number is not 0
95
JZ
jump to another section of code if the number is 0
96
MUL
multiply two numbers together
97
NOT
Boolean algebra function
98
OR
Boolean algebra function
99
SUB
subtract one number from another
100
XOR
Boolean algebra function
101
Iteration
where code statements are repeated
102
Leaf
a terminal node with no children
103
Left Pointer
position of the item to the left of the current node
104
Linear Function
a function that as the form f(x)=ax+c where a and c are constant variables. In this function, c becomes insignificant as x increases
105
Linear Growth Rate
the growth rate of a factorial recursive function
106
Linker
combines pre-compiled modules of code, such as standard libraries, into a single executable file
107
Logarithmic Function
a function that has the form f(x)=a logn x where a and n are constant values, the result of a function growing very slowly
108
Logarithmic Growth Rate
the growth rate of quicksort algorithm
109
Lossless Compression
used to compress files using run length encoding so does not involve removing data as it looks for repeating
110
Lossy Compression
used to store images (JPEG), sound (MP3) and videos (MP4) which involves removing part of the data
111
LZ Compression
a table-based compression model where table entries are substituted for repeated strings of data. This table is normally generated dynamically from earlier data in the input. The table itself is often Huffman encoded
112
Manual Techniques
tools to detect errors
113
Dry Running
where a programmer manually goes through the code line by line to find the error
114
Rubber Duck Debugging
where a programmer explains to a rubber duck what the code will do
115
Trace Table
used to track how variables change when a program is run
116
Tracing
where a programmer manually goes through the code line by line to find the error
117
Variable Dumping
write variable values to screen as the program runs
118
Memory Inspector
allows contents of computer memory to be examined
119
Memory Management
the process of controlling and coordinating a computer’s main memory
120
Memory Protection
a way to control memory access rights to a computer
121
Modularisation
use of functions and subroutines to break up programs into a series of subprograms
122
Negative Compression
where compression causes a file to grow in size
123
Nesting
where one statement is placed within another to build up the complexity of the code
124
Null Pointer
points to the end of the list
125
Number
represents an amount of stuff
126
Number System
the way in which numbers are represented by digits
127
Object-Oriented Program
programming based on the concept of objects, which can contain data and code
128
Paradigm
a distinct set of concepts or thought patterns
129
Parameter
treated as a local variable within a subroutine so the value can be changed but removes the need to rely on the global variables to pass values between routines, helping reduce the chance of bugs in your code
130
Parameters by Reference
where the address of the value is supplied to the sub-routine so if the subroutine changes the value of the parameter, the original value is updated
131
Parameters by Value
a copy of the data item is sent to the sub-routine so changes in the value of the parameter will not alter the original value
132
Parent
nodes in a tree can only have one of these
133
Partition
an unsorted section of the list, is repeatedly partitioned until every partition contains only one number and the list is sorted
134
Passing by Reference
allows a function to modify a variable without creating a copy
135
Passing by Value
a copy of the passed-in variable is copied into the argument of the method. Any changes to the argument do not affect the original one
136
Point of Invocation
the place where the function was called from
137
Polynomial Function
a function with the form f(x)=axn+bx+c where a, n, b and c are constant values, and in this function, x2 becomes the only significant function as x increases
138
Processing
all code other than input or output
139
Program
implementation of algorithm, a list of instructions that a computer has to work through in order to complete a specific task
140
Program Logic
the thinking, planning and implementing behind coding
141
Pseudorandom
randomness satisfying one or more statistical tests for randomness but produced by a definite mathematical procedure
142
Publisher
packages the programs and its sub-modules into a single easy to install package for program development
143
Quick Sort
a divide-and-conquer algorithm that recursively breaks the list up into multiple lists. An item is selected at random to be the pivot, creating two new lists. Items less than the pivot move to one list and itmes more than the pivot move to the other. This is repeated with each sub list until the lsits only have one item, after which they are merged back together
144
Recursion
a function that calls itself and stops calling itself when a base condition is met
145
Recursive Algorithm
these require space for each call of the function as all data items for each call are added to the stack as the memory growth or space complexity is dependent on the number of cells
146
Recursive Fibonacci Algorithm
the recursive equation for Fibonacci is T(n)=T(n-1)+T(n-2)+O(1). This means the time taken to calculate fib(n) is equal to the sum
147
Recursive Step
a step that will be followed until the base condition is met in recursion
148
Recursive Tree
where every tree has only one root and each node is the root of a sub-tree. Thus, a tree consists of a root and one or more sub-trees, each of which is a tree
149
Regular Expression
an approach that uses experience to make informed guesses that assist in finding a polynomial time solution to an intractable algorithmic problem; the solution may be non-optimal
150
Regular Language
any language that a finite state machine (FSM) will accept
151
Return Value
when exiting, functions always return a value to the point of invocation either by using the keyword Return or by setting the name of the function to a value
152
Reverse Polish Notation
the order in which computers execute operations, effectively computer BODMAS
153
Right Pointer
position of the item to the right of the current node
154
Root
the top node in a tree
155
Rooted Tree
a tree structure with a clear root node
156
Searching Algorithm
a computer uses searching algorithms to search for a value in a given list
157
Binary Search
a more efficient way of soring that only works on sorted lists which starts by finding the middle item and comparing it to the value it is searching for; if the middle value is smaller than the value it is searching for then the first half of the list is removed, including the middle value. If the new middle value is larger than the value it is searching for then the top half of the list is removed, including the middle value. This process is repeated until the value is found.
158
Insertion Search
when exiting, functions always return a value to the point of invocation either by using the keyword Return or by setting the name of the function to a value
159
Linear Search
goes through each item in an algorithm one by one until it finds the one it is looking for, then it stops the search after potentially going through every item in the list
160
Second Search
checks every second record, then goes back if it has gone past what it is searching for
161
Quick Search
uses a divide and conquer approach, begins by breaking the list into two sections based off of a pivot value, one of which will eventually contain all the numbers before the pivot value and one of which will eventually contain all the numbers after the pivot value
162
Rooted Tree
a tree structure with a clear root node
163
Selection
where code statements are carried out based on the results of a condition
164
Selection Sort
where the algorithm repeatedly selects the smallest element from the unsorted portion of the list and swaps it with the first element of the unsorted part. The process is repeated for the remaining unsorted portion until the entire list is sorted.
165
Sequence
a block of statements where every statement is carried out in written order, and each statement is carried out once
166
Sequence Block
a block of statements where every statement is carried out in written order, and each statement is carried out once
167
Sequential Operations
instructions that are executed in order
168
Space Complexity
describes growth of storage space required with data volumes and the growth rate of memory usage is the amount of additional memory required by each additional run through the program
169
Tree
dynamic data structure consists of nodes linked by branches and the top node is the root node. Nodes can have up to two child nodes and only one parent node. Trees can be implemented using a two-dimensional array to store the nodes. Each node stores a left pointer, a data item and a right pointer
170
Breadth-First Traversal Algorithm
consists of accessing each node, one level after the other. On each layer the nodes are accessed as they appear, from left to right
171
Depth-First Traversal Algorithm
traversal algorithms which are based on a recursive approach
172
In Order Traversal
start by traversing the left-hand subtree, visiting the root node first, then the right-hand sub-tree
173
Post Order Traversal
traverse the left-hand sub-tree, then traverse the right-hand sub-tree then return to the root node
174
Pre Order Traversal
start at the root node, then traverse the left-hand sub-tree followed by the right-hand sub-tree
175
Try/Catch Block
contains a set of statements for when an error occurs
176
Unrooted Tree
a tree without a clear root node
177
Unwinding
when a base condition is met and all function calls start to return
178
Validation
ensuring that the data meets certain rules. It does not ensure that data is correct
179
Batch Total
the sum of a particular field in a collection of items used as a control total to ensure that all data has been entered into the computer
180
Data Type Check
checks that data is the correct type
181
Existence Check
checks that the value exists in a table/file in the system
182
Format Check
checks that data meets formatting rules
183
Hash Total
number produced by adding together corresponding fields over all the records of a file, but the total has no external meaning and is used solely to verify the records in the file
184
Length Check
checks that data meets rules regarding a minimum or maximum length
185
Presence Check
checks that data was entered into a field
186
Range Check
checks the data item lies within an allowed range between a specified minimum and a maximum value
187
Variable
a computer memory location that is referred to by an identifier and holds a values that can change when the program is run
188
Global Variable
a variable available to all areas of the program
189
Local Variable
a variable only available to part of the program, such as in one subroutine
190
Variable Assignment
setting a value to a variable
191
Variable Declaration
when variables are declared, indicating variable name and data type
192
Verification
ensuring that data is correct
193
Double Entry
the data item is entered twice and the two copies are compared
194
Proof Reading
the data is entered and manually checked
195
Weight
a value associated with the edge in a graph
