Section 4.1 Problems, Algorithms, and Programs
Subsection 4.1.1 Problems
Programmers regularly encounter three distinct concepts: problems, algorithms, and computer programs.
A problem can be understood as a task that needs to be accomplished, typically described in terms of inputs and desired outputs. It is crucial to define a problem precisely, focusing on inputs and matching outputs, without specifying the solution method. Constraints on the resources allowable for a solution should be included in the problem definition. Every problem solvable by a computer is subject to such constraints, whether explicitly stated or implied. For instance, a computer program can only utilize available main memory and disk space, and it should execute within a reasonable timeframe.
Problems can be seen as mathematical functions. A function matches inputs (domain) with corresponding outputs (range). Inputs can be individual values or collections of information, referred to as parameters. A specific set of parameter values represents an instance of the problem. For example, a sorting function’s input parameter might be an array of integers, and a particular array with its size and values at each position would be an instance of the sorting problem. Different instances may yield the same output, but any instance of a problem consistently produces the same output whenever the function is computed with that particular input.
This perspective of problems behaving like mathematical functions may differ from your intuition about how computer programs operate. You may be aware of programs where the same input value produces different outputs on separate occasions. For example, entering the "date" command in a typical Linux command line prompt provides the current date, which naturally changes with each day. However, there is more to the input of the "date" program than just the command entered. The program computes a function, and on any given day, a properly functioning "date" program with a fully specified input will always produce a single answer. The output of any computer program is entirely determined by the program’s complete set of inputs. Even a "random number generator" is entirely determined by its inputs (although some random number generation systems seem to circumvent this by incorporating random inputs from external physical processes beyond the user’s control). The scope of functions implementable by programs falls within the realm of Computability.
Subsection 4.1.2 Algorithms
An algorithm refers to a method or process employed to solve a problem. If we consider the problem as a function, an algorithm serves as an implementation of that function, transforming an input into the corresponding output. Multiple algorithms can be employed to solve a single problem. Conversely, a specific algorithm is designed to solve only one problem, computing a particular function. The OpenDSA modules cover various problems, and for many of them, we will explore multiple algorithms. In the case of sorting, there are over a dozen well-known algorithms.
Having knowledge of multiple solutions for a problem offers the advantage of selecting the most efficient solution for a particular problem variation or class of inputs. Solution A may be more efficient than solution B for a specific problem variation or input class, while solution B may be superior for another variation or input class. For instance, one sorting algorithm may be ideal for sorting a small collection of integers (which is significant when performing the task multiple times), while another algorithm may excel at sorting a large collection of integers. A third algorithm might be the most suitable for sorting a collection of variable-length strings.
By definition, something can only be considered an algorithm if it possesses the following properties:
- Correctness: It accurately computes the desired function, transforming each input into the correct output. Note that every algorithm implements a function, as it maps every input to some output (even if that output is a program crash). The concern here is whether a given algorithm effectively implements the intended function.
- Concrete Steps: It comprises a series of well-defined and comprehensible steps that can be executed by the person or machine performing the algorithm. Each step must be accomplishable within a finite amount of time. Thus, the algorithm provides a step-by-step "recipe" for problem-solving, where each step is within our capability to perform. The feasibility of executing a step may vary depending on the intended executor. For example, the steps in a cookbook recipe may be sufficiently concrete for instructing a human cook but not for programming an automated cookie-making factory.
- Unambiguous Execution: There should be no ambiguity about which step is to be executed next. Typically, algorithms involve selection, such as the use of an "if" statement, enabling a choice of the next step. However, at the time of making the choice, the selection process must be unambiguous.
- Finite Steps: It consists of a finite number of steps. If the algorithm’s description were to comprise an infinite number of steps, it would be impossible to document or implement it as a computer program. Most algorithm description languages incorporate iteration constructs, allowing repeated actions. Programming languages feature constructs like the "while" and "for" loops to facilitate iteration. Iteration enables concise descriptions, with the actual number of steps executed controlled by the input.
- Termination: It must terminate and not enter an infinite loop, ensuring that the algorithm reaches a conclusion.
Subsection 4.1.3 Programs
We often perceive a computer program as a specific instance or tangible representation of an algorithm in a programming language. Algorithms are typically described in terms of programs or sections of programs. Naturally, multiple programs can be instances of the same algorithm since various modern programming languages can be used to implement the same set of algorithms (although some languages may offer more programmer-friendly features). In practice, the terms "algorithm" and "program" are often used interchangeably, even though they represent distinct concepts. However, by definition, an algorithm must provide sufficient detail to allow its conversion into a program when necessary.
The requirement for an algorithm to terminate means that not all computer programs align with the technical definition of an algorithm. An example is your operating system. Nonetheless, it is possible to consider the different tasks performed by an operating system, each with its associated inputs and outputs, as individual problems. These problems can be addressed by specific algorithms implemented within different parts of the operating system program. Each algorithm terminates once it produces the desired output for its respective problem.
Subsection 4.1.4 More about Problems, Algorithms, and Programs
You have attempted of activities on this page.
opendsa-server.cs.vt.edu/OpenDSA/Books/Everything/html/AnalPrelim.html#id1
