Algorithms
The word algorithm refers to a step-by-step method for performing some action.
•
An algorithm is “a finite set of precise instructions for performing a computation or for solving a problem”
•
A program is one type of algorithm
Examples
•
Directions to somebody’s house is an algorithm
•
A recipe for cooking a cake is an algorithm
•
The steps to compute the cosine of 90° is an algorithm
•
Instructions for filling out a residency transfer form
Suppose we have a list of numbers. Then how do we find the maximum element in the list?
To express the algorithm, we’ll use pseudocode
•
Pseudocode is like a programming language, but not really
The algorithmic language used in this book is a kind of pseudocode, combining elements of Python, C, C++, and Java, and ordinary, but fairly precise, English. (여러 언어들의 요소를 조합한 유사코드)
•
We will use some of the formal constructs of computer languages—such as assignment
statements, loops, and so forth
•
assignment statement (대입문 or 할당문)
•
conditional statements (조건문)
•
iterative statements (반복문)
Ordinarily, algorithm statements are executed one after another in the order in which they are written.
In high-level computer languages, the term variable is used to refer to a specific storage location in a computer’s memory.
•
A given storage location can hold only one value at a time. So if a variable is given a new value
during program execution, then the old value is erased.
The data type of a variable indicates the set in which the variable takes its values, whether the set of integers, or real numbers, or character strings, or the set {0, 1}, and so forth.
An assignment statement gives a value to a variable. It has the form x ≔ e
where x is a variable and e is an expression.
This is read “x is assigned the value e” or “let x be e.”
When an assignment statement is executed,
•
the expression e is evaluated (using the current values of all the variables in the expression),
•
and then its value is placed in the memory location corresponding to x (replacing any previous contents of this location).
Conditional Statement
Conditional statements allow this natural order to be overridden by using the current values of
program variables to determine which algorithm statement will be executed next.
Iterative statements are used when a sequence of algorithm statements is to be executed over and
over again. We will use two types of iterative statements: while loops and for-next loops.
A while loop has the form
while (condition)
[statements that make up the body of the loop]
end while
where condition is a predicate involving algorithm variables.
1. The condition is checked.
2. 3. If condition is true, all the statements in the body of the loop are executed in order.
– Then execution moves back to the beginning of the loop and the process repeats.
If condition is false, execution passes to the next algorithm statement following the loop.
A notation for algorithms
1. The name of the algorithm, together with a list of input and output variables.
2. A brief description of how the algorithm works.
3. The input variable names, labeled by data type (whether integer, real number, and so forth).
4. The statements that make up the body of the algorithm, possibly with explanatory comments.
5. The output variable names, labeled by data type.
Properties of algorithms
•
Input: what the algorithm takes in as input
•
Output: what the algorithm produces as output
•
Definiteness: the steps are defined precisely
•
Correctness: should produce the correct output
•
Finiteness: the steps required should be finite
•
Effectiveness: each step must be able to be performed in a finite amount of time
•
Generality: the algorithm should be applicable to all problems of a similar form
Measuring algorithms
We can time how long it takes a computer
• What if the computer is doing other things?
• And what happens if you get a faster computer?
– A modern 3.5 GHz Windows machine with an Intel Core i7 chip will run an algorithm at a different speed
than a 3.5 GHz MacBook with an Apple M2 chip.
We can measure how many machine instructions an algorithm takes
• Different CPUs will require different amount of machine instructions for the same algorithm
We can loosely define a “step” as a single computer operation
•
A comparison, an assignment, etc.
•
Regardless of how many machine instructions it translates into
An efficient algorithm on a slow computer will always beat an inefficient algorithm on a fast computer
Big-O, Big-Omega, and Big-Theta Notations
The cost and feasibility of implementing a computer algorithm are most affected by the length of
computer time and the amount of computer memory the algorithm requires.
• It often happens that any one of several algorithms could be used to do a certain job
but the time or memory space they require varies dramatically.
The O- , Ω-, and Θ-notations provide approximations that make it easy to evaluate large-scale
differences in algorithm efficiency, while ignoring differences of a constant factor and differences
that occur only for small sets of input data.
Functional growth size
if r ≤ s, then nr = O(ns)
Example: Show that 15n3 + 11n2 + 9 is O(n3)
(Proof) First, as all terms are positive,
0 ≤ 15n3 + 11n2 + 9 for every integer n ≥ 1.
Next,
0 ≤ 15n3 + 11n2 + 9 ≤ 15n3 + 11n3 + 9n3 = 35n3
Thus, it is O(n3)
Orders of exponential and logarithmic functions
For large enough values of x,
•
the graph of the logarithmic function with any base b > 1 lies below the graph of any positive power function,
•
the graph of the exponential function with any base b > 1 lies above the graph of any positive power function.
Another important function in the analysis of algorithms is the function f defined by the formula
f(x) = x logbx for every real number x > 0.
•
For large values of x, the graph of this function fits in between the graph of the identity function and the graph of the squaring function.
Tractable and intractable problems
Class P problems
•
Problems whose solutions can be found with algorithms whose worst-case order with respect to time is a polynomial are said to belong to class P.
•
They are called polynomial-time algorithms and are said to be tractable.
•
Problems that cannot be solved in polynomial time are called intractable.
Class NP (nondeterministic polynomial time) problems
•
For certain problems, it is possible to check the correctness of a proposed solution with a
polynomial-time algorithm, but it may not be possible to find a solution in polynomial time.
•
Such problems are said to belong to class NP.
The biggest open question in theoretical computer science is whether every problem in class NP belongs to class P. This is known as the P vs. NP problem.
The Clay Institute, in Cambridge, Massachusetts, has offered a prize of $1,000,000 to anyone who can either prove or disprove that P = NP.
Class NP-complete problems
•
In recent years, computer scientists have identified a fairly large set of problems, called NP-
complete, that all belong to class NP but are widely believed not to belong to class P.
•
What is known for sure is that if any one of these problems is solvable in polynomial time, then so are all the others
