|
Introduction
It wasn't until the arrival of the first electronic and programmable computers during the early 1940's at places such as Bletchley Park, that began a journey into a new field called computer science. At the foundation of computer science is the algorithm. An algorithm is an abstract recipe that performs a finite and deterministic sequence of steps on some input to produce some output for solving a problem. An algorithm is a general solution for answering a family of questions. A computer program is an instantiation of an algorithm written in some programming language. Algorithms can be analyzed, designed, implemented and verified. Algorithms should be designed so that they are easy to understand, code, debug, and makes efficient use of the resources. Algorithms must compute the desired function, they must be composed of a series of concrete steps where each step is performed in a finite amount of time. Any next step in a sequence of steps of an algorithm should be unambiguous, there must be a finite number of steps, and algorithms must terminate. Computer science is still in its infant stages and suffers from a lack of foundation. The main focus of computer science deals with the limitations of computers by classifying problems as solvable or unsolvable. The complexity of an algorithm deals with the basis for solution cost by distinguishing computationally easy problems from hard problems, as measured by resource requirements of space and time. Hence, the very essence of computation theory deals with what can and cannot be computed and how quickly can a solution to a problem be computed. Problems can theoretically be solvable, however, due to excessive resources of time and space, some of these problems are not practically solvable. There are two main concerns regarding algorithms: correctness and speed. There are methods for algorithmic proof of correctness such as induction. Another method for correctness is using formalism such as contract programming. When an algorithm halts with a desired output for every input then it is said to be correct. If an algorithm does not halt or produces an undesirable result then it is said to be incorrect. Computation models such as the Turing Machine, can help define boundaries of algorithmic potential. In fact, there are some properties of programs that are undecidable, i.e. cannot be solved in general, such as eliminating all bugs. Lastly, the structure and dynamics of algorithms do have a profound impact on time complexity, for instance, in using an insertion-sort instead of a merge-sort for sorting an array of a million numbers could cause a significant loss of time such as two days vs. two hours respectively regardless of hardware. Related Documents
|