Algorithms Flashcards
What is an algorithm?
A series of steps to solve a given problem
What is algorithmic thinking?
A way of solving problems by producing algorithms
Writing down an algorithm
Can be written as a set of numbered steps to follow
What is often used to represent algorithms?
Pseudocode or flow diagrams
How do you interpret an algorithm?
Identify what the algorithm does
What is a search algorithm?
A set of instructions for finding a specific item of data within a data set
What is an effective search?
A search that will either find the solution or determine that the target data is not present
What is an efficient search?
Will find the solution quickly regardless of its location within the data set
What are examples of search algorithms?
1) linear search 2) Binary search
What is linear search?
A simple searching algorithm
What is the concept of linear search?
If you were looking for a specific piece of paper in a stack of papers, then one way to find it would be to work from the top of the stack to the bottom, checking each paper on the way.
Linear search -
1) Check the first item in the dataset:
- if it is what we are looking for, return it
2) Check the second item in the dataset:
- if it is what we are looking for, return it
3) Continue for the rest of the items
What does it mean when you reach the end of the dataset in linear search?
The item was not in the data set
Linear search pseudocode example =
for item in dataset
if item = target then
return True
endif
endfor
return FalseWhat are the pros of linear search?
Very easy to implement
What are the cons of linear search?
Slow on a longer list
What is binary search?
A divide and conquer algorithm
What is the concept of binary search?
If you try to find a certain page in a book, it’s unlikely that you check every page on the way
- you are more likely to split the book in 2 then see if the page you need is before or after the split & repeat
Binary search -
1) Find the middle of the dataset
- if the middle value is greater than the target then:
- - repeat on first half of dataset
2) If the middle value is lesser than the target then:
- repeat on second half of dataset
3) If the middle value is the target:
- We found it
4) Stop repeating once the size of our dataset is zero
Binary search pseudocode example =
dataset = [...] min = 0; max = len(dataset)
while (min target then max = midpt - 1 else if dataset+ [midpt] < target then min = midpt + 1 endif endwhile return False
What are the pros of binary search?
Faster than linear search on a large dataset
What are the cons of binary search?
Dataset must be sorted before starting
What are the 3 basic constructs when needed to design an algorithm?
Iteration, Selection & Sequence
