2.1 Algorithms Flashcards
Computational Thinking
Breaking down a problem into manageable steps and developing into an algorithm to solve with.
Abstraction
Filtering out the characteristics of a problem that are not needed in order to concentrate on those that are needed.
Decomposition
Breaking down a large problem into smaller sub-problems.
Algorithmic thinking
Identifying the steps involved in solving a problem.
Linear Search
Each item in the list is checked and parsed through in order.
Binary search
An ordered list is divided into two parts with each comparison.
Bubble Sort
Moving through a list repeatedly , swapping elements that are in the wrong order.
Merge sort
A list is splint into smaller lists (2 elements ) and then are combined and ordered.
List
A collection of data with a single identifier.
Insertion Sort
Each item takes it turns , compare to the items in a sorted list and placed in the correct position.
Algorithm
The series of steps to solve a problem or perform an action.
Flowchart
A diagram that shows the inputs, outputs and processes in an algorithm.
Process
An action that takes place .
Pseudocode
Simplified programming code that is not language specific , used to design algorithms.
Trace Table
A table that follows the values of a variable to check for accuracy.
What is the symbol for a process ?
Rectangle = An action
What is the symbol for a subroutine ?
Rectangle + bars
What is the symbol for an Input/Output ?
Parallelogram
What is the symbol for a decision ?
Diamond
What is the symbol for a terminator ?
Oval = start/stop
What are the two types of error ?
- Syntax
- Logic
What is a syntax error ?
code written does not follow the grammatical and format rules of the programming language
What is a logic error ?
error in the way a program works
How does a binary search work ?
- set the counter to middle pos of list
- value = match means the search ends
- if midpoint value is < value , list split in 2 and bottom half ignored
-if midpoint value > value , list split in 2 and top half ignored - Repeat until value is found
How does a linear search work ?
-each item of data is examined until a match is made.
-Once the item is found, the search ends.
What does a binary search require ?
An ordered list
Do values in list have to be ordered to perform linear search ?
NO
How does a bubble sort work ?
- Start at the beginning of the list
- Compare first and second value , swap
- Repeat until no more items to compare
How does a merge sort work ?
- List is divided into individual elements bu
splitting into two until elements are singular
-Pairs of elements compared , placed into order and combined until list becomes one
How does an insertion sort work ?
- Compares values in turn, start with 2nd value
- the greater value shifts to the right and repeats
