Unit 5 Lab 1
Search Algorithms and Efficiency
In this lab, you will use two different algorithms to search a list, and you will learn that algorithms are categorized by the time required to run them.
Guess My Number
In this section, you will modify your number guessing game from Unit 2 to make the computer do the guessing
How Many 5 Letter Words Are There?
In this section, you will see how long it takes to run a linear search algorithm
Vocabulary
Click each word to view the definition.
Problem
A problem is a general description of a task that may (or may not) be solved algorithmically.
Instance of a Problem
An instance of a problem is one case of a problem, with specific inputs.
Linear Search or Sequential Search
An algorithm takes linear time if multiplying the input size by ten multiplies the time required by ten.
A linear search (or sequential search) algorithm checks each element of a list in order, a process which takes linear time.
Is “Seperate” Spelled Correctly?
In this section, you will use a binary search algorithm to search efficiently in a sorted list.
Vocabulary
Click each word to view the definition.
Binary Search
A binary search algorithm starts in the middle of a sorted list and repeatedly eliminates half the list until either the desired value is found or all elements have been eliminated.
Linear search does a complete traversal of the list. Binary search saves time by doing a partial traversal of the list.
Insert Self-Check Section!
If There's Time
Insert If There is Time Slides
Exactly How Much Faster Is Binary Search?
In this section, you will compare the time required for binary search and for linear search
Vocabulary
Click each word to view the definition.
Efficiency
The relationship between the input size and the number of steps required to solve a problem is the efficiency of the algorithm used to solve the problem.
Categorizing Algorithms
In this section, you will compare four algorithms and learn how they each take a different category of time to run.
Vocabulary
Click each word to view the definition.
Linear Time
An algorithm takes linear time the number of steps is proportional to the input size; doubling the input size doubles the time required.
Sublinear Time
An algorithm takes sublinear time if the time grows more slowly than the size.
Constant Time
An algorithm takes constant time if it takes the same amount of time regardless of input size.
Quadratic Time
An algorithm takes quadratic time if the number of steps is proportional to the square of the input size.
Polynomial Time
An algorithm takes polynomial time if the number of steps is less than or equal to a power of the size of the input, such as constant (n0 ), sublinear, linear (n1), quadratic (n2), or cubic (n3).
Exponential Time
An algorithm takes exponential time if the number of steps is less than or equal to a function like 2n , 10n , etc., which is much slower than any polynomial.
Reasonable Time
The term "reasonable time" describes any algorithm that runs in polynomial time. Exponential time algorithms are not considered reasonable.
If There's Time
Need to add If There is Time Slides
Need to add Self-Check Question
Heuristic Solutions
In this section, you'll learn that even for unreasonable time problems, there can still be reasonable time "close enough" solutions.
Vocabulary
Click each word to view the definition.
Decision Problem
A decision problem is a problem with a true/false answer (for example, "is 5,825,496,221 a prime number?")
Optimization Problem
An optimization problem is one with the goal of finding the best solution among many (for example, "what's the best school schedule to place every student into as many of their requested classes as possible?")
Decidable Problem
A decidable problem a decision problem for which it's possible to write an algorithm that will give a correct output for all inputs.
Undecidable Problem
An undecidable problem is the opposite. It's not possible to write an algorithm that will give a correct output for all inputs—even though it might be possible for some of them.
Insert Self-Check Question
Removing Duplicates
In this section, you will learn a recursive technique to remove duplicates from a list.
Parallelism
In this section, you will learn how running multiple scripts in parallel can reduce the total time it takes to run an algorithm.
Vocabulary
Click each word to view the definition.
Sequential Computing
In sequential computing, operations are performed in order one at a time.
Parallel Computing
In parallel computing, the program is broken into smaller steps, some of which are performed at the same time. Modern computers have multiple processors (2, 4, or 8) in a single computer, so you can do small-scale parallel processing on the machine on your desk.
Distributed Computing
Distributed computing is a form of parallel computing that uses multiple computers (perhaps even spread out around the world).
Processor
A processor is a piece of circuitry inside a computer that processes the instructions from computer programs.
Speedup
Programmers refer to the speedup of parallel solution to describe how many times as fast the parallel solution is compared to the sequential solution:
Insert Self-Check Section (There are three questions! The third is in the If There is Time Section on BJC.)