Algorithms & Programs Flashcards
What is an algorithm
A set of rules to solve a specific problem
What are the 3 most common methods for describing an algorithm
Pseudocode
Structured English
Flow Chart
What are 3 good programming practices to follow do that your program can be edited more easily in the future
Self documenting identifiers - suitable names for identifiers
Annotation - describe what the code is doing
Program layout - looks tidy and easy to differentiate different parts
What are parameters
Sets of conditions
Define a variable
A variable is a store of data
What is a constant
A constant is a variable which value doesn’t change during the runtime of a program
What is the lifetime of a variable
The lifetime of a variable is the duration of time for which the variable holds the value during the execution of a program
What is the scope of a variable
The scope of a variable describes the parts of the program in which the variable can be accessed.
E.g. a global variable would have a scope of the entire program
What is a subroutine
Performs a specific task packaged as a unit
What are the advantages of subroutines
Makes the program easier to understand by splitting into smaller chunks
By splitting the program into separate subroutines, it is easier to test each procedure in isolation before being used with the rest of the program
Allows team-working as different members of a team can be allocated different procedures to write
Procedures can be reused in future programs. It is also possible to compile procedures and put them into subroutine libraries so that they can be called from other programs.
What are the two types of subroutine?
Procedures or functions
What is the difference between a function and a procedure?
A function produces am output/returns a value whereas a procedure doesn’t
What is a function?
A section of code that, when programming, can be called by another part of the program with the purpose of returning one single value
What is a procedure?
A section of code which performs a specific task when called from elsewhere in the program
What is a parameter?
Values that can be sent to a procedure and/or received from a procedure
What are the two types of parameters
Value or reference
What is passing by value?
Parameters that are used to pass information into a procedure but which do not receive information back
E.g. this works by sending a copy of the parameter to the procedure so any changes made are to the copy and therefore so not affect the original value
What is passing by reference?
Parameters that need to be able to pass information back.
E.g. this works by sending a copy of the memory address is passed into the procedure and therefore any changes made are to the memory location of the variable sent to the procedure.
Subroutines as a black box, what does this mean?
Separate from the rest of the program, hides the complexity within the subroutines
Ignored by programmers who are developing it ofc
A programmer only need to know the parameters (inputs and outputs) to the procedure and doesn’t need to know how the procedure works (I.e. what goes on inside)
Therefore code inside the procedure can be modified/improved without other parts of the program bring affected as long as it continues to use the same parameters
This is also why global variables are best avoided where possible as these are ways in which the procedure can interact with the rest of the program without using parameters
What are modules
Modules are collections of subroutines (procedures & functions)
Modules should he loosely coupled and highly cohesive, what does this mean?
Loosely coupled - independent or almost independent (they can function completely without the presence of the other) (the module is not much dependent on other modules)
Cohesion - the degree at which different parts of the module related to eachother
E.g. a module used to calculate tax returns should just contain subroutines used in different steps od the tax return process, and not routines used for other parts of the system (the parts of a module fit together to a high degree)
What is validation?
Checking how appropriate the data being entered is
What are the 6 types of validation
Range check - makes sure data is between a min and max val
Presence check - ensures that a particular data item hasn’t been omitted
Length check - could be min or max length of characters entered
Type check - ensures that the correct type of data has been entered e.g. quantity field only contains digits
Format check - correct format e.g. dd/mm/yy
Lookup check - checks the data entered is present in a list of possibilities e.g. confirms a postcode exists
What is verification?
Checking to see if the data entered is consistent
E.g. asking for you to enter password twice when changing it to avoid locking yourself out of your own account
What is DIV
Returns the amount one number goes into
E.g.
7 DIV 3 = 2
What is MOD
Returns remainder
E.g.
7 DIV 3 = 1
What is a recursive algorithm
An algorithm that calls itself and has a terminating condition
Any algorithm that is recursive could instead be written in an iterative way (using loops)
However, recursive algorithms usually require much less code and are therefore more elegant and in many cases a more natural way of thinking about the problem.
Downside is when a recursive algorithm runs it can use more memory as it needs to keep track of each of the multiple calls to the procedures on the run time stack
Why are sorting algorithms important, why do we sort data?
Makes it easier to do tasks with
Write bubblesort pseudocode
Answer on flashcard sheet
Describe a bubble sort
Bubble sort is a simple sorting algorithm
It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order
After 1 pass the largest number should be moved to the last spot in the list
The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted
Describe an insertion sort
Starting with the second item, compare to all items before it in the list, shifting them up one place until the correct place to insert the item is found
E.g.
Insertion sort pseudocode
Check sheet
What are the three characteristics of a recursive algorithm
- parameters
-function that has a terminating condition
-calls itself
When testing a sorting algorithm what different types of data should we use?
Random numbers
Same numbers
Nearly sorted
Unordered
Using 0 in list
Low to high order
High to low order
Describe quick sort
- Find a pivot (data before pivot is listA, data after pivot is listB)
2.Move data less than the pivot into ListA and data after the pivot into ListB
- Split into sub-lists and quicksort again
- Terminate when there is only one item left in the list
The terminating condition is that it only calls quicksort if the list has more than 1 item in it
It is extremely fast when compared to the other sort algorithms, particularly with longer lists. However, as with all recursive algorithms it will use more memory when executing.
Quicksort pseudocode
See sheet
Why not make all parameters reference parameters?
There is a danger that the programmer of the procedure might accidently change the parameter values and so it is safer to pass a parameter by value so that the data can not be changed, even accidently
Describe a serial search
Looking at each item one after the other until the item is found or the end of the list is reached
Describe a sequential search
search is a slight improvement over serial search and can be used where the data is already sorted in order of the search field but where binary search can’t be used because direct access isn’t possible (e.g. searching a file on tape).
When searching through the list if an item is read that would be after the item being searched for then the search can stop immediately rather than waiting until end of list.
Binary search
Extremely fast way to find data in a list, the data has to be sorted in order of the field being searched.
Can only be used where there is direct access to items in the list (e.g. data in memory or on disk)
Can’t be used to search data in a file on tape storage
How does binary search work
The middle item is examined to see if it is the item being searched for
If it isn’t then either the bottom half or the top half of the list is discarded and the search then continues by again choosing the middle item in that half of the list.
This is a ‘divide and conquer’ algorithm where the amount of data to search reduces very quickly.
Binary search is sometimes implemented using recursive methods and sometimes using non-recursive (iterative). There isn’t really much difference between them: the recursive version is a little shorter and more elegant but will take up more memory on the stack when running.
What is dijkstras algorithm
Used to find the shortest path between 2 nodes
Used in e.g. satnav, routing around the Internet, path finding in video games etc.
Do big O questions
..
Do dijkstras algorithm questions
..
What do algorithms consist of
Sequence - executing lines of code one after the other in the order given
Selection - where there is a choice as to whether a set of instructions are executed (e.g. if statement)
Repetition - where the same instructions can be repeated in a loop
What do algorithms consist of
Sequence - executing lines of code one after the other in the order given
Selection - where there is a choice as to whether a set of instructions are executed (e.g. if statement)
Repetition - where the same instructions can be repeated in a loop
Co
What do algorithms consist of
Sequence - executing lines of code one after the other in the order given
Selection - where there is a choice as to whether a set of instructions are executed (e.g. if statement)
Repetition - where the same instructions can be repeated in a loop
Counts - where we need to keep track of the number of items or where we are in a list e.g. total = total + 1
Rogue value - a special value in a data set that indicates the end of the data
What do algorithms consist of
Sequence - executing lines of code one after the other in the order given
Selection - where there is a choice as to whether a set of instructions are executed (e.g. if statement)
Repetition - where the same instructions can be repeated in a loop
Why should you split programs into modules?
Can help to logically split a program up into sections relating to the task at hand e.g. sound effects, combat
Can be easier to test modules in isolation before linking it to the rest of the program
Modules can be worked on at different times by different people which would be difficult otherwise
Modules can be compiled separately and can be linked to other modules using the linkage editor
After compilation, can be stored on a computer in a subroutine library which can be used in future applications
Are loosely coupled and highly cohesive
Why are subroutine libraries used
They are a folder (or folders) which store compiled, tried and tested, documented modules that can be used in other programs
Saves a lot of time as they don’t have to be written again
Data compression
When the size of a file (or any block of data) is reduced
Two types
Lossy
Lossless
Describe lossy compression
Reduces the size of a file but does it by losing some of the information
E.g. reducing the quality of jpeg or mp3 files
Describe lossless compression
Reduces the size of a file without losing any information
E.g. png images, zip files, rar files
Describe lossy compression
When compressed files are decompressed they do not give back the original data, because data was lost during compression
Because lossy compression cannot be decompressed to yield the exact original data, it is not a good method of compression for critical data, such as textual data
It is most useful for digitally sampled analogue data, such as sound, video, graphics or images
What is run length encoding
A simple lossless compression technique
Where there are sections of a file where the same data repeats this is replaced with a single data value and a count.
This is less successful with text but is used with image and audio files.
Dictionary encoding
A lossless compression technique
A dictionary of commonly occurring sequences of characters is created and in the text these sequences are replaced by pointers to the relevant dictionary entry.
The references are shorter than the data they replace so the file is reduced in size.
Huffman Coding looks at the frequency of each character with the most frequently used characters given a shorter code than others.
How do you Dry run an algorithm
You may be asked to dry-run an algorithm with specified test data, either to try to identify what the algorithm does or to identify why an algorithm gives an error.
To dry-run, use a trace table with a column for each variable and if applicable, a column for output. As values change you should note those changes in the table.
Why are procedures used in algorithms
Algorithm can be broken into smaller parts
Used to avoid the duplication of code
Procedures are used to make an algorithm/program more efficient and secure
Each procedure can be tested in isolation
Standard module benefits
A standard module is one which carries out a common / standard task
E.g. print function / input
Benefits of passing by reference
Avoids the larger amount of processing/storage (associated with padding by value)
- allows the desired change to be passed back into the calling program
