2.1 Algorithms Flashcards
Principles of Computational Thinking
- Abstraction
- Decomposition
- Algorithmic thinking
Abstraction
The process of removing all unnecessary details and including only the most relevant details.
Decomposition
Breaking down a complex problem into smaller, more manageable parts.
Algorithmic thinking
A way of getting to a solution by identifying the individual steps needed.
Inputs
Anything that needs to be supplied to the program to meet its goals.
Processes
Which calculations must be performed while the program is running.
Outputs
What your program needs to output.
Types of Errors
- Syntax errors
- Logic errors
Syntax Errors
Errors that break the grammatical rules of a programming language and stop it from running.
Logic Errors
Errors that produce an unexpected output, however the program still runs.
Structure Diagrams
Help to illustrate problem decomposition. They use ‘Step Wise Refinement’
Each node should achieve a single task which can then be coded as a subprogram
Trace Tables
Take each line at a time and write out the state of each variable.
Flow Charts
A method of representing the sequence of steps in an algorithm in the form of a diagram.
→
Represents flow from one component to the next.
▭
Process
E.g. Input
▱
Input/output
◧◨
Subroutine
⍚
Decision
E.g. IF/ELSE
▢
Start/stop. Terminator.
Types of Searches
- Binary search
- Linear search
Binary Search
- Calculate the midpoint of data set.
- Check if that is the desired item
IF desired item is lower than midpoint… - Repeat on left half data set
IF desired item is higher than midpoint… - Repeat on right side of data set
- Repeat until item is found.
Characteristics of Binary Search
- Required data set to be ordered
- More efficient than linear search
Linear Search
Starting from the beginning of a data set, each item is checked against to see if it is the desired item.
Characteristics of Linear Search
- Will work on any storage device
- Efficient for smaller data sets, not large ones.
Types of Sorts
- Bubble sort
- Merge sort
- Insertion sort
Bubble Sort
Compares each item with the next and swaps them if they are out of order.
Algorithm ends when there are no more swaps.
Characteristics of Bubble sort
- Sorts an unordered list of items.
- Most inefficient
- Easy to implement
- Popular for small data sets
Merge Sort
Divide and Conquer method.
Creates two or more identical sub-problems from the largest problem and solves them individually, then combines their solutions to solve the large problem.
Characteristics of Merge Sort
- Very efficient
- Works well for large data sets
Insertion Sort
Inserts each item into its correct position in a data set.
Characteristics of Insertion Sort
- Useful for inserting items into an already sorted list.
- Good for small data sets
- Not good for large data sets
Pseudocode
A simple way of describing a set of instructions in a manner that resembles a programming language.
Advantages of Pseudocode
- Can be quickly and easily converted into an actual programming language.
- Easy to understand
- Changes to the design can be incorporated easily
Disadvantages of Pseudocode
- Can be hard to see how a program flows
- Time consuming.
