The Concept of an Algorithm Algorithm Representat
What is an algorithm?
An
algorithm is a well-ordered collection of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time.
1.
Wet your hair. 2. Lather your hair. 3. Rinse your hair. 4. Stop.
The question that must be answered is:
At any point in the execution of the algorithm, do you know what operation is to be performed next? Well-ordered operations: 1. Wet your hair. 2. Lather your hair.
Not well-ordered operations:
1. Either wet your hair or lather your hair. 2. Rinse your hair.
3. Rinse your hair.
Don't assume that you can't make choices:
Well-ordered operations: 1. If your hair is dirty, then a. Wet your hair. b. Lather your hair. c. Rinse your hair. 2. Else a. Go to bed. Well-ordered operations: If your hair is dirty, then
Wet your hair. Lather your hair. Rinse your hair.
Else Go to bed.
Note: We will often omit the numbers and the letters and assume a "top-down" reading of the operations.
Unambiguous operations
The question that must be answered is: Does the computing entity understand what the operation is to do?
This implies that the knowledge of the computing entity must be considered.
For example, is the following ambiguous?
Make the pie crusts.
To an experienced cook,
Make the pie crusts. is not ambiguous. But, a less experienced cook may need: Take 1 1/3 cups of flour.
Sift the flour.
Mix the sifted flour with 1/2 cup of butter and 1/4 cup of water to make dough. Roll the dough into two 9-inch pie crusts. or even more detail!
One question we will be exploring in the course is what are the primitives of a computer. Note that a given collection of operations may be an algorithm with respect to one computing agent, but not with respect to another computing agent!!
The question that must be answered is: Is the computing entity capable of doing the operation? This assumes that the operation must first be unambiguous- i.e. the computing agent understands what is to be done. Not effectively computable operations: Write all the fractions between 0 and 1. Add 1 to the current value of x.
The question that must be answered is: Can the user of the algorithm observe a result produced by the algorithm? The result need not be a number or piece of text viewed as "an answer". It could be an alarm, signaling something is wrong.
It could be an approximation to an answer.
It could be an error message.
The question that must be answered is: Will the computing entity complete the operations in a finite number of steps and stop? Do not confuse "not finite" with "very, very large". A failure to halt usually implies there is an infinite loop in the collection of operations: 1. Write the number 1 on a piece of paper. 2. Add 1 to the number you just wrote and write it on a piece of paper. 3. Repeat 2. 4. Stop.
An
algorithm is a well-ordered collection of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time.
Computer
science is the study of algorithms
including
1. Their 2. Their 3. Their 4. Their
formal and mathematical properties hardware realizations linguistic realizations applications
It
is not enough to simply develop a correct algorithm to solve a problem. We must worry about some additional properties of an algorithm:
How efficient is it? How does it compare to other algorithms that solve the same problem?
Algorithms
are executed by computing
entities How are these entities constructed?
The emphasis will be on the logical construction of a computer, not the physical construction.
How
do we represent algorithms? Designing programming languages and translating algorithms into these languages so that they can be executed by the hardware
What
are some of the many important and popular applications of computers in current use including:
modeling and simulation information retrieval numerical problem solving networking graphics
Communication
problems arise:
when the language used for an algorithms representation is not precisely defined or when information is not given in adequate details. Computer Science approaches these problems by establishing a well-defined set of building blocks from which algorithm representation can be constructed. Such a building block is called primitive.
2-18
2-19
Requires
well-defined primitives A collection of primitive along with a collection of rules starting how the primitives can be combined to represent more complex ideas constitutes a programming language.
2-20
less formal, intuitive notation system known as pseudocode.
In general it is a notational system in which ideas can be expressed informally during the algorithm development process.
2-21
Assignment
Statement:
name expression assign name the value of expression E.g.
RemainingFunds CheckingBalance+ SavingsBalance.
Conditional
selection
if condition then action E.g. Should it be the case that sales have decreased, lower the price by 5%
if (sales have decreased) then (lower the price by 5%)
2-22
Repeated
execution
while condition do activity E.g. While there are tickets to sell, keep selling tickets
while (tickets remain to be sold) do (sell a ticket)
2-23
Indentation
often enhances the readability. For example:
if (not raining) then (if (temperature= hot) then (go swimming) else (play golf) ) else (watch TV)
2-24
Procedure
procedure name (generic names) E.g. Apply the procedure Sort to the organizations membership list
procedure Sort (List)
2-25
2-26
