Unit 7:
Algorithm Design and Problem Solving
Embedded Files
Unit 7 Curriculum
Unit 7 Curriculum
Unit 7.pdfKey Takeaways:
Key Takeaways:
Linear search checks each item in order one at a time
Linear search does not need to be sorted
binary search needs to be sorted
binary search uses a divide and conquer method
sorted means in order (alphabetical, numerical etc)
every computer system consists of 4 elements; inputs, outputs, processing and storage
decomposition is the process of breaking down a big problem in to smaller more manageable problems
flowcharts have 4 commonly used shapes to represent start/stop, input/output, process, decisions
flowcharts are used to visually represent and map an algorithm
pseudocode is mix of programming language and written language
pseudocode is used to plan a program
algorithms are step by step instructions used to complete a task
Program Development Lifecycle
Program Development Lifecycle
Flowcharts
Flowcharts
Pseudocode
Pseudocode
Coding
Coding
Testing
Testing
Algorithms
Algorithms
Computers can hold a lot of information, but that information is only useful if we can find it easily. There are many ways that a computer can search for information, two of the most common methods are by searching and sorting.
Search Algorithms
Search Algorithms
Linear Search
Linear Search
The first search algorithm that we need to know about is called a linear search. This is the most common way that humans would search for something, we start at the beginning and check each item until we have either found what we are looking for, or reached the end - like starting at one end of a book shelf and looking at each book one book at a time for a particular book.
The list of items does not need to be in order (the books can be randomly placed on the shelf).
In a program you may need to look for a specific value in a set of data. A linear search will check each item in the data set one at a time until it either finds it or reaches the end of the data set without finding it.
This algorithm works just fine, think about how long it might take to run. Imagine looking for a book on one shelf and then imagine looking for a book in a university or national library.
Python Linear Search example:
Python Linear Search example:
Binary Search
Binary Search
Binary Search
Binary Search
Obviously, there are faster and more efficient ways of searching than just starting at the beginning and checking every item until you find it (as in the linear search above)
If the list of items to be found are in order, then we can use binary search. Binary search is also referred to as a divide and conquer algorithm, here's why ...
The algorithm start by checking the item right in the middle of the list.
If the item you are looking for is in the middle then yay - if not ....
The algorithm then compares the number you are looking for with the number in the middle
if the number in the middle is bigger than the one you are looking for, the algorithm discards all the numbers that are less than and equal to the value of the middle number.
if however the middle is smaller than the one you are looking for, the algorithm discards all the numbers that are greater than and equal to the value of the middle number.
So the number of items you are searching through has halved
The algorithm then repeats these steps until the item is found or the algorithm finds that the item is not in the list at all.
This search is called a binary search because we split the list in two each time. It is usually much faster than a linear search.
Python binary search example:
Python binary search example:
Sorting Algorithms
Sorting Algorithms
As well as searching for an item in a list, it is very common for us to be able to sort a list of items into a particular order. One of the simplest ways to do this is the bubble sort.
One of the most important jobs a computer performs for us is sorting of data. Without sorted data our computer systems would be much harder to use
Imagine:
trying to read through all your emails if they were in a random date order.
finding a friend’s telephone number if all you contacts were in a random order.
loading an app from your apps list if they were all jumbled up.
There are many different ordering systems we can use, common ones include:
alphabetical order
numerical order
date order
size order
Different sorting algorithms
There are many different algorithms(methods) for sorting lists of things one is called bubble sort.
The bubble sort algorithm works by sorting through the array in pairs. It starts at the left of the array and inspects the first two items.
If the items are in the wrong order they are swapped around. The algorithm then carries on with the next pair along and so forth. When it reaches the end of the array it goes back to the beginning of the array and starts again.
If it completes a full pass of the array without swapping any items it knows that the array is sorted.
Python Bubble sort example
Python Bubble sort example
Trace Tables
Trace Tables
Trace tables are used when performing a dry-run of an algorithm.
This could be an algorithm expressed as a flowchart or pseudocode.
Trace tables record the outputs for a given set of data, allowing the user to compare these to the expected results.
Trace tables also show the values of variables at each stage of the algorithm.
This information helps to identify errors and issues with logic.
If you are unsure of the purpose of an algorithm, trace tables can help with that too.
The documented nature of a trace table should make performing your dry-run easier with less chances of making a mistake.
Error Detection
Error Detection
Types of error detection
Types of error detection
range check - Checks that data falls within a specified range eg. between 1 and 100
length check – Checks that the data entered is the correct length eg. passwords must be at lest 8 characters long
type check – Checks that the data entered is the right type eg. first names contain only letters
presence check – Checks that data has been entered into the data box eg. when a user is forced to enter data into a field
format check – CHecks that data entered is in the correct format eg an email address contains an @ sign or the date is dd/mm/yyyy
check digit - Checks is a digit added to a string of numbers for error detection purposes
Can you answer the following?
Can you answer the following?
Can you draw and identify the 4 main shapes used in flowcharts?
Convert the following algorithm into a flowchart: Start, Input x, Input y, Is x > y, Stop
Describe the purpose of pseudocode
What do you record in a tracetable?
Why would you change the data in a tracetable?
Page updated
Google Sites
Report abuse