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
