Algorithms
- Definition
(HSM Ch.1.5.1):
An algorithm is a finite set of instructions that, if followed,
accomplishes a particular task.
- All algorithms must satisfy the
following criteria:
- Zero or more input values
- One or more output values
- Clear and unambiguous instructions
- Atomic steps that take constant time
- No infinite sequence of steps (help, the halting problem)
- Feasible with specified computational device
- Selection sort
(HSM Ch.1.5.1)
- selsort.cpp
- The algorithm
- Tracing the algorithm, line by line for each variable
- Soundness and completeness
- Binary search
- binsrch1.cpp
- The linear algorithm
(HSM Ch.1.5.1)
- binsrch2.cpp
- The recursive algorithm
(HSM Ch.1.5.2)
- Thus there are alternative ways, which is better?
- Recursive algorithms
- Always have a parameter
- Always have a conditional on the parameter to limit the recursion
- Recursive call always involves a modified version of the parameter
- Examples
Exercises
- Writing algorithms: HSM Ch.1.5, exercises 3, 4, 12, 13, 16.
- Examining algorithms: HSM Ch.1.5., exercises 5, 14.
Lab Tasks
Exam Style Questions
- Define an algorithm.
- List six properties that an algorithm should possess.
- List the three key features of a recursive algorithm.
- Give an algorithm to [some task].
- Does the following algorithm achieve [some task]? If not, why not?
[An algorithm]