Paper 2 Flashcards
Searching Algorithms D
Linear Search (can be used on Unordered list)
- Check first value, if desired value: stop
- Otherwise check second value, keep going until all elements have been checked or value is found
- not as efficient used on smaller lists
- once list has been ordered binary search is much more efficient
Binary Search (Ordered List)
- Put list in order
- take the middle value, if desired value: stop
- otherwise if its larger than desired value take list from left of middle value, if it is smaller take list to right of middle value
- take middle value of that list and keep repeating till value is found or list is too small to be split
Trace Tables D
- tests program for logic errors
- simulates the steps of algorithm
- each stage is executed one at a time allowing for inputs, outputs, variables and processes to be checked for the correct value for each stage
Key Concepts D
Computational Thinking
- use of computers to solve problems
- Developing algorithms to solve problems
- using abstraction, decomposition and algorithmic thinking
Abstraction
- removing unnecessary elements from problem
- using symbols and variables to represent real world problems
Decomposition
- Breaking down a large problem into a smaller problem
- smaller problems are easier to solve
- each part can be solved and tested independently
- parts are combined to produce full problem
- several ways to do this and they are all right
Algrothmitic Thinking
- a logical way of getting from the problem to the solution. If the steps you take to solve a problem follow an algrothim (set of instructions) then they can be reused and adapted to solve similar problems in the future
Error Types D
Syntax Error
- Code has not been correctly typed (typo)
- does not follow the rules or grammar of the programming language
- compiler or interpreter doesn’t understand something
Logic Error
- Program runs but produces unexpected result
- might be because program runs steps in incorrect order or multiplies instead of dividing
Sorting Algorithms D
Bubble Sort
- look at first two elements in a list, if 1 > 2 swap them, otherwise do nothing
- if they are in the wrong order you swap them or else do nothing
- move to the next pair in the list, repeat step 2. Until at end of the list (one pass), the last item will be in the correct place so don’t include in second pass
- repeat the passes till you have made your way through the list without any changes (no swaps)
Pros
- Simple algorithm that can easily be implemented
- efficient way to check if a list is already in order, only one pass to check if its in order
- Doesn’t use much memory as sorting is done using original list
Cons
- inefficient way to sort list, multiple passes or lots of comparisons
- Due to being inefficient it does not cope very well with a very large list
Merge Sort
- keep splitting list in half till individual elements are left
- merge pairs of sub-lists, each time you merge sort the items into right order
- keep merging till all pairs are in order
Pros
- more efficient and quicker than bubble sort and insertion sort for large lists
- it has consistent running time regardless of how ordered the items in the original list are.
Cons
- slower than other algorithms for small lists
- even if list is already sorted it still goes through the whole splitting and merging process
- uses more memory than other algorithms in order to create separate lists
Insertion Sort (CGP)
- look at second item in list
- compare to all items before it and insert number into right place
- repeat step 2 for third, fourth, fifth etc. Items until last number in the list has been inserted into correct place
advantages
- intuitive way of sorting things and can be easily coded
- copes very well with small lists - for this reason an insertion/merge hybrid sort is often used to take advantage of the strengths of each algorithm.
- all sorting is done on the original list so, like bubble sort it doesn’t require additional memory
- very quick to add items to an already ordered list
- quick at checking if a list is already sorted
Disadvantages
- doesn’t cope well with large lists
- requires lots of comparisons
Exam Reference Language D
Exam Reference Language
- looks like pretend code
- more formal way to represent algorithm for exam
- more like programming language but does not compile
- easy for programmers to read
Pseudocode D
Pseudocode
- uses short English words and statements to describe an algorithm
- Flexible
- less precise than programming language
- a little more structured than English
Completing an Algorithm D
Completing an Algorithm
- read what the algorithm should do
- note down the steps that should take place
- read steps of algorithms you already have
- use notes to write code to fill gaps
Correcting an Algorithm D
Correcting an Algorithm
- Read what the program should do
- Note down the steps that should take place
- Read each step of the algorithm
- At each step compare what the algorithm does to your notes
- take action to correct algorithm where it differs from your notes
Key Terms D
Algorithmic thinking - identifying the steps involved in solving a problem
Algorithm – a series of steps to perform an action or solve a problem.
Flowchart – a diagram showing inputs, outputs and processes within an algorithm
Process – an action that takes place
Pseudocode – simplified language used to design algorithms
Exam Reference Language – a more formal way of writing algorithms used within the exam
Sequencing D
Sequencing
- breaking down complex takes into simple steps
- order of steps matters
- step by step progress through program
Benefits
- each line follows the next
- can create simple programs very quickly
- Easy to follow for small programs
Disadvantages
- Not very efficient
- Difficult to follow for large problems
- Hard to maintain
Data Types D
Integers - whole numbers
Reals - decimal numbers
Boolean - TRUE or FALSE
Strings - alphanumeric characters
Casting is used to covert data from one type to another
Sub Programs D
Sub Programs
- used to save time and simplify code
- allows same code to be used several times without having to write it out each time
- Procedures are sets of instructions stored under a single name (identifier)
- Functions are similar to procedures but always return a value to the main program
- Parameters are values passed into the sub program, these are referred to as arguments when calling the sub program
- Both procedures and functions accept parameters
Arrays D
Arrays
- an ordered collection of related data
- each element in an array has a unique index, starting with 0
- all elements must be the same type of data
- usually a fixed size
- 1D arrays, each element needs a single index number, similar to lists
- 2D arrays, each elements needs two index numbers, similar to tables
String Manipulation D
String.length String.upper String.lower String.substring(1, 2) String.left(3) String.right(2) String+string
Keywords D
Variable
- a box in which data is stored
- contents change as program runs
Assignment
- process of changing data stored in a variable
- copies value into memory location
- different values may be assigned to a variable at different times during execution of program
- each assignment over writes current value
Constants
- Data does not change as program runs
- used to reference known values such as pi
Inputs
- may come from a user, a file or elsewhere
- usually treated as text even if it contains numbers
Outputs
- The end results of a program
- may be displayed on screen, written to file or sent to device
Operators
- used to manipulate and compare data
Operators D
Arithmetic Operators
- addition (+)
- subtraction (-)
- Multiplication (*)
- division (/)
- Modulus (MOD) remainder from division
- (DIV) Integer division
- (^) Exponentiation, to the power of
Comparison Operators
- (==) Equal to
- (!=) Not Equal to
- () greater than
- (>=) greater than or equal to
Boolean Operators
- AND, two conditions must be met for the statement to be true
- OR, at least one condition must be met for the condition to be true
- NOT, inverts result
Selection D
Selection
- allows programs to make decisions
- uses conditions to change the flow of the program
- selection may be nested inside one another
- IF statements compare sequentially and so order is important
- SELECT case has less typing but is less flexible
Random Numbers D
random(5)
Iteration D
Iteration
- iterating through a set of steps several times
- also known as looping
Count Controlled Iteration
- Repeats the same code a set number of times
- uses variable to track how many times the program has been run
- this variable can be used in the loop
- at the end of each iteration the variable is checked to see if the program should run again
Condition Controlled Iteration
- uses condition to determine how many times it should be repeated
- while loops run while condition is met
Authentication D
Authentication
- a coding method to check that the user is who they say they are, and that the user is allowed to access the program
- asking for username and password
authentication factors
- Something you are, finger print or iris scan
- Something you know, password, pin or secret answer
- Something you have such as a swipe card or mobile phone app
- 2FA is where two different authentication types are required to access the program
Input Validation D
Input Validation
- Applies rules to inputs, inputs that do not follow the rules is rejected to prevent it from crashing program
- Wont catch all errors as users still make typos
- Verification requires the user to enter this info twice to reduce the risk of this
Range Check
- Input must be within a range
Length Check
- Input must not be too long or too short
Presence Check
- The input must be present, for example requiring a credit card number for online order
Format Check
- input must be in the correct format
- for example must have @ and a . for email
Type Check
- data must be a specific type
- requiring currency input to only be numbers
Look-up table
- Checks data against table of acceptable values
Naming Conventions D
Naming Conventions
- Use same rules for naming to make it easier to read
- easy to read and meaningful
- Makes code easier to understand
Indentation D
Indentation
- allows code within a particular function or procedure to be group together
- Multiple levels of indentation may be used
- often used in IF statements
- makes code easier to read and understand
- makes it easier to focus on particular parts of program when needed
Commenting D
Commenting
- lines within code which are not executed
- starts with certain character depending on language used (python is #)
- informs reader about bugs or issues in the code
- explains functionality of particular code
- explains purpose of particular code
- prevent code from executing without deleting fully
Refining Algorithms D
Refining Algorithms
- User prompts should be helpful and explain any input validation rules
- code should convert input into correct data type if required
- loops can be used to request the user to re-enter data if it is invalid
- may be a limit on how many times the user is asked in the case of passwords or other security fields
Selecting and Using Suitable Test Data D
Selecting and Using Suitable Test Data
- A range of data should be used when testing
- Normal data is correct and what would usually be inputted by the user
- Boundary data is correct but is the largest or smallest value which a user might input
- Invalid data is too large or small
- Erroneous data is completely
incorrect, for example entering Bob into an age field
Test Plans D
Test Plans
- Provides structure to testing
- Records the results of testing
Should Include:
- Test number
- Data entered
- Type of data
- expected outcome
- result of the test
- Any action required as a result
Anticipating Misuse D
Anticipating Misuse
- May be a brute force attack on the program
- May be user entering incorrect input to try and break the program
- May be user entering code into input fields to access parts of the program they shouldn’t
- May simply be an error in the input
Testing D
Testing
- Newly written code often contains more errors
- Testing helps locate and remove these errors
- Ensures the program works the way it should
Iterative Testing
- Takes place whilst program is being written
- programmer tests individual lines of code or sections as they are written
- if an error is found it is fixed, and code tested again
- Process repeats or iterates till code works as intended
- it is easier to fix errors in small sections of code
Final Testing
- Takes place once code is finished
- a final check to make sure code works correctly
- makes sure program does what it should
- harder to locate and fix errors at this stage because of the amount of code
Truth Tables D
Truth Tables
- Used to show outputs of logic gates or circuits
Key Terms D
Logic Gate - components which compare one or more inputs based on a logical function to provide single output
Logic Diagram - a diagram showing one or more logic gates
Transistor - Components contained in the CPU which can either be on or off
Truth Table - a table representing the possible outputs of a logic gate or diagram
Logic Circuit - two or more logic gates used together one after the other
Binary - a number system containing two symbols, 1s and 0s also known as base 2
IDEs (Integrated Development Environments) D
IDEs - a software package containing several features useful for writing code
Editor
- Allows code to be written and edited
- Fairly simple with programmer specific features
- Automatic line numbering
- Colour coding
- Auto-Correct
- Auto-Suggestion
- Auto-indent
Runtime Environment
- software which allows code to run on different platforms to which they were written on
- allows code to be written for specialist hardware without having that hardware on hand
- creates virtual machine to run code in
Translators
- Translates code into format which computer can execute
- Allows code to be run and tested within the IDE
Error Diagnostics and Debuggers
- helps locate and fix errors
- breakpoints allow program to be paused at certain points so that the programmer can then examine different parts of the code or variables
- Variable tracing shows the changing values of variables as the program runs
- Syntax highlighting shows where syntax errors occur
Low Level Languages D
1st Generation (machine code)
- Also known as machine code
- can be executed directly by CPU
- generation that computers understand
- difficult for humans to understand, write or debug
- 1s and 0s
2nd Generation (Assembly Code)
- also known as assembly code
- uses mnemonics (abbreviations)
- easier for humans to understand and program but still difficult
- 1-1 relationship with machine code, one Assembly language instruction translates to one Machine code instruction
- Must be translated into Machine code for execution
- Commonly used to program device drivers
High Level Language D
3rd Generation
- still easier for humans to understand, program and debug
- Uses English-like key words
- 1-many relationship with machine code, 1 instruction translates into many Machine code instructions
- Examples include Java, Basic and Pascal
- Translated using compiler or interpreter
4th Generation
- also known as declarative languages
- has strict fact and rules for use
- ……… (messaged sir on teams)
Translators D
Translators
- translates a language into a form that the computer can directly execute
- compilers and interpreters are used for third generation languages
Compilers D
Compilers
- Translates whole code into Machine code in one go
- Optimise the code
- Used at end of development when code is finished
- Create error reports and object code
Interpreters D
Interpreters
- Translate and execute source code
- Work line by line
- Syntax is checked
- if code is correct it is executed
- if code is in correct interpreting is stopped
- Aid debugging
Compilers (Advantages and Disadvantages) D
Compilers (Advantages)
- Compiled programs run quickly and without needing additional software
- Compiled programs can be supplied as a executable file which cannot be easily modified
- Optimise code so it runs quickly and uses less memory
Compiler (Disadvantages)
- because the source code is translated as a whole more memory is needed
- requires a temporary working space for the compiler to perform the translation
- Do not spot errors
- code must be recompiled every time it changes
- code compiled on one platform will not run on another
Interpreters (Advantages and Disadvantages) D
Interpreters (Advantages)
- instructions are executed as soon as they are translated
- Instructions are not stored for later so less memory is needed
- Errors can be quickly spotted
Interpreters (Disadvantages)
- CPU must wait for each instruction to be translated so execution is slower
- Code is translated each time it is run
- do not produce an executable file that is distributable
- Do not optimise code
