Definition of an algorithm.
An algorithm is a well-ordered and a finite sequence of unambiguous computable steps which when executed produces a desired and halts in a finite amount of time.
Some elucidation.
■■ desired result
■■ unambiguous steps
■■ computable steps (perhaps not all are computable)
■■ well-ordered
■■ finite sequence of steps
■■ must halt
How do we write an algorithm? Oil/filter change problem.
In plain English:
Place an oil-pan underneath the oil-plug of the car. When ready, unscrew the plug from the oil-plug and let the oil drain. When the oil is completely drained, replace the oil-plug and unscrew the oil-filter. Take a new filter and screw it in. Next, remove the oil-cap from the engine block and pour in 4-quarts of oil. When finished, replace the oil-cap back.
In structured English:
1. Place an oil-pan underneath the oil-plug
2. Unscrew the oil-plug
3. Drain oil
4. Replace the oil-plug
5. Unscrew the oil-filter
6. Insert a new oil-filter
7. Replace the oil-plug
8. remove the oil-cap from the engine block
9. Pour in 4-quarts of oil
10. Replace the oil-plug.
Another example. Making Bread.
1. Add all the dry ingredients.
2. Mix.
3. Add the required amount of water into it.
4. Knead.
5. Let rise.
6. Bake for x units of time.
Another example. Washing dishes.
1. Stack dishes by sink.
2. Fill sink with hot soapy water
3. While there are more dishes:
3.1 Get dish from the stack
3.2 Wash the dish thoroughly
3.3 Put dish in drain rack.
4. Wipe off counter
5. Rinse out sink.
Another problem. Print all integers from 1 to 100.
1. Let
2. While is not greater than 100:
2.1 Print
2.2
3. Stop.
Another problem. Add all odd integers from 1 to 100.
1. Let
2. Let
3. While is not greater than 100:
3.1 add to
3.2
4. Stop.
Consider a sorting algorithm. Items to be sorted are in an array items[5].
1. sorted = false
2. while (not sorted) do the following:
2.1. sorted = true;
2.2. Scan list from first-item to last-item
comparing two consecutive items at a time
2.2.1 if the first item > next item
2.2.1.1. swap them
2.2.1.2. sorted=false
2.2.1.3 go back to 2
3. stop. // end sort.
What if we had 10,000 items? Could we use the same algorithm? Does it always end? How efficient is the routine: Time-wise, memory-wise, complexity-wise?
3. Find the largest item in a list of items.
Assume items[5]. If the algorithm works on it, we could use it for a larger–sized problem.
1. largest = item[0] // the first-item of the list
1.1 current_position = 0 // location of the largest
1.2 location = current_position
2. Compare the largest item with the items in the list from the cuurent_position to the last one.
2.1 currrent_position = current_position + 1
2.2 if list[current_position] > largest
2.2.1 largest = list [current_position]
2.2.2 location = current_position
3. stop. Report largest, current_postion.
Another type of algorithms. Recursive algorithms.
Given a list, find the number of items in the list.
1. If the list is empty, return zero.
2. Otherwise, go to the next item of the list and count the list from there.
3. Add 1 to the above count, and return this value.
Another example. Coin changing.
US coin denominations: 25c, 10c, 5c, and 1c.
Given a number such as between 0 and 99, make up using minimum number of coins.
Example. Suppose = 73.
1. We choose as many quarters as we can to arrive closest to . In this case, # of quarters = 2, and the remainder could be handled using the rest of the coin denominations.
Do you see what we have to do? We want to express mathematically the identity that
such that is minimum and are integers and never negative.
For US denomination, this will always find the best solution. This is a type of algorithm known as Greedy algorithm. Does it always work?
What if we have a denomination with 10, 5, and 1? Would it work still?