Vocabulary: LINEAR SEARCH

Checking each item (element) in a list from left to right, one after another, to find a specific item.

It checks each item in sequential order and stops when a match is found or when the entire list has been checked (which happens when the item being searched for isn’t in the list).

Aka. Sequential search.

Vocabulary: Linear/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.

Vocabulary:

Binary Search

• 1) Set min & max

• 2) Average min & max to find the index of the middle element

• 3) Compare value at middle to target; if matched, return index

• 4) If element < target, set min to middle+1; Else, set max to middle-1

• 5) Repeat steps 2-4 until value is found or if min>max

Will binary search to make a program more efficient?

• Are you searching for one thing in a list or are you finding all the things in the list with some characteristic?

• Is your data sorted or unsorted?

Algorithm takes...

• Linear time: if the number of steps is proportional to the input size. 2x the input size, 2x the time.

• Sublinear time: if the time grows more slowly than the size.

Algorithm takes...

• Constant time: if it takes the same amount of time regardless of input size.

• Quadratic time: if the number of steps is proportional to the square of the input size.

The most important difference in algorithm efficiency is between algorithms that take:

• Polynomial time: if the number of steps is less than or equal to a power of the size of the input, such as constant (n⁰), sublinear, linear (n¹), quadratic (n²), or cubic (n³).

• Exponential time: if the number of steps is less than or equal to a function like 2ⁿ, 10ⁿ, etc., which is much slower than any polynomial.

Vocabulary: Heuristic Solutions

• An exponential time algorithm still solves a problem correctly; it just takes a unreasonably long time.

• Exponential time algorithms can sometimes be replaced by heuristics, which are polynomial-time algorithms that don't solve the problem exactly, but give a good enough approximation.

• A decision problem is a problem with a true/false answer (for example, "is 5,825,496,221 a prime number?").

• 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?").

Classic Heuristic: Traveling Salesman Problem

• There must be a shortest route.

• There is no known polynomial time algorithm for this problem.

• One heuristic: Pick a path at random, then try to improve it by swapping two cities repeatedly until you can't make the path better with such small changes.

"Hill-Climbing"

• You'll find the best nearby path (the top of a hill)

• There might be a higher hill (a better path) further away

• You'll be stuck at a local maximum

Not all decision problems (T/F questions) can be solved with an algorithm.

• A decidable problem a decision problem for which it's possible to write an algorithm that will give a correct output for all inputs. EX: "Is the integer even?"

• 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. EX: "Will this computer program that takes an input always eventually report a result?"

Vocabulary:

Sequential & Parallel Computing

• In sequential computing, operations are performed in order one at a time.

• In parallel computing, the program is broken into smaller steps; some steps are performed at the same time. Modern computers have multiple processors (2, 4, or 8 cores) in a single computer, so you can do small-scale parallel processing on your desktop machine.

Vocabulary

• Distributed computing is a form of parallel computing that uses multiple computers (perhaps even spread out around the world).

• A processor is a piece of circuitry inside a computer that carries out the instructions from programs.

Vocabulary

• Programmers refer to the speedup of parallel solution to describe how many times as fast the parallel solution is compared to the sequential solution:

• E.g. Sequential time is 10 mins, parallel time is 2 mins. speedup = 10/2 = 5. Parallelization is 5x faster.

Homework

• APClassroom.CollegeBoard.org: "5.1 Checkpoint", 7 Q's

• KhanAcademy.org: The building blocks of algorithms, Expressing an algorithm, and Verifying an algorithm (may be next day)