U10 - Algorithms

Unit Vocabulary

  • 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.

  • Iteration: a repetitive portion of an algorithm which repeats a specified number of times or until a given condition is met

  • Selection: deciding which steps to do next

  • Sequencing: putting steps in an order

  • 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


Unit Objectives

  • Explain that some algorithms may look or operate differently but still solve the same problem.

  • Explain that some problems may look different but be similar or look similar but be different.

  • Explain the formal definitions of a problem, an algorithm, sequencing, selection, and iteration.

  • Compare the efficiency of Linear Search and Binary Search

  • Use Binary Search to determine if a number is in a list

  • Use Linear Search to determine if a number is in a list

  • Explain how both formal mathematical reasoning and informal measurement can be used to determine an algorithms efficiency

  • Explain the difference between problems that run in a reasonable time and those that do not

  • Determine if an algorithm runs in unreasonable time.

  • Develop a heuristic to solve a problem.

  • Distinguish between decision problems and optimization problems.

  • Explain the existence of undecidable problems

  • Calculate the speedup of a parallel solution to a problem

  • Describe the benefits and challenges of parallel and distributed computing.

  • Explain the difference between sequential, parallel, and distributed computing.