2.1 Algorithms Flashcards
(25 cards)
What is abstraction?
The process of removing unnecessary details and including only the relevant details.
Examples of abstraction are:
Flow charts, icons, satellite navigation (maps) and variables
What is decomposition?
The process of breaking down a complex problem into smaller, more manageable parts.
Examples of decomposition are:
The processes of crossing roads, game development and morning routines.
Advantages of decomposition are:
It makes problems easier to solve, development time is reduced and more than one part can be worked on at a time with multiple people.
What is an input?
Anything that needs to be supplied to the program, often inputted by the user.
What is a process?
The consideration of what calculations need to be performed while the program is running.
What is an output?
The result of the program after the processes, the final answer.
How are structure diagrams used?
They are used to illustrate decomposition using step-wise refinement.
They can also be used by developers to understand the problems they need to code and share with the users during systems analysis.
What is algorithmic thinking?
A way of getting to a solution by identifying the individual steps needed.
How does algorithmic thinking work?
- Breaks the problem down.
- Sort the data that is + isn’t important.
- Think of relevant data structures.
- Tackle each part of the problem step by step.
What is a linear search?
When starting from the beginning of a data set, each item is checked in turn to see if it is the one being searched for.
Characteristics of a linear search are:
- Doesn’t require the data set to be in order.
- Will work on any type of storage device.
- Can be efficient for smaller data sets.
- Very inefficient for large data sets.
How does a binary search work?
- The mid-point of the data set is found (left + right // 2)
- Check if that’s the item to be found.
- If not + the item to be found is lower than the mid-point:
repeat on the left half of the data set. - If not + the item to be found is greater than the mid-point:
repeat on the right half of the data set. - Repeat until the item is found or there are no items left to check.
Characteristics of a binary search are:
It requires the data set to be in order of a key field + is more efficient than a linear search (on average).
Characteristics of a bubble sort:
- Sorts an unordered list of items.
- Compares each item with the next one and swaps them if the are out of order.
- Algorithm finishes when no more swaps need to be made
- Most inefficient of the sorting algorithms, but the easiest to implement.
- Popular choice for small data sets.
Characteristics of a merge sort:
- Efficient sorting method
- Divide and conquer method
- Creates two or more identical sub problems from the largest problem to solve them individually
- Combines the solutions to solve the bigger problem
- Data is halved repeatedly until each item is in its own list
-Adjacent lists merged back together - Works very well for large data sets
Characteristics of an insertion sort:
- Inserts each item into its correct position in a dataset one at a time
- Useful algorithm for small data sets
- Particularly useful for inserting items into an already sorted list
- Usually replaced by more efficient sorting algorithms for large data sets
How do trace tables help program creation?
- Help to understand program flow
- Testing accuracy of an algorithm
- Examination of a printed program code and running through the
program one line at a time - Written out to follow the current state of the variable
- Any produced output written down
- Variables have their own columns
- New row for any variable state changes
- Excellent to track down logic errors
Example of a trace table:
number = print(“Enter a number”)
total = 1
for counter = 1 to number
total = total * counter
next counter
output(total)
|number|counter|total|
| 5 | 1 | 1 |
| | 2 | 1 |
| | 3 | 2 |
| | 4 | 6 |
| | 5 | 24 |
| | 6 |120 |
What are flowcharts?
A sequence of steps representation in the form of a diagram.
What are all the pieces and their shapes of a flowchart?
Terminal = pill shape
Process = rectangle
In/output = Parallelogram
Subroutine = rectangles with ends sectioned off
Decision = Diamond
Line = arrowed line
What is pseudocode?
Text based alternative sequence of steps representation that is a simplified form of programming code.
A method to “lay down the logic” of a problem without rules of the programming language.
What is a syntax error?
An error that breaks grammatical rules of the programming language and stop the code from running/translation.
