2.1 Flashcards
what is abstraction
the process of removing unnecesary details ad only including relevant details
what is decomposition
breaking down complex tasks into smaller manageable tasks
advantages of abstraction
allows the focus of what is important in problem solving
advantages of decomposition
makes tasks easier to manage
different people can work on different tasks at the same time, reducing time
program components can be easily used in other components
what is algorithmic thinking
a way of getting to a solution by identifying the individual steps needed
what is an input
anything which needs to be supplied to the program to meet its goals
what is usually created for an input
an appropriate variable name and data type
how does algorithmic thinking work
- it creates sets of rules, an algorithm that follows it precisely leads to its solution
- for example, algorithms for doing multiplications will work 100% of the time if you follow the rules to get the result
how are structure diagrams created
- they are produced using the method, step-wise refinement
- the problem is broken down using decomposition into smaller components (some problems will need more decomposition than others)
- the lowest level nodes should achieve a single task
- these can then be coded as a single or sub-program
what do outputs do
they consider what the program needs to output
consider what form this output needs to take
consider an appropriate variable name and data type for any output
what is a structure diagram
it is a method of designing a solution to a problem by illustrating the problem using decomposition
what is pseudocode
an alternate text-based way of representing the sequence of steps in an algorithm
advantages of using pseudocode
it allows us to lay down the logic of a problem without worrying about rules of syntax
what is the terminal symbol (oval shaped) in a flow diagram
shows the start or end of a process
what is the process symbol (rectangular shaped) in a flow diagram
shows that something is initialised, processed or calculated
what is the decision symbol (diamond shaped) in a flow diagram
shows yes or no, true or false
what is the input/output symbol (rhombus shaped) in a flow diagram
shows an input and output of data to the algorithm
what is the subroutine symbol (rectangle with stripes) in a flow diagram
it is used to call a subroutine (separate function)
what is the line in a flow diagram
controls passing between connected shapes
name the different types of errors
- syntax errors, which are grammatical rules of programming language
- they stop code from being translated
- logic errors, which produce unexpected outputs
- on their own they will not stop programs from running
what is tracing execution
- used for testing the accuracy of an algorithm for logic
- it involves examining a printed extract of program code and running through the program
what is a trace table
- used for noting down any output the program produces
- each variable present in the program should have its own column in the trace table
- a new row should be added under any column if the state of a variable changes
advantages of trace tables
they are a good way to track down logic errors in a problem
how does binary search work
- calculate a midpoint in the data set
- check if that is the item to be found
- if not…
- if the item to be found is lower than the midpoint, repeat on the left half of the data set
- repeat until the item is found or there are no items left to check
- requires the data set to be in order of a key field
advantages of binary search
more efficient than a linear search on average
what is linear search
- starting from the beginning of a data set, each item is checked in turn to see if it is the one being searched for
advantages of linear search
- does not require the data set to be in order
- will work on any type of storage device
- can be efficient for smaller data sets
disadvantages of linear search
inefficient for larger sets of data
what is bubble sort
it sorts an unordered list of items
how does bubble sort work
- it compares each item with the next one and swaps them if they are out of order
- the algorithm finishes when no more swaps need to be made
- in effect it “bubbles” up the largest or smallest item to the end of the list in successive passes
advantages of bubble sort
- it is the most inefficient of the sorting algorithms but is very easy to implement
- this makes it a popular choice for very small data sets
what is merge sort
uses division and creation of lists within lists to sort a list
how does merge sort work
creates two or more identical variables from the original list, and solves them individually by merging separate lists in the correct order
advantages of merge sort
- very efficient method of performing a sort
- works well with larger data sets
what is insertion sort
a sort similar to bubble sort except each variable is sorted into its correct data position one at a time
advantages of insertion sort
- it is useful for small data sets
- it is useful for inserting items into already sorted lists
disadvantages of insertion sort
- usually replaced by more efficient sorting algorithms for larger data sets
