Part 6, Algorithms Flashcards
finish the sentence
a well written algorithm can be
implemented into many different programming languages
give a definition that would describe an algorithm for a program
a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.
what is this sentence a definition of
a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.
this is the definition of an algorithm for a program
what is meant by unambiguous in the definition for a programs algorithm
a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.
the term unambiguous means that no part of the algorithm is open to interpretation
the algorithm is therefore written clearly and precise for the benefit of the computer and anyone wanting to reuse the algorithm
what is meant by self contained in the definition for a programs algorithm
a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.
the term self contained means that the algorithm contains all information it needs
therefore when using the algorithm it will require no external sources of information or extra work put into it
what is meant by step-by-step instructions in the definition for a programs algorithm
a set of unambiguous, self contained, step-by-step instructions. Guaranteed to complete a particular task in a finite amount of time.
step-by-step instructions means that the algorithm is written in steps which eventually lead to the desired outcome
this is much like the steps written in a recipe
an algorithm needs refinement/decomposition
what does this mean
this means the algorithm is open to more than one interpretation
it should be refined or decomposed until all ambiguities have been resolved
an algorithm is open to more than one interpretation what two terms describe the process it must go through to rid it of the open interpretation
refinement
decomposition
what method might you use to refine an algorithm that is open to more than one interpretation
break the step down into several smaller clearer steps
how can you tell when an algorithm is refined fully
the algorithm will be clear and precise to the author and any audience that uses it
what four fundamental features do all algorithms share
- inputs and outputs
- sequence of instructions
- repetition of instructions
- selection of instructions
what shares these four features
- inputs and outputs
- sequence of instructions
- repetition of instructions
- selection of instructions
algorithms
an algorithm will follow a sequence of instructions unless
1.
2.
- there is repetition in which case the algorithm repeats a set of instructions until the loop is broken
- there is selection. in which case the sequence of instructions will branch to different sequence of instructions and outcomes
name four input sources an algorithm might get its data from
- the user
- a constant unchangeable value written in the algorithm
- data from the current environment (current time, current mouse position)
- lists
what is a case instruction or a switch statement
this can be used in contrast to selection.
instead an input variable is assessed then if the variable exists as a case or switch then it has its block of code ran
switch (variable or an integer expression)
{
case constant:
//C Statements
;
case constant:
//C Statements
;
default:
//C Statements
;
}
this can be used in contrast to selection.
instead an input variable is assessed then if the variable exists as a case or switch then it has its block of code ran
switch (variable or an integer expression)
{
case constant:
//C Statements
;
case constant:
//C Statements
;
default:
//C Statements
;
}
case instruction/switch statement
what two ways can you judge if an algorithm is good or not
- readability - are its steps clearly laid out and self explanatory
- efficiency - is it written in its most efficient form. that is can it be re written to perform the same outcome quicker and with less effort
how can you tell if an algorithm has good readability
the steps will be clear and precise to all. this includes the author and any audience that uses it
name two ways you can increase the efficiency of an algorithm
- reduce the number of steps while still maintaining the desired outcome
- reduce the number of calculations while still maintaining the desired outcome
describe the three steps of the swapping algorithm
- set temp to item 2
- set item 2 to item 1
- set item 1 to temp
what does this algorithm do
- set temp to item 2
- set item 2 to item 1
- set item 1 to temp
swaps two items
describe a sorting algorithm
a sorting algorithm takes a list of unsorted items and then sorts the items by a given rule
takes a list of unsorted items and then sorts the items by a given rule
sorting algorithm
what rules might be applied to sort items in a list
1 - 4
- sort numbers in ascending/descending order
- sort words alphabetically in ascending/descending order
- sort by length of item in ascending/descending order
- sort by price in ascending/descending order
what are the three steps for the selection sort algorithm
repeat until (only 1 item of unsorted data remains)
- ——- find the lowest item in the unsorted data
- ——- swap the lowest item with the first item in the ———— unsorted data
what algorithm is this
repeat until (only 1 item of unsorted data remains)
- ——- find the lowest item in the unsorted data
- ——- swap the lowest item with the first item in the ———— unsorted data
selection sort algorithm
name two features of the selection sort algorithm
- always makes the same number of comparisons regardless of lists initial state sorted or unsorted
- has a non linear line on a graph. as the number of items to sort increases the number of comparisons grows faster
- always makes the same number of comparisons regardless of lists initial state sorted or unsorted
- has a non linear line on a graph. as the number of items to sort increases the number of comparisons grows faster
features of the
selection sort algorithm
describe a
not in place sort
this uses two lists two sort data
unsorted list - holds the initial unsorted data. is either emptied while being sorted or its state is left unchanged
sorted list - is initially empty but is filled with items from the unsorted list as the items are sorted
this uses two lists two sort data
unsorted list - holds the initial unsorted data. is either emptied while being sorted or its state is left unchanged
sorted list - is initially empty but is filled with items from the unsorted list as the items are sorted
not in place sort
describe an in place sort
uses only one list and upon sorting is abstracted into two lists. the unsorted items and the sorted items
pass 1 - the entire list is unsorted (1 list)
pass 2 - the list has 1 sorted item (2 lists)
pass 3 - the list has 2 sorted items (2 lists)
repeat until there is only one unsorted item (essentially 1 sorted list)
uses only one list and upon sorting is abstracted into two lists. the unsorted items and the sorted items
pass 1 - the entire list is unsorted (1 list)
pass 2 - the list has 1 sorted item (2 lists)
pass 3 - the list has 2 sorted items (2 lists)
repeat until there is only one unsorted item (essentially 1 sorted list)
in place sort
which of these two methods is more likely to be used
- in place sort
- not in place sort
an in place sort is more likely to be used as it is more elegant and efficient as items are contained within one list no extra memory is required
describe the bubble sort algorithm/sinking sort algorithm
this sorts items in a way that the sorted items will bubble or sink to either end of the list
the bubble sort algorithm contains a swapping pass describe what it does
looks at the first item in the list and compares it to the adjacent item if they are in the wrong order they are swapped. it then moves to the next item and repeats until there are no more adjacent items
the swapping pass sorts 1 item
what are the four steps in the swapping pass
starting at the beginning of the list
repeat for (each pair of adjacent items)
——– if items are in the wrong order then
—————- swap them
what is this
starting at the beginning of the list
repeat for (each pair of adjacent items)
——– if items are in the wrong order then
—————- swap them
bubble sort algorithms swapping pass
what are the 8 steps of the bubble sort algorithm written in its most efficient form
set flag to true
repeat until (flag is false)
—- set flag to false
—- starting at the beginning of the list
—- repeat for (each pair of adjacent items in the ————– unsorted portion)
——– if items are in wrong order then
———— swap them
———— set flag to true
what algorithm is this
set flag to true
repeat until (flag is false)
—- set flag to false
—- starting at the beginning of the list
—- repeat for (each pair of adjacent items in the ————– unsorted portion)
——– if items are in wrong order then
———— swap them
———— set flag to true
bubble sort algorithm
name two features of the bubble sort algorithm
- can stop sorting a sorted list after 1 iteration because of its use of a flag
- shares the same non linear line on a graph of selection sort when reverse sorting
- can stop sorting a sorted list after 1 iteration because of its use of a flag
- shares the same non linear line on a graph of selection sort when reverse sorting
features of the bubble sort algorithm
name 3 sorting algorithms
- selection sort
- bubble sort
- merge sort
