CONSTRUCTION AND OPTIMIZATION OF ALGORITHMS Computational complexity theory

classifying computational problems according to their inherent difficulty, and relating

these classes to each other.

Stein. Introduction to Algorithms.

N. Wirth. Algorithms and Data Structures.

worst, best or average case. In some particular cases, we

shall be interested in the average-case running time of an algorithm; we shall see the technique of probabilistic analysis applied to various algorithms.

1. The larger of the two natural numbers is 34. What should be the smaller number for the Euclidean algorithm to have as many steps as possible?
2. The larger of the two natural numbers is 55. What should be the smaller number for the Euclidean algorithm to have as many steps as possible?

such as
the amount of communication (used in communication complexity),

the number of gates in a circuit (used in circuit complexity) and
the number of processors (used in parallel computing).
One of the roles of computational complexity theory is to determine the practical limits on what computers can and cannot do.

a few times, then the cost of writing and debugging

the program will dominate the total cost of the program, that is, the actual execution time will not have a significant impact on the total cost. In this case, you should prefer the algorithm that is the easiest to realize.

“small” input data, the degree of growth in the execution

time will be less important than the constant present in the asymptotic runtime formula. At the same time, the notion of “smallness” of the input data depends on the exact execution time of competing algorithms. There are algorithms, such as the algorithm of integer multiplication, which are asymptotically the most efficient, but which are never used in practice even for large tasks, since their proportionality constants far exceed those of other, simpler and less “efficient” algorithms.

get looped or sometimes give the wrong result. But they

still apply, because in most cases they lead to the desired result. For example, Kramer’s rule or resolution method.

sort on the same machine. For inputs of size n,

insertion sort runs in 8n2 steps, while merge sort runs in 64nlgn steps. For which values of n does insertion sort beat merge sort?
2. What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine?

following table, determine the largest size n of a problem

that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.

so that 3 points leave each point.
2. Connect 14 points

with non-intersecting segments so that 4 points leave each point.
3. Draw a closed six-pattern broken line that intersects each of its links once.
4. The volleyball net has a size of 10 by 50 cells. What is the greatest number of ropes can be cut so that the grid does not fall apart into pieces?