Unit 6 Algorithms
- Problem: a general description of a task that can (or cannot) be solved with an algorithm
- Algorithm: a finite set of instructions that accomplish a task
- Sequencing: putting steps in an order
- Selection: deciding which steps to do next
- Iteration: doing some steps over and over
- Linear search: a search algorithm which checks each element of a list, in order, until the desired value is found or all elements in the list have been checked
- As more inputs are added, the number of steps grows at the same rate
- Binary search: a search algorithm that starts at the middle of a sorted set of numbers and removes half of the data; this process repeats until the desired value is found or all elements have been eliminated
- Faster than linear search, but the data must be sorted
- Efficiency: a measure of how many steps are needed to complete an algorithm
- Reasonable Time: algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc) are said to run in a reasonable amount of time
- Unreasonable Time: Algorithms with exponential or factorial efficiencies are examples of algorithms that run in and unreasonable amount of time
- Heuristic: provides a “good enough” solution to a problem when an actual solution is impractical or impossible
- Decision Problems
- “Is there a path?”
- Optimization Problems
- “What’s the shortest path?”
- Undecidable Problem: a problem for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer
- “Will this code work?”
- Ex: Halting Problem
- Sequential Computing: programs run in the order, 1 command at a time
- Parallel Computing: programs are broken into small pieces, some of which are run simultaneously
- Some steps are performed at the same time
- Distributed Computing: programs are run by multiple devices
- Speedup: the time used to complete a task sequentially divided by the time to complete a task in parallel
- Sequential time divided by parallel time