1.3 Flashcards
Algorithm
A set of instructions designed to solve a problem
Identifier
A name given to an element of a program so it can be referred to throughout
Good Programming Practice
- Meaningful names, clear what variable is holding
- Annotation, easier for programmers to follow
- Program Layout, see each function and aids readability
Variable
An attribute within a program whose value can be reassigned (during execution)
Constant
An attribute within a program which never changes its value (during execution)
Global Variable
- Declared at the top of the program
- Available to the whole program
Local Variable
- Declared inside a subroutine
- Available only to that subroutine
Sequence
Steps processed once
Selection
- Uses a logical condition to determine which line of code to process next
- Purpose: to execute code if a certain condition is met
Nesting
When another selection statement is contained within an existing selection statement
Repetition
Purpose: to repeatedly execute code until a certain condition is met
Count
A value in a loop that will increase/decrease each time the loop is executed
Rogue Value
a value which tells the computer that input has finished
DIV
//
How many times one number goes into another
MOD
%
Remainder after DIV
Lossy Compression
- Cannot be decompressed to yield back the original data
- Not Good method for critical data such as text
- Good for digitally sampled analogue data e.g. Sound/Video/Graphics
- Algorithms vary but many use threshold truncation
Lossless Compression
- Original message can be decompressed back to it’s original form
- Good for text
- Good for high quality media e.g. .FLAC .PNG
Character Combinations (Compression)
Finding frequently occurring character combinations and replace them with tokens
Run Length Encoding
Replace long strings with a number
Photo Compression
Approximate all shades of blue in a photograph to one shade and only store this colour instead of every pixel
Sub Sections
- Algorithms and programs can be broken down into smaller parts.
- These are named, reusable pieces of code that can be called any number of times within an algorithm to perform a specific task.
Sub Sections Advantages
- Can be developed by teams, easier to write.
- Code is more readable
- Avoids duplication of code.
- Sections can be tested individually.
Standard Module and Function
STANDARD FUNCTION
Carries out a common task for a standard situation in a program and is provided by the compiler/interpreter
STANDARD MODULE
Contains a group of related standard functions
EG: Module = math
Function = math.cos(x)
Standard Module Advantages
- Pre-written / No need to write again (Saves Development Time)
- High Quality as written by experts
- Already Tested/Used – Less Errors
User defined sub functions
a section of code (method) which is written for a specific purpose by the programmer
Parameter
a value which can be passed to a procedure or function
Reference Parameter
the memory address of the original data is passed to the procedure
- The (original) data can be altered
- A list, object or any non-primitive data type
Value Parameters
a copy of the data is passed into the procedure
- Useful in calculations (not change original data)
- Avoids unwanted side – Prevents the original value being changed by mistake
Linear Search
- Used on an unordered (or ordered) array
METHOD
- Cycle through each element in turn
- Compare current element with SearchValue until a match is found or we get to the end of the list
Dry Run
A dry run can be used to determine what a section of unknown code does.
Binary Search
- Used for searching an ordered array
METHOD
- Calculate mid element in the array
- Compare SV with the middle element
- If SV is not found, search lower/upper half
- Repeat until found (or not present in array)
Bubble Sort
- A pass through the data comparing each value with the following one and swapping values if necessary
- A number of passes is made until the data is in order
Insertion Sort
- Whilst being processed, the array is effectively split into sorted/unsorted
- Items are copied one by one (from unsorted part of the array)
- Each new item is inserted in the correct place in the output (sorted part of the array)
Why Psuedocode
- Language independent
- Easy to read/understand
Translatable into any programming language
Logical Error
A bug in a program that causes it to operate incorrectly, but not to terminate abnormally
- produces unintended or undesired output or other behaviour, although it may not immediately be recognised as such
Recursive Algorithm
- Calls itself (with different input values)
until the terminating condition is met. - Values are placed onto the stack
- Complicated to program and debug
- Uses more memory, if not terminated could use all stack space causing the program to crash
- Can be a more elegant solution to a problem e.g. factorial
- Usually less lines of code.
Recursion Potential Problems
- Difficult to program (effectively)
- Memory overheads of stack use with many recursive calls
- Infinite Loop (Run out of memory)
- Stack Overflow Exception risk
- Difficult to debug if there is a fault
Quick Sort
- Quicksort is a recursive sorting algorithm
METHOD
- Select a pivot value
- Re-order the data, producing 2 sub-lists: one which contains items smaller than the pivot, one which contains items greater than the pivot
- Perform the same action on the sub-lists (recursively)
until each sub-list has only one element - Rebuild the List
Big O
An approximation to compare algorithm efficiency
- Constants are dropped
- As n tends towards infinity, the constant will become insignificant
- The biggest value of O will always override all other values
Big O, 1 loop through all items
O(n)
Big O, 2 nested for loop
O(n^2)
Big O Linear Search
O(n)
The time to complete grows linearly in comparison to the size of the data.
Big O Binary Search
O(log n)
The time to complete initially grows in a linear way when compared to the size of the data. As the data size grows larger the time taken starts to flatten off.
Big O Quick Sort
O(n log n)
Big O Bubble Sort/ Insertion Sort
O(n^2)
Big O Fibonnacci
O(2^n)
Big O Factorial
O(n!)
is cato cool
yes
