Computer Science Unit 10 notes
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
Efficiency: a measure of how many steps are needed to complete an algorithm
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.
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.
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 an unreasonable amount of time.
Heuristic: provides a "good enough" solution to a problem when an actual solution is impractical or impossible
Decision Problem: a problem with a yes/no answer (e.g., is there a path from A to B?)
Optimization Problem: a problem with the goal of finding the "best" solution among many (e.g., what is the shortest path from A to B?)
Undecidable Problem: a problem for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer
Sequential Computing: a model in which programs run in order, one command at a time.
Parallel Computing: a model in which programs are broken into small pieces, some of which are run simultaneously
Distributed Computing: a model in which 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
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
Efficiency: a measure of how many steps are needed to complete an algorithm
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.
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.
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 an unreasonable amount of time.
Heuristic: provides a "good enough" solution to a problem when an actual solution is impractical or impossible
Decision Problem: a problem with a yes/no answer (e.g., is there a path from A to B?)
Optimization Problem: a problem with the goal of finding the "best" solution among many (e.g., what is the shortest path from A to B?)
Undecidable Problem: a problem for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer
Sequential Computing: a model in which programs run in order, one command at a time.
Parallel Computing: a model in which programs are broken into small pieces, some of which are run simultaneously
Distributed Computing: a model in which 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