ALG1 : What is Algorithm?

My first journey into learning and understanding algorithms and data structures starts here. After almost a week of learning the basic theory, from the definition of an algorithm, I summarized and wrote down the things that need to be understood as a basic foundation. Nothing too much or complicated, just the definition, main points, criteria, and the stages of analyzing an algorithm.

Basic Definition

An algorithm is a collection of instructions needed to solve a problem or complete a task, which is written down in a form that can be understood by others. This collection of instructions can also be interpreted as a thought process. The thought process between one individual and another will definitely be different. Even when the given problem and the desired result are the same, each person will have a different way or thought process. This is what an algorithm is. Simply put, there is a problem, there is an output to be achieved, and there is an algorithm.

Algorithms that are written down can take many forms. They can be written as sentences, pictures or diagrams, and even tables. There is a lot of freedom when writing an algorithm because it is not bound by anything. You can use any language and any device.

In computer science, computers are the ones that execute algorithms. Computers execute the commands they are given, which were previously written as a collection of instructions called a program. A program is written in a specific programming language, such as C, C++, Java, COBOL, BASIC, etc. The instructions can be the same, almost the same, or completely different from one individual to another.

According to Donald Knuth, an algorithm has at least the following 5 criteria:

1. Input : Can have 0 or more inputs.

2. Output : Must have at least 1 output

3. Definiteness : Has a clear, specific, and unambiguous definition or description

4. Finiteness : Has an endpoint, so infinite loops must be avoided

5. Effectiveness : Of course, every step must be able to solve the problem effectively and without unnecessary complexity

Algorithm & Program

Algorithms and programs are two different things, but they are closely related. As mentioned earlier, an algorithm is a thought process for solving a computational problem. A program, on the other hand, is the procedure for implementing the algorithm to solve that problem.

In a process called SDLC (Software Development Lifecycle), there are two important stages: the design phase and the implementation phase. Whatever we want to manufacture, develop, or build using an engineering process, the first thing we do is design. Design what we want to accomplish as thoroughly as possible, not necessarily 100% perfectly, but pay attention to details that can support the success of the project. We cannot simply use trial and error, start building immediately, then destroy and rebuild if it fails, and keep repeating the process. This is highly ineffective, inefficient, and wastes a lot of resources. It is not just about relying on feelings; these things can cause a lot of time to be wasted writing useless programs. So, the main point is: design first, then write the program, also known as implementation.

There are two approaches to understanding algorithms and programs: a priori analysis and a posteriori testing. A priori analysis describes an algorithm during the design and analysis stages. It is conceptual, not tied to any particular language or device, and its result is a complexity function. The purpose of a priori analysis is to understand in detail how an algorithm works and how much memory space and time it requires. Meanwhile, a posteriori testing describes a program during the implementation stage. It is tied to a specific language or device, and its result is a real measurement using specific units. The purpose of a posteriori testing is to directly test the performance of a program on a computer.

The image below explains the main differences between an algorithm and a program

An algorithm is limited to a concept or big picture. This is the design phase. It is not tied to a programming language and is not tied to any particular hardware or software. This stage analyzes the things that are needed. Generally, the result of algorithm analysis is a mathematical complexity function, namely time and space functions.

A program, on the other hand, is in the implementation stage, applying the algorithm that has already been designed. It turns the algorithm into an executable program using a specific programming language and depends on the software and hardware being used. The program then enters the testing stage, and the results can take many forms with specific calculations and units. For example, the program's execution time can be measured in seconds or milliseconds, and memory usage can be measured in bytes.

Writing & Analyzing Algorithms

A. Writing Algorithms

Writing an algorithm does not have specific rules such as defining data types. In simple terms, it can be written as follows in the Swap algorithm:

Algorithm Swap(a, b)
begin
    temp <- a;
    a <- b;
    b <- temp;
end

When writing an algorithm, the most important thing is that it is easy to understand. In the algorithm above, there is the function name, Algorithm Swap, as well as the variables a, b, and temp. There is also a beginning and an end to the algorithm.

B. Analyzing Algorithms

There are several criteria for analyzing an algorithm, and the following criteria are not universal and may not apply to every analysis. The most important ones, as discussed earlier, are time and space, while the others are additional depending on the requirements.

• Time : How quickly is the procedure executed? Does it take a long time or not?

• Space : How much memory is used?

• Network : How will the program be executed and transferred?

• Power : How much power is required?

• CPU Register : What will the use of memory addresses in the CPU look like?

Here is an analysis of a Swap algorithm:

When analyzing an algorithm, we can assume certain values without needing to look at details such as data types. Assume two parameters: time complexity and space complexity. Assume that a statement such as "temp = a" takes 1 unit of execution time, and one variable such as "a" requires 1 unit of memory space. Therefore, based on the total time and space required, the Swap algorithm has constant total time and space, which can be represented using Big O notation as O(1).