Ch 5. Recurrence Relations
5.3 Algorithms
An algorithm is a finite, step-by-step procedure for solving a specific problem or performing a task. In computing, algorithms are essential for tasks such as sorting data, searching databases, encrypting information, and analyzing patterns. To understand how algorithms function and how they are evaluated, it is important to define several foundational concepts. They will be explained using the selection sort algorithm, which arranges a list of numbers in ascending order.
Algorithms require input; in the case of selection sort, the input can be a list of unsorted numbers, such as [29, 10, 14, 37, 13]. Once the input is received, an algorithm will execute and process the input based on a finite step-by-step procedure. In selection sort, the algorithm performs a series of comparisons and swaps, gradually transforming the list into a sorted sequence.
The output produced after the algorithm completes all necessary steps is [10, 13, 14, 29, 37] for our selection sort example. It is important for well-designed algorithms that they terminate after a finite number of operations; selection sort does so after processing each element in the list and placing it in its correct position.
To test and understand how an algorithm works internally, we can examine its trace, which is a step-by-step record of its execution. For the selection sort example we have been discussing, the trace may look like the following:
Input: [29, 10, 14, 37, 13]
Select 10 as the smallest element and swap it with 29: [10, 29, 14, 37, 13]
Select 13 and swap it with 29: [10, 13, 14, 37, 29]
Select …
This trace helps visualize the algorithm’s behaviour and is especially useful for debugging.
To describe the algorithm clearly and concisely, we use pseudocode, which expresses the algorithm’s logic in a structured, language-neutral format. The pseudocode for selection sort might look like this:
FUNCTION selection_sort(list)
FOR i FROM 0 TO LENGTH(list) - 1
SET min_index TO i
FOR j FROM i + 1 TO LENGTH(list) - 1
IF list[j] < list[min_index] THEN
SET min_index TO j
END FOR
SWAP list[i] WITH list[min_index]
END FOR
RETURN list
END FUNCTION
This pseudocode outlines the algorithm’s logic without relying on any specific programming language syntax, making it easier to understand and implement across different platforms.
Example 5.23
The problem is to find the position of a target value in a list. The input is a list of integers and a target value. The output is the index of the target value if found, or -1 if not found. The pseudocode for this linear search algorithm is the following:
FUNCTION linear_search(list, target)
FOR i FROM 0 TO LENGTH(list) - 1
IF list[i] == target THEN
RETURN i
END FOR
RETURN -1
END FUNCTION
As a trace example, let the input be list = [3, 7, 9, 2] and target = 9:
Compare 3 with 9, which gives no match
Compare 7 with 9, which gives no match
Compare 9 with 9, which gives a match
The output is 2. This algorithm terminates when the loop ends after checking all elements or upon finding a match.
Real-World Example 5.3: Package Sorting in a Warehouse
Suppose you work for a logistics company that manages a large warehouse where thousands of packages arrive every day. Each package has a barcode label, and the warehouse uses an automated system to sort packages into bins based on the destination information stored in the barcode.
The sorting algorithm handles each package one at a time. It reads the barcode, extracts the destination city, and sends a command to direct the package to the correct bin. The input to the algorithm is the stream of barcode data coming from the scanners. Each barcode includes structured details such as the destination city, postal code, and priority level.
The output is a routing command sent to the conveyor system, which physically moves the package to the appropriate bin. For instance, a package going to Vancouver might be sent to bin 12, while a shipment for Toronto might be placed in bin 7. The algorithm must finish processing each package before moving on; otherwise, a stalled or looping process could leave packages unsorted and slow down operations.
To verify that the system is working properly, engineers often trace the algorithm. This involves recording each step: reading the barcode, decoding the destination, selecting the correct bin, and confirming that the package was routed as expected. Tracing helps identify issues such as unreadable barcodes or packages being sent to the wrong location.
Before the algorithm is added to the warehouse control software, developers typically draft it in pseudocode to make the logic clear. For example:
FUNCTION sort_package(barcode)
destination ← decode(barcode)
bin_number ← lookup_bin(destination)
route_to_bin(bin_number)
END FUNCTION
This pseudocode outlines the essential steps without tying them to a specific programming language, making it easier for engineers, software developers, and warehouse managers to work together on improving the sorting process.
