Chapter 1 - The Role of Algorithms in Computing Flashcards
Informally, what is an algorithm?
Any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. Thus it is a sequence of computational steps that transform the input into the output.
What is a well-specified computational problem?
A problem whose statement specifies in general terms the desired input/output relationship.
Provide a well-specified problem description of the sorting problem.
Input: A sequence of n numbers
Output: A permutation <a> of the input sequence such that a’1 <= a’2 <= … <= a’n</a>
Given the input sequence <31, 41, 59, 26, 41, 58>, what should a sorting algorithm return as output?
The sequence <26, 31, 41, 41, 58, 59>.
What is an instance of a problem?
An instance of a problem consists of the input needed to compute a solution to the problem. Each unique input to an algorithm is a new instance of the problem that algorithm aims to solve.
What does it mean when an algorithm solves the given computational problem.
That means that the algorithm is correct. That is, for every input instance, it halts with the correct output.
What might cause an algorithm to be incorrect?
For certain input instances an incorrect algorithm might halt with an incorrect answer, or it may not halt at all.
T/F Incorrect algorithms are never useful.
False, they can be useful if their error rate is controlled. However most of the time, we’re concerned with correct algorithms.
How can an algorithm be specified? What are the requirements that this specification must provide?
An algorithm can be specified in English, as a computer program, or even as a hardware design. The only requirement is that the specification must provide a precise description of the computational procedure to be followed.
What is a data structure?
A data structure is a way to store and organize data in order to facilitate access and modifications.
T/F No single data structure works well for all purposes.
True, it is important to know the strengths and limitations of several data structures.
What is the usual measure of efficiency for an algorithm?
Speed, or how long an algorithm takes to produce its result.
What is an NP-complete problem? What is unique about NP-complete problems?
NP-complete problems are problems for which no efficient algorithm has ever been found. However, NP-complete problems are different from other problems for which no efficient algorithm has been found because nobody has ever proven that an efficient algorithm for one cannot exist. In other words nobody knows whether or not efficient algorithms exist for NP-complete problems. NP-complete problems are even more unique because they have the remarkable property that is an efficient algorithm exists for any of them, then efficient algorithms exist for all of them. Several NP-complete problems are similar, but not identical, to problems for which efficient algorithms are known.
Other than speed, what other measures of efficiency might one use in a real-world setting?
Storage space, and cost-efficiency.
Are algorithms really that important in light of other advanced technologies?
Yes, algorithms should be considered a technology, just like advanced computer hardware. Total system performance depends on choosing efficient algorithms as much as on choosing fast hardware.
