1.3 - Algorithms Flashcards
What are the two ways algorithms can be defined?
- Flow Charts
- Pseudo Code
- Structured English (Additional)
What shape is the start/stop symbol?
- Rounded off rectangle
What is represented by a rectangle?
- A process
What shape is a decision represented by?
- A diamond
What is represented by a parallelogram?
- Input/output
What shape is a connector (jump from one point in the sequence to another) represented by?
- A circle
What do the arrows represent?
- The direction of flow
What is the use of a variable?
A variable is a named area of memory used to store data that may change when the program is running
What is the use of a constant?
A constant is a named area of memory used to store data which will not change
When are values passed by value?
This is where only the value of the data is passed and therefore it cannot be accidentally changed by the procedure
When are values passes by reference?
This is where the memory address of the data is passed and therefore the procedure can update the its value
What is the difference between a local and global variable?
Global variables can be changed anywhere in the program whereas local variables be used in the procedure where it is declared
What is a parameter?
A parameter is a variable / value that can be passed to / from the procedure
What is the difference between validation and verification?
- Validation checks if the data seems right
- Verification checks if the data is accurate
What two features of does a recursive algorithm need?
- To call itself
- Needs a base case
Describe a bubble sort
- A pass is made over the data
- Neighbouring items are compared
- Swaps made if necessary
- Stops when a pass is made with no swaps
Describe an insertion sort
- An unsorted item is compared with the sorted part of the list
- Items in the sorted list are shifted to make room for the new item
- Process continued until the data is sorted
Describe a quicksort
- The middle of the list is a pivot
- Two sub-lists are created one less than pivot, one greater than pivot.
- Two more pivots are chosen in each sub list and process is repeated
- Continued until all items are pivoted and list is sorted
Give an advantage and disadvantage of recursion
- Some problems can be coded more compactly using recursion
- Less efficient than non-recursive algorithms
- Difficult to debug as you don’t know which recursive cell produced the error
Put these into order from most efficient to least efficient:
- O(n log n)
- O(n!)
- O(n^c)
- O(log n)
- O(n)
- O(c^n)
- Logarithmic
- Linear
- Super Logarithmic
- Polynomial
- Exponential
- Factorial
What can big O notation refer to?
- Time efficiency
- Memory efficiency
How would you analyse an algorithm’s time efficiency?
- Look for the number of calculations / operations
- Each has a value of 1
- If the calculation is inside a loop, it is multiplied by how many time that loop runs in terms of n
- In terms of n, find out how many calculations occur in the whole algorithm
- As n increases, the highest power of n dominates
- Therefore O(n^c)
How would you analyse an algorithm’s memory efficiency?
- Look at the number of variables / constants declared
- Constants and variables have a value of 1
- 1D arrays have a value of n
- 2D arrays have a value of n^2
- And so on…
- Overall the highest power of n dominates there for O(n^c)
What is lossless compression and where can it be used?
This is where no data is lost when compressing the file instead the data is stored more efficiently to reduce the file size
- e.g A word document
What is lossy compression and where is it used?
This is where data is removed from a file to reduce its size. It does this by discarding detail that humans can’t notice or data that that it doesn’t need to make sense.
- Images
- Audio
- Video
What is the compression ratio?
This is the ratio of the original file size to the new compressed file size.
What is compression/decompression time?
The time needed to compress or decompress a file
What is the saving percentage?
A percentage measure of how much smaller the compressed file is to the original file.
How is a sound file compressed?
- Discarding sounds that humans can’t hear as when two sounds are playing, we only hear the louder one
- Decrease the sample rate
What is Huffman encoding?
It is a dictionary encoding method which stores all the characters that are used in a text, the more commonly used characters are given a shorter code. These codes are then used in the composition of the file. this reduces the file side as the character code is smaller than the ASCII value.
