430
mathematical software and numerical analysis play a big role. Therefore, despite the
misconception of many, computer science is not only about programming.
Thus, the next subsections will introduce some basics of computer science to
help readers understand the role of computer science in FEW nexus research.
16.2.1 What Is a Computer Program?
A computer program is a set of machine-understandable instructions which aims to
perform specific tasks on a computer. Computer programs consist of two parts,
namely, algorithms and data structures. Algorithms are ordered step-by-step instructions that aim to solve a problem. The idea of an algorithm does not necessarily
require a computer (Hopcroft et al. 2001). For example, in mathematics, an algorithm may be the strategy to calculate the derivatives of a function. To solve the
same problem, different algorithms may be used. However, algorithms may use
strategies to provide efficiency, to scale up to large datasets and to provide outputs
in a reasonable time.
16.2.2 Computational Complexity Theory
The efficiency of a computer algorithm is often analyzed through a set of mathematical approaches which are considered under computational complexity theory
(Papadimitriou 1994). The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying the amount
of resources needed to solve them, such as time and storage. In addition, it also
provides a qualitative viewpoint where the question of whether a problem is algorithmically decidable or not. In other words, it tries to reply whether there exists an
algorithm to solve the problem. For example, quadratic integer programming is
undecidable (Wolsey 1998).
At the end, the theory gives insight about what can (decidable) and cannot be
computed (non-decidable) as well as the resources needed to do so. For the decidable problems, there are time complexity classes defined to introduce the hardness
of providing the decisions. These decidable problems are yes/no problems which
are tried to be answered by the algorithm. For example, in graph theory “Is the
graph connected?” is such a question to be answered by an algorithm.
(a) Time complexity: In order to quantify the complexity classes, time complexity,
which is denoted by Big-O, is used. For example, suppose we are given an input
with a size of “n,” if the problem can be solved by a square function of the input,
i.e., n
2
, then the time complexity is shown with O(n
2
).
Class P problems: P is the class of problems that can be decided in polynomial time, i.e., those for which the running time is O(n
k
), for k ∈ N. For example,
E. Eftelioglu and S. Shekhar
mathematical software and numerical analysis play a big role. Therefore, despite the
misconception of many, computer science is not only about programming.
Thus, the next subsections will introduce some basics of computer science to
help readers understand the role of computer science in FEW nexus research.
16.2.1 What Is a Computer Program?
A computer program is a set of machine-understandable instructions which aims to
perform specific tasks on a computer. Computer programs consist of two parts,
namely, algorithms and data structures. Algorithms are ordered step-by-step instructions that aim to solve a problem. The idea of an algorithm does not necessarily
require a computer (Hopcroft et al. 2001). For example, in mathematics, an algorithm may be the strategy to calculate the derivatives of a function. To solve the
same problem, different algorithms may be used. However, algorithms may use
strategies to provide efficiency, to scale up to large datasets and to provide outputs
in a reasonable time.
16.2.2 Computational Complexity Theory
The efficiency of a computer algorithm is often analyzed through a set of mathematical approaches which are considered under computational complexity theory
(Papadimitriou 1994). The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying the amount
of resources needed to solve them, such as time and storage. In addition, it also
provides a qualitative viewpoint where the question of whether a problem is algorithmically decidable or not. In other words, it tries to reply whether there exists an
algorithm to solve the problem. For example, quadratic integer programming is
undecidable (Wolsey 1998).
At the end, the theory gives insight about what can (decidable) and cannot be
computed (non-decidable) as well as the resources needed to do so. For the decidable problems, there are time complexity classes defined to introduce the hardness
of providing the decisions. These decidable problems are yes/no problems which
are tried to be answered by the algorithm. For example, in graph theory “Is the
graph connected?” is such a question to be answered by an algorithm.
(a) Time complexity: In order to quantify the complexity classes, time complexity,
which is denoted by Big-O, is used. For example, suppose we are given an input
with a size of “n,” if the problem can be solved by a square function of the input,
i.e., n
2
, then the time complexity is shown with O(n
2
).
Class P problems: P is the class of problems that can be decided in polynomial time, i.e., those for which the running time is O(n
k
), for k ∈ N. For example,
E. Eftelioglu and S. Shekhar