Flowcharts Searching Algorithms Trace Tables

• Created to represent an algorithm. Linear Search • Tests algorithms for logic errors which
• Show the data that is input, and output. 1. Check the first value occur when the algorithm is executed.
• Show processes that take place. 2. If it is desired value • Simulates the steps of algorithm.
• Show any decisions and repetitions that take place. - Stop • Each stage is executed one at a time
• Lines show flow through the chart. 3. Otherwise check the second value allowing inputs, outputs, variables, and
• Shapes represent different functions 4. Keep Going until all elements have been checked processes to be checked for the correct
or the value is found value at each stage.
Binary Search
Start or End Process 1) Put the list in order. Stage X Y Output
2) Take the middle value. 1 3 1
3) Compare it to the desired value. X = 3
2 2
Input or a) If it is the desired value. Y = 1
YES 3 2
Decision i) Stop. while X > 0
Output 4 3
b) If it is larger than the desired value. Y = Y + 1
X = X - 1 5 1
i) Take the list to the left of the middle value. 6 4
Subprogram NO c) If it is smaller than the desired value. print(Y)
7 0
i) Take the list to the right of the middle
8 4
value.
4) Repeat step 3 with the new list.

Unit 1 – Fundamentals of Algorithms

Key Terms Sorting Algorithms Algorithm Efficiency Pseudocode
• Abstraction Bubble Sort • Several different algorithms can • Uses short English words and
- Using symbols and variables. to represent a real- 1) Take the first element and second element solve the same problem statements to describe an
world problem with a computer program. 2) Compare the two • Efficiency allows us to compare two algorithm.
- Removing unnecessary elements a) If element 1 > element 2 different algorithms that solve the • Generally looks a little more
- Example - a program is to be created to let users i) Swap then same problem. structured than normal English
play chess against the computer. b) Otherwise • A more efficient algorithm is a better sentences.
▪ Board is created as an array(s). i) Do nothing choice. • Flexible.
▪ Pieces are objects that have positions on the c) Move to the next pair in the list • The quicker the algorithm can • Less precise than a programming
board d) If there are no more elements return to step (1) complete its task, the more efficient language.
▪ The shape and style of the pieces may not be e) Otherwise, return to step (2) it is.
required. 3) Repeat until you have worked through the whole list without making any • For example, an algorithm that can IF Age is equal to 14 THEN
changes be executed in 10 instructions, is Stand up
• Decomposition more efficient than one which takes ELSE Age is equal to 15 THEN
- Breaking down large problems into a set of smaller Merge Sort 25 instructions. Clap
parts. 1) Split the list into individual elements. ElSE Age is equal to 16 THEN
▪ Smaller problems are easier to solve 2) Merge the elements together in pairs, putting the smallest element first. Sing a song
▪ Each part can be solved independently 3) Merge two pairs together, putting the smallest first. Determining The Purpose of ELSE
▪ Each part can be tested independently 4) Keep merging until all pairs are in order. Algorithms Sit on the floor
▪ The parts are combined to produce the full • There are several ways to determine END
problem. the purpose of an algorithm.
- There are usually several different approaches, and Comparing Algorithms • We can dry run the algorithm, by
An Example Algorithm
not one single right way to do this. assigning values to its inputs, and
Linear Search Binary Search This algorithm, written in
working through to see what
pseudocode, follows a simple pattern
Pros • Works with unsorted lists • More efficient happens.
for working through each letter of an
• Not affected by changes to the list • Efficient for large lists • Trace Tables allow us to record
What is an Algorithm input to determine if it matches a
• Works well for small lists these values as the algorithm is run.
• An algorithm is a series of steps which can be followed predefined word. This might form part
• Visual Inspection involves simply of a hangman game
to complete a task. Cons • Slower • Does not work with unsorted looking at the algorithm to determine
• A computer program may use an algorithm. • Inefficient for large lists lists its purpose. guess ← USERINPUT
• A computer program and an algorithm are not the
• Sometimes the algorithm may follow FOR i ← 0 TO LEN(word)
same thing. Bubble Sort Merge Sort
a standard pattern which we can IF word[i] = guess THEN
• Algorithms help to work out the steps needed to solve Pros • Simplest and easiest to code • Far more efficient and faster recognise.
a given problem. • Uses less memory • Consistent running time OUTPUT “found”
• With shorter or simpler algorithms, ENDIF
• This helps us plan how to write a computer program. the purpose may be obvious by
• An algorithm will always finish and return an answer or Cons • Slower with larger lists • Uses more memory ENDFOR
• Inefficient and slow • More complexed to program simply looking at it.
perform a series of tasks that it was supposed to.