Algorithms and Programming Flashcards
Algorithms
unambiguous series of instructions needed to create a task that is language neutral and not in code
Annotation
add comments to explain function of each section of the code
Arbitrage Opportunity
converting between currencies to generate profit
Arithmetic Efficiency
used to describe the efficiency of an algorithm based on standard mathematical functions, with O standing for Order
Auto-Completion of Statements
gives suggestions in a drop-down menu when the user is typing, saving time and minimising bugs
Auto-Completion of Statements
gives suggestions in a drop-down menu when the user is typing, saving time and minimising bugs
Automatic Formatting
may also include automatically indenting code, saves time and reduces chance of bugs
BNF
Backus-Naur Form
used by the developers of programming languages to specify the syntax rules of a language
Base Condition
a requirement in recursive functions, without which the function will continue to execute in an infinite loop
Basic Operation
the operation which contributes most to the total running time
Big O Notation
tells you the number of operations an algorithm will make
Constant Time
O(1)
this takes the same amount of time to complete regardless of the amount of input data
Exponential Time
O(2^n)
where the time taken to complete will double with every extra data item, such as a recursive Fibonacci algorithm
Factorial Time
O(n!)
where the time taken to complete will grow much faster than the exponential time, for example, in password cracking programs
Linear Time
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
O Growth Time
O(n log^2 n)
where the time complexity depends on n, such as in a recursive quicksort algorithm
Polynomial Time
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
Block Code
putting code into blocks where each block deals with one task
Blue Screen of Death
signifies a fatal error with the operating system
Bracket Matching
automatically adds a bracket after an opening bracket has been added, saves time and reduces chance of bugs
Branches
links nodes together in a tree structure
Breakpoint
causes program to run up to a point and then pause, allowing for variable inspection
Bubble Sort
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
Colour Coding Key Words
an automatic function in the IDE, helps with preventing bugs
Compression Algorithm
process that reduces a file’s size for efficient storage or transmission
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
Dynamic Allocation
memory space is only allocated when required at runtime
Huffman Coding
a form of lossless compression which makes files smaller using the frequency with which characters appear in a message
Lossless Compression
a way of compressing data without removing parts, such as ZIP files
Lossy Compression
a way of compressing data by removing parts, permanently changing it, using this equation: compression ration = original file size / compressed file size
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
Condition
a Boolean test which can either be true or false
Condition Controlled Loop
where code statements are repeated whilst a condition is met
Constant
hold a fixed value, stored in memory, have an identifier, data type and value and cannot change during execution of the program
Constant Declaration
involves specifying the identifier, data type and value
Constant Growth Rate
most iterative algorithms will have a constant growth rate of O(1), for example, in an iterative sorting algorithm
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
Control Flow
the order in which statements, instructions or function calls of an imperative program are executed or evaluative
Control Operations
where instructions don’t have to be carried out in order
Conditional Operations
a control structure that checks if a condition is true or false then executes an instruction based on the answer
Iterative Operations
a control structure that repeats a set of instructions until a condition is met using loops
Count Controlled Loop
where code statements are repeated a specific amount of times
Current Pointer
position in the array of the current node
Data Type
indicates size of variable and enforces some rules about the nature of the variable
Debugging Tools
a software tool in the IDE that helps the user identify errors in the code
Breakpoint
causes program to run up to a point then pause, allowing for variable inspection
Step Thru’
steps through program one statement at a time, allowing faults in program logic to be identified
Variable Inspection
allows variables stored in a program to be watched as the program runs
Variable Watch
the act of observing a specific variable whilst the program runs, which the programmer can do whilst using variable inspection
Declarative Program
used in programs such as Chat GPT, involves telling the computer what needs to be done instead of how to do it
Defensive Programming
a form of defensive design intended to develop programs that are capable of detecting potential security abnormalities and make predetermined responses
Digit
a symbol that can be used with other digits to represent a number
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
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
Error
problems in the program
Linking Error
an error that occurs when the program calls a library that has not been linked to the program
Logical Error
when the code runs, but does not do what you want it to do
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
Runtime/Execution Error
an error that occurs when a program requests more memory than is available
Semantic Error
error in the meaning of the code
Syntax Error
an error that occurs when a program does not follow the expected syntax of the code
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
Error Trapping
refers to the prediction, finding and fixing of programming errors
Exception Handler
the process of responding to anomalous or exceptional conditions requiring special processing
Explorer’s Problem
a problem in which the solution finds a route that traverses each road exactly once before returning to the starting point
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
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
Complexity
how big an executable file is
Compression Ratio
how much space it saves
Latency
how long you have to wait until it starts streaming
Portability
whether files are readable by any standard compression utility
Space
how much RAM the algorithm needs to run
Speed
how fast it is
Flag
a specific symbol such as a dollar sign that designates RLE
Free Pointer
points to the next free space in the list
Function
self contained modules of code that accomplish a specific task, and can be recalled several times in the program
Graph
a non-linear data structure that comprises a set of connected nodes
Head Pointer
points to beginning of list
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
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
Hyperlocal Variable
a variable used in extreme isolation
Identifier
allows program to retrieve the value stored in the variable for memory
Illegal Operation
an operation that cannot be run by the system
IDE
Integrated Development Environment
an integrated set of tools used in software development
Imperative Program
involves giving the computer a clear set of instructions, which it then follows exactly
Indentation
shows the structure of the program
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
Intractable Problem
a problem that cannot be solved because it takes up too much memory
ADD
add one number to another
AND
Boolean algebra function
DEC
decrement a number by 1
INC
increment a number by 1
JMP
jump to another section of code
JNZ
jump to another section of code if the number is not 0
JZ
jump to another section of code if the number is 0
MUL
multiply two numbers together
NOT
Boolean algebra function
OR
Boolean algebra function
SUB
subtract one number from another
XOR
Boolean algebra function
Iteration
where code statements are repeated
Leaf
a terminal node with no children
Left Pointer
position of the item to the left of the current node
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
Linear Growth Rate
the growth rate of a factorial recursive function
Linker
combines pre-compiled modules of code, such as standard libraries, into a single executable file
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
Logarithmic Growth Rate
the growth rate of quicksort algorithm
Lossless Compression
used to compress files using run length encoding so does not involve removing data as it looks for repeating
Lossy Compression
used to store images (JPEG), sound (MP3) and videos (MP4) which involves removing part of the data
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
Manual Techniques
tools to detect errors
Dry Running
where a programmer manually goes through the code line by line to find the error
Rubber Duck Debugging
where a programmer explains to a rubber duck what the code will do
Trace Table
used to track how variables change when a program is run
Tracing
where a programmer manually goes through the code line by line to find the error
Variable Dumping
write variable values to screen as the program runs
Memory Inspector
allows contents of computer memory to be examined
Memory Management
the process of controlling and coordinating a computer’s main memory
Memory Protection
a way to control memory access rights to a computer
Modularisation
use of functions and subroutines to break up programs into a series of subprograms
Negative Compression
where compression causes a file to grow in size
Nesting
where one statement is placed within another to build up the complexity of the code
Null Pointer
points to the end of the list
Number
represents an amount of stuff
Number System
the way in which numbers are represented by digits
Object-Oriented Program
programming based on the concept of objects, which can contain data and code
Paradigm
a distinct set of concepts or thought patterns
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
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
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
Parent
nodes in a tree can only have one of these
Partition
an unsorted section of the list, is repeatedly partitioned until every partition contains only one number and the list is sorted
Passing by Reference
allows a function to modify a variable without creating a copy
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
Point of Invocation
the place where the function was called from
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
Processing
all code other than input or output
Program
implementation of algorithm, a list of instructions that a computer has to work through in order to complete a specific task
Program Logic
the thinking, planning and implementing behind coding
Pseudorandom
randomness satisfying one or more statistical tests for randomness but produced by a definite mathematical procedure
Publisher
packages the programs and its sub-modules into a single easy to install package for program development
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
Recursion
a function that calls itself and stops calling itself when a base condition is met
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
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
Recursive Step
a step that will be followed until the base condition is met in recursion
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
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
Regular Language
any language that a finite state machine (FSM) will accept
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
Reverse Polish Notation
the order in which computers execute operations, effectively computer BODMAS
Right Pointer
position of the item to the right of the current node
Root
the top node in a tree
Rooted Tree
a tree structure with a clear root node
Searching Algorithm
a computer uses searching algorithms to search for a value in a given list
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.
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
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
Second Search
checks every second record, then goes back if it has gone past what it is searching for
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
Rooted Tree
a tree structure with a clear root node
Selection
where code statements are carried out based on the results of a condition
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.
Sequence
a block of statements where every statement is carried out in written order, and each statement is carried out once
Sequence Block
a block of statements where every statement is carried out in written order, and each statement is carried out once
Sequential Operations
instructions that are executed in order
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
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
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
Depth-First Traversal Algorithm
traversal algorithms which are based on a recursive approach
In Order Traversal
start by traversing the left-hand subtree, visiting the root node first, then the right-hand sub-tree
Post Order Traversal
traverse the left-hand sub-tree, then traverse the right-hand sub-tree then return to the root node
Pre Order Traversal
start at the root node, then traverse the left-hand sub-tree followed by the right-hand sub-tree
Try/Catch Block
contains a set of statements for when an error occurs
Unrooted Tree
a tree without a clear root node
Unwinding
when a base condition is met and all function calls start to return
Validation
ensuring that the data meets certain rules. It does not ensure that data is correct
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
Data Type Check
checks that data is the correct type
Existence Check
checks that the value exists in a table/file in the system
Format Check
checks that data meets formatting rules
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
Length Check
checks that data meets rules regarding a minimum or maximum length
Presence Check
checks that data was entered into a field
Range Check
checks the data item lies within an allowed range between a specified minimum and a maximum value
Variable
a computer memory location that is referred to by an identifier and holds a values that can change when the program is run
Global Variable
a variable available to all areas of the program
Local Variable
a variable only available to part of the program, such as in one subroutine
Variable Assignment
setting a value to a variable
Variable Declaration
when variables are declared, indicating variable name and data type
Verification
ensuring that data is correct
Double Entry
the data item is entered twice and the two copies are compared
Proof Reading
the data is entered and manually checked
Weight
a value associated with the edge in a graph
