unit 1 - fundamentals of algorithms Flashcards
what is an algorithm?
a set of instructions for solving a problem or completing a task
what is abstraction?
removing unnecessary detail from a problem so that you can focus on the essentials
what is decomposition
breaking down a large problem into smaller sub-tasks, which can then be further broken down until each small task is manage
arithmetic operators
+ add
- subtract
/ divide
* multiply
^ exponent
MOD division with a remainder
DIV integer division
what is a variable?
is a location in memory where you can temporarily store text or numbers
what are two tools to plan and write algorithms?
- pseudocode
- flowcharts
what are the three programming constructs?
- sequence
- selection
- iteration
data types
integer - a whole number
real - a number with a decimal point
boolean - can only be TRUE or FALSE
character - a single alphabetic or numeric character
- string - one or more characters enclosed in quote marks
boolean operators
> greater than
< less than
= greater than or equal to
<= less than or equal to
= equal (== in python)
/= not equal (!= in python)
what is sequence?
the statements are executed in the order that they are written
what is selection?
- an IF statement in a selection statement
- the next statement to be executed depends on whether the condition tested is TRUE or FALSE
what is pseudocode?
- a structured english for describing algorithms
- allows the designer to focus on the logic on the algorithm without being distracted by the syntax
how to assign a value to a variable in pseudocode?
total <- 0
cost <- adult * child
counter <- counter + 1
how to write an input/output in pseudocode?
firstname <- USERINPUT
OUTPUT (“enter a value”)
what does iteration mean?
- repetition of a certain block of code
what are the three different types of iteration statements?
- FOR…ENDFOR
- WHILE…ENDWHILE
- REPEAT…UNTIL
what is the FOR…ENDFOR loop used for?
when you want to execute the loop a specific number of times
what is the WHILE…ENDWHILE loop used for?
when you want to execute the loop while a certain condition is true
the condition is checked at the start of the loop
what is the REPEAT…UNTIL loop used for?
- when you want to execute the loop until a certain condition is true
- the condition is tested at the end of the loop
- usually has an IF statement to test the condition at the end
what is a flowchart?
means of defining an algorithm using shapes and arrows. each shape has a specific meaning that corresponds to an action/decision
flowchart shapes and what they signify
tablet > marks the start and end of the code
diamond > a decision (asks if a condition is true or not)
parallelogram > input/outputs
rectangle/box > process (each contains a single instruction)
what is a trace table?
a table used to keep track of variables that change throughout the algorithm
what is searching?
determining whether a specific item of data exists within a data structure
what is a linear search?
a search algorithm that begins at one end of the data and checks each item methodically if and until the required item is found or the end of the structure is reached
what are the two types of search algorithms?
- linear search
- binary search
what is binary search?
a search algorithm that begins in the middle of the data structure and eliminates half the structure with each pass
- the data must be sorted in ascending order before the search can take place
linear search vs binary search
linear search:
+ functions on unsorted data
- is more time consuming than a binary search
- only really works on smaller data structures
binary:
+ far more time efficient
- data has to be sorted first
what is sorting?
putting the data into order (ascending or descending)
what is bubble sort?
- each item in a list is compared to the one next to it, and if it is greater then they swap places
- the initial pass doesn’t do anything
- at the end of the first pass through the list, the largest item is at the end of the list
- this is repeated until the items have been sorted
what is merge sort?
- divide the unsorted list into n sublists, each containing one element
- repeatedly merge two sublists at a time to produce new sorted sublists until there is only one sublist remaining - the sorted list
bubble sort vs merge sort
bubble sort:
+ straightforward to program
+ doesn’t use much extra memory space whilst the sort is in progress
- often slow and inefficient compared to merge sort
- cannot sort long data structures
merge sort:
+ much more efficient in terms of time
- more complex to program
- requires a lot of memory space whilst it runs (quite bad with large data structures)
