Unit 6 - Algorithms Flashcards
What is an algorithm?
Computational thinking
An algorithm is a set of instructions for solving a problem or completing a task
What is abstraction?
Computational thinking
Abstraction involves removing unnecessary detail from a problem so that you can focus on the essential components
What is decomposition?
Computational thinking
Decomposition involves breaking down a large problem into smaller, more manageablesub-problems
What are advantages of decompostition?
Computational thinking
- The problem becomes easier to solve when it consists of a number of small subtasks
- Some may be reusable, saving development time
What are the 2 types of searching algorithms?
Searching algorithms
- Binary search
- Linear search
What is a linear search?
Searching algorithms
A linear search requires going through each item in the list, one by one
How does a binary search work?
Searching algorithms
Mark Scheme answer
- Select middle number and ..
- check if selected number matches target number
- if searched number is larger, discard left half // if searched number is smaller, discard right half
- Repeat until number found
What are the 3 sorting algorithms?
Sorting algorithms
- Bubble sort
- Merge sort
- Insertion sort
How does bubble sort work?
Sorting algorithms
- Start with the leftmost item
- Compare it with the one next to it
- If the one next to it is less, swap them
- Repeat for all the other items
- At the end of one pass through the list, the largest item is at the end of the list
- Repeat the process until the items are sorted
How does insertion sort work?
- This algorithm sorts one data item at a time
- One item is taken from the list, and placed in the correct position
- This is repeated until there are no more unsorted items in the list
How does merge sort work?
Sorting algorithms
Which sorting algorithm is fastest?
Sorting algorithms
The Insertion sort is much quicker than the Bubble sort, but the Merge sort is faster still
What is a variable?
Developing algorithms
A variable is a location in memory in which you can temporarily store a value such as a string or number
What are the 2 common tools to write an algorithm?
Developing algorithms
- Flowcharts
- Pseudocode
What are the 3 basic program stuctures?
Developing algorithms
- Sequence
- selection
- Iterarion
What is a sequence?
Developing algorithms
A sequence is a series of steps which are completed one after the other
What is selection?
Developing algorithms
Selection is the ability to choose different paths through a program
What is iteration?
Developing algorithms
Iteration means repeating a part of a program (repeating or looping)
How is a terminal represented?
Flowcharts
A curved rectangle for start + end
How is an input/output represented?
Flowcharts
A parallelogram
How is a decision repesented?
Flowcharts
A diamond with arrows for different choices
How is the direction of flow represented?
Flowcharts
An arrow line
How is a process represented?
Flowcharts
A rectangle
How is a subroutine represented?
Flowcharts
A rectangle with lines o each end
