Standard algorithms – FA Software Development

Within programming texts, you might encounter the word Algorithm. An algorithm is just a list of rules or processes to follow to solve a problem or complete a task. You could make an algorithm describing the steps you take to leave the house and go shopping. You have written algorithms to solve any of the assignments that’ve you’ve done to date on the course.

Some tasks have been used so often in computing that they are now referred to as Standard Algorithms. Most computing languages will have built in functions that you can use to carry out these tasks, but you will also be asked in exams to either explain or code one or more of these standard algorithms. This is to show that you understand the logical steps involved.

Some standard algorithms might be problems such as finding if a value appears in a list (linear search), finding the minimum or maximum value in a list, or counting how many times a value appears in a list.

Keep in mind that the code below is not the only way to do it, so learn to look for the steps within any code you are reading to see if you can spot a standard algorithm.

Linear search

Searches through a list to look for a given value.

# Linear Search Example

list_to_search = ["cat", "dog", "rabbit", "sheep", "cow", "pig"]
length_of_list = len(list_to_search)
value_to_look_for = "lion"
found_value = False

for counter in range(length_of_list):
    if value_to_look_for == list_to_search[counter]:
        print(value_to_look_for + " was in the list at position " + str(counter))
        found_value = True
        break

if not found_value:
    print(value_to_look_for + " was not in the list")

The steps to do a linear search are:

Loop through the list of values to search
If the current value matches the value you are searching for then stop searching and notify the user that it was found. Depending on the requirement of the program you can also state the location in the list the match was found

Binary search

If you are looking through a list of numeric values and the list of values has been sorted then you can use a binary search which is more efficient than a linear search. A binary search looks at the half way point of a list of sorted values and checks if the value it is looking for is higher or lower than the mid point. You then split the list in half and discard the unwanted half then repeat the test.

A linear search can be faster if the result you are looking for is near the start of the list. But a binary search is faster for larger lists as you keep halving the size of the list you need to check.

list_of_numbers = [9, 10, 21, 32, 93, 342, 542]
value_to_find = 342
value_found = False
length_of_list = len(list_of_numbers)
lower_limit = 0
upper_limit = length_of_list
print("Looking for: " + str(value_to_find))

while (value_found == False) and (lower_limit != upper_limit):
     midpoint = int((upper_limit + lower_limit) / 2)
     if list_of_numbers[midpoint] == value_to_find:
          print("Found at list index: " + str(midpoint))
          value_found = True
     else:
          if list_of_numbers[midpoint] > value_to_find:
               upper_limit = midpoint - 1
          else:
               lower_limit = midpoint + 1

if value_found == False:
    print("Not found")

The steps for a binary search are:

Work out the lower and upper limits of the list indexes.
Work out the half way point of the list of ordered values
Is this value the one you are looking for? If so stop searching.
If not check if it is higher or lower than the half way point value.
If lower then set the new upper limit to the old half way point minus 1.
If higher then set the lower limit to the old half way point plus one.
Repeat from step 3 until the value is found or you have searched the whole list.

Find maximum

Finds the largest value in a list of values.

# Find Maximum Example
list_of_numbers = [93, 21, 9, 342, 542, 10, 32]
length_of_list = len(list_of_numbers)

for counter in range(length_of_list):
    if counter == 0:
        maximum_value = list_of_numbers[counter]
    else:
        if list_of_numbers[counter] > maximum_value:
            maximum_value = list_of_numbers[counter]

print("The maximum value was: " + str(maximum_value))

The steps to find the maximum are:

Loop through the list of values
If it is the very first entry then set that to the maximum, otherwise compare it to the maximum
If the current value is greater than the maximum then update the maximum to the current value

Find minimum

Find the smallest value in a list of values.

# Find Minimum Example
list_of_numbers = [93, 21, 9, 342, 542, 10, 32]
length_of_list = len(list_of_numbers)

for counter in range(length_of_list):
    if counter == 0:
        minimum_value = list_of_numbers[counter]
    else:
        if list_of_numbers[counter] < minimum_value:
            minimum_value = list_of_numbers[counter]

print("The minimum value was: " + str(minimum_value))

The steps for a find the minimum are:

Loop through the list of values
If it is the very first entry then set that to the minimum, otherwise compare it to the minimum.
If the current value is less that the minimum then update the minimum to the current value.

Count occurrence

Keep a count of how many times a value appears in a list of values.

# Count Occurrences Example

list_to_search = ["A", "B", "A", "C", "C", "A", "D", "C", "A"]
value_to_look_for = "A"
count_occurences = 0

for current_list_entry in list_to_search:
    if value_to_look_for == current_list_entry:
        count_occurences += 1

print(value_to_look_for + " was in the list " + str(count_occurences) + " times")

The steps in a count occurrences example are:

Initialise a variable to store the number of matches found to 0.
Loop through the list of values.
If the current value matches the value that you are searching for then incremented the number of matches found by 1.
Once you have gone through all entries in the list, display the number of matches found.

Next: Challenge 6