x is evenAppendix C — Algorithms
|
|
C.1 A taste of algorithm
An informal definition of an algorithm is:
Algorithm: a step-by-step method for solving a problem or doing a task.
In this definition, an algorithm is independent of the computer system. More specifically, we should also note that the algorithm accepts input data and creates output data
Let us elaborate on this simple definition with an example. We want to develop an algorithm for finding the largest integer among a list of positive integers. It is obvious that finding the largest integer among many integers is a task that cannot be done in one step. The algorithm needs to test each integer one by one.
To solve this problem, we need an intuitive approach. First use a small number of integers (for example, five), then extend the solution to any number of integers. Assume that the algorithm handles the integers one by one. It looks at the first integer without knowing the values of the remaining integers. After it handles the first one, it looks at the second integer, and so on.
The above figure does not show what should be done in each step. We can modify the figure to show more details.
There are two problems for the above figure to become an algorithm that can be programmed. First, the action in the first step is different than those for the other steps. Second, the wording is not the same in steps 2 to 5. The reason that the first step is different than the other steps is because Largest is not initialized! If we initialize Largest to \(-∞\), then the first step can be the same as the other steps!
Is it possible to generalize the algorithm? We want to find the largest of n positive integers, where n can be 1000, 1000000, or more. We can tell the computer to repeat the steps n times!
C.2 Algorithm representations
Computer scientists have defined three constructs for a structured program or algorithm. The idea is that a program must be made of a combination of only these three constructs: sequence, decision, and repetition.
It has been proven there is no need for any other constructs!
C.2.1 Example 1: Write an algorithm that finds the sum of two integers.
This is a simple problem that can be solved using only the sequence construct. Note also that we name the algorithm, define the input to the algorithm and, at the end, we use a return instruction to return the sum
C.2.2 Example 2: Write an algorithm to change a numeric grade to a pass/no pass grade.
This problem cannot be solved with only the sequence construct. We also need the decision construct. The computer is given an integer between 0 and 100. It returns ‘pass’ if the integer is greater than or equal to 70, and returns ‘no pass’ if the integer is less than 60.
C.2.3 Example 3: Write an algorithm to find the largest of a set of integers. We do not know the number of integers.
We use the concept before to write an algorithm for this problem
C.2.4 Exercise 1: Write an algorithm to find the smallest of the first 5 integers in a set of integers.
Here we need a counter to count the number of integers.
def FindSmallest(ilist):
"""
Parameters
----------
ilist: list
The input list that contains integers
Returns
-------
largest : int
The smallest integer of the first 5 integers in the list
"""
# Your code here
smallest = math.inf
if len(ilist) != 0:
counter = 0
while(counter<5):
if ilist[counter] < smallest:
smallest = ilist[counter]
counter = counter +1
return smallestC.3 A more formal definition
Now that we have discussed the concept of an algorithm and shown its representation, here is a more formal definition.
Algorithm: An ordered set of unambiguous steps that produces a result and terminates in a finite time.
- Well-Defined: An algorithm must be a well-defined, ordered set of instructions.
- Unambiguous steps: Each step in an algorithm must be clearly and unambiguously defined. If one step is to add two integers, we must define both ‘integers’ as well as the ‘add’ operation
- Produce a result: An algorithm must produce a result, otherwise it is useless. The result can be data returned to the calling algorithm, or some other effect (for example, printing).
- Terminate in a finite time: An algorithm must terminate (halt). If it does not (that is, it has an infinite loop), we have not created an algorithm.
C.4 Basic algorithms
Several algorithms are used in computer science so prevalently that they are considered ‘basic’.
C.4.0.1 Summation
One commonly used algorithm in computer science is summation. The solution is simple: we use the add operator in a loop
def summation(numbers):
"""
Parameters
----------
numbers: list
The input list.
Returns
-------
sum : int
The summation of the input list, if the input is empty please return None
"""
# Your code here
# Special case: If the numbers list is empty, return None:
if len(numbers) == 0:
return None
# Start the total at 0:
sum = 0
# Loop over each number in numbers:
for current in numbers:
# Add the number to the total:
sum += current
return sumC.4.0.2 Product
Another common algorithm is finding the product of a list of integers.
def product(numbers):
"""
Parameters
----------
numbers: list
The input list.
Returns
-------
product : int
The product of the input list, if the input is empty please return None
"""
# Special case: If the numbers list is empty, return None:
if len(numbers) == 0:
return None
# Your code here
product = 1
# Loop over each number in numbers:
for current in numbers:
# Multiply the number to the total:
product *= current
return productC.4.0.3 Smallest and largest
C.5 Sorting
One of the most common applications in computer science is sorting, which is the process by which data is arranged according to its values. People are surrounded by data. If the data was not ordered, it would take hours and hours to find a single piece of information. Imagine the difficulty of finding someone’s telephone number in a telephone book that is not ordered!
C.5.1 Selection sorts
In a selection sort, the list to be sorted is divided into two sublists — sorted and unsorted— which are separated by an imaginary wall. We find the smallest element from the unsorted sublist and swap it with the element at the beginning of the unsorted sublist. After each selection and swap, the imaginary wall between the two sublists moves one element ahead, increasing the number of sorted elements and decreasing the number of unsorted ones. Each time we move one element from the unsorted sublist to the sorted sublist, we have completed a sort pass.
A list of n elements requires n − 1 passes to completely rearrange the data.
The visualization is as follows:
The figure shows how the wall between the sorted and unsorted sublists moves in each pass. As we study the figure, we will see that the list is sorted after five passes, which is one less than the number of elements in the list. Thus, if we use a loop to control the sorting, the loop will have one less iteration than the number of elements to be sorted.
source: https://github.com/hustcc/JS-Sorting-Algorithm
Refer to https://visualgo.net/en/sorting for more visualization of sorting algorithms.
The algorithm uses two loops, one inside the other. The outer loop is iterated for each pass: the inner loop finds the smallest element in the unsorted list.
C.5.2 Exercise 2: Write a selection sort for list of intergers that sorts the integer from smallest to largest
def selection_sort(arr):
"""
Parameters
----------
arr: list
The unsorted input list that contains integers
Returns
-------
arr : list
The sorted list
"""
n = len(arr)
## Move the wall one element to the right
for wall in range(n-1):
## Place the wall at the leftmost of the list
min_index = wall
## Find smallest element in the unsorted list
for cur in range(min_index+1,n):
if arr[cur] < arr[min_index]:
min_index = cur
## Swap smallest element with first element in the unsorted list
arr[wall], arr[min_index] = arr[min_index], arr[wall]
return arrC.5.3 Bubble sort
In the bubble sort method, the list to be sorted is also divided into two sublists—sorted and unsorted. The smallest element is bubbled up from the unsorted sublist and moved to the sorted sublist. After the smallest element has been moved to the sorted list, the wall moves one element ahead, increasing the number of sorted elements and decreasing the number of unsorted ones.
Each time an element moves from the unsorted sublist to the sorted sublist, one sort pass is completed. Given a list of n elements, bubble sort requires up to n − 1 passes to sort the data.
The following shows how the wall moves one element in each pass. Looking at the first pass, we start with 56 and compare it to 32. Since 56 is not less than 32, it is not moved, and we step down one element. No exchanges take place until we compare 45 to 8. Since 8 is less than 45, the two elements are exchanged, and we step down one element. Because 8 was moved down, it is now compared to 78, and these two elements are exchanged. Finally, 8 is compared to 23 and exchanged. This series of exchanges places 8 in the first location, and the wall is moved up one position. The algorithm gets its name from the way in which numbers — in this example, 8 — appear to move to the start, or top, of the list in the same way that bubbles rise through water.
source: https://github.com/hustcc/JS-Sorting-Algorithm
C.5.4 Exercise 3: Write a bubble sort for list of intergers that sorts the integer from smallest to largest
def bubble_sort(arr):
"""
Parameters
----------
arr: list
The unsorted input list that contains integers
Returns
-------
arr : list
The sorted list
"""
n = len(arr)
## Move the wall one element to the right
for wall in range(n-1):
#swapped = False
## bubble each element up to the left
for j in range(n-1, wall, -1):
if arr[j] < arr[j-1]:
arr[j], arr[j-1] = arr[j-1], arr[j]
#swapped = True
return arrC.5.5 Insertion sort
The insertion sort algorithm is one of the most common sorting techniques, and it is often used by card players. Each card a player picks up is inserted into the proper place in their hand of cards to maintain a particular sequence. (Card sorting is an example of a sort that uses two criteria for sorting: suit and rank.)
In an insertion sort, as in the other two sorting algorithms discussed above, the list is divided into two parts—sorted and unsorted. In each pass, the first element of the unsorted sublist is transferred to the sorted sublist and inserted at the appropriate place. Note that a list of n elements will take n − 1 passes to sort the data.
As you can perceive from the above figure, the wall moves with each pass as an element is removed from the unsorted sublist and inserted into the sorted sublist.
source: https://github.com/hustcc/JS-Sorting-Algorithm
The design of insertion sort follows the same pattern seen in both selection sort and bubble sort. The outer loop is iterated for each pass, and the inner loop finds the position of insertion.
C.5.6 Exercise 4: Write a insertion sort for list of intergers that sorts the integer from smallest to largest
def insertion_sort(arr):
"""
Parameters
----------
arr: list
The unsorted input list that contains integers
Returns
-------
arr : list
The sorted list
"""
n = len(arr)
## Move the wall one element to the right
for wall in range(1,n):
temp = arr[wall]
cur = wall -1
while arr[cur] > temp and cur >= 0:
arr[cur+1] = arr[cur]
cur = cur -1
arr[cur+1] = temp
return arrThe three sorting algorithms discussed here are the least efficient sorting algorithms, and should not be used if the list to be sorted has more than a few hundred elements. There are however several reasons for discussing these sorting algorithms in an introductory book:
- They are the simplest algorithms to understand and analyze.
- They are the foundation of more efficient algorithms such as quicksort, heap sort, Shell sort, bucket sort, merge sort, radix sort, and so on.
Most such advanced sorting algorithms are discussed in books on data structures. You may ask why there are so many sorting algorithms. The reason lies in the type of data that needs to be sorted. One algorithm may be more efficient for a list that is partially sorted, whereas another algorithm may be more efficient for a list that is completely unsorted.
See https://www.sortvisualizer.com/ for more details
C.6 Searching
Another common algorithm in computer science is searching, which is the process of finding the location of a target among a list of objects. In the case of a list, searching means that given a value, we want to find the location of the first element in the list that contains that value. There are two basic searches for lists: sequential search and binary search. Sequential search can be used to locate an item in any list, whereas binary search requires the list first to be sorted.
C.6.1 Sequential search
Sequential search is used if the list to be searched is not ordered. Generally, we use this technique only for small lists, or lists that are not searched often. In other cases, the best approach is to first sort the list and then search it using the binary search discussed later.
In a sequential search, we start searching for the target from the beginning of the list. We continue until we either find the target or reach the end of the list. The following figure traces the steps to find the value 62. The search algorithm needs to be designed so that the search stops when we find the target or when we reach the end of the list.
C.6.2 Exercise 5: Write a sequential search for a list of intergers that return the index of the target value. Note that we should return
Noneif the target does not in the list!
def sequential_search(arr, target):
"""
Parameters
----------
arr: list
The unsorted input list that contains integers
target: int
The target we are trying to search
Returns
-------
location : int
The location or index of the target. Return None if it does not contain the target
"""
location = 0
while location < len(arr) and arr[location] != target:
location += 1
if location == len(arr):
return None
return locationC.6.3 Binary search
The sequential search algorithm is very slow. If we have a list of a million elements, we must do a million comparisons in the worst case. If the list is not sorted, this is the only solution. If the list is sorted, however, we can use a more efficient algorithm called binary search. Generally speaking, programmers use a binary search when a list is large.
A binary search starts by testing the data in the element at the middle of the list. This determines whether the target is in the first half or the second half of the list. If it is in the first half, there is no need to further check the second half. If it is in the second half, there is no need to further check the first half. In other words, we eliminate half the list from further consideration.
We repeat this process until we either find the target or satisfy ourselves that it is not in the list. The following figure shows how to find the target, 22, in a list of 12 numbers using three references: first, mid, and last.
At the beginning,
firstshows 1 andlastshows 12. Letmidshow the middle position, (1 + 12)/ 2, or 6 if truncated to an integer. Now compare the target (22) with data at position 6 (21). The target is greater than this value, so we ignore the first half of the list.Move
firstaftermid, to position 7. Letmidshow the middle of the second half, (7 + 12) / 2, or 9. Now compare the target (22) with data at position 9 (62). The target is smaller than this value, so we ignore the integers from this value (62) to the end.Move
lastbeforemidto position 8. Recalculate mid again, (8 + 7) / 2, or 7. Compare the target (22) with the value at this position (22). We have found the target and can quit.
The algorithm for binary search needs to be designed to find the target or to stop if the target is not in the list. It can be shown that if the target is not found in the list, the value of last becomes smaller than the value of first, an abnormal condition that helps us to know when to come out of the loop.
C.6.4 Exercise 6: Write a binary search for a sorted list of intergers that return the index of the target value. Note that we should return
Noneif the target does not in the list!
def binary_search(arr, target):
"""
Parameters
----------
arr: list
The sorted input list that contains integers
target: int
The target we are trying to search
Returns
-------
location : int
The location or index of the target. Return None if it does not contain the target
"""
first, last = 0, len(arr) - 1
while first <= last:
mid = (first + last) // 2
val = arr[mid]
if val == target:
return mid
if val < target:
first = mid + 1
else:
last = mid - 1
return NoneC.7 Recursion
In general, there are two approaches to writing algorithms for solving a problem. One uses iteration, the other uses recursion. Recursion is a process in which an algorithm calls itself.
C.7.1 Iterative
To study a simple example, consider the calculation of a factorial. The factorial of a integer is the product of the integral values from 1 to the integer. The definition is iterative as shown below. An algorithm is iterative whenever the definition does not involve the algorithm itself.
C.7.2 Recursive
An algorithm is defined recursively whenever the algorithm appears within the definition itself. For example, the factorial function can be defined recursively as shown below.
The decomposition of factorial (3), using recursion, is shown below. If we study the figure carefully, we will note that the recursive solution for a problem involves a two-way journey. First we decompose the problem from top to bottom, and then we solve it from bottom to top.
Although the recursive calculation looks more difficult when using paper and pencil, it is often a much easier and more elegant solution when using computers. Additionally, it offers a conceptual simplicity to the creator and the reader!