BJC AP CSP Unit 5 Lab 1

CSP Unit 5 Lesson 1

Algorithmic Efficiency

Open Ended

We'll watch the video together. Describe the strategy that the contestant used.

Multiple Choice

Below is an unsorted list of numbers, which is a list whose elements are not in order.

True or False? The list contain the number 121.

[171, 122, 211, 120, 71, 217, 12, 11, 211, 212, 711, 21, 210, 1, 17, 100, 121, 102, 127, 21, 721, 1, 712, 117]

• True

• False

Multiple Choice

True or False? The list contain the number 71.

[171, 122, 211, 120, 71, 217, 12, 11, 211, 212, 711, 21, 210, 1, 17, 100, 121, 102, 127, 21, 721, 1, 712, 117]

• True

• False

Multiple Choice

True or False? The list contain the number 172.

[171, 122, 211, 120, 71, 217, 12, 11, 211, 212, 711, 21, 210, 1, 17, 100, 121, 102, 127, 21, 721, 1, 712, 117]

• True

• False

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.

Multiple Choice

Suppose an unordered list has n elements. In the best case scenario, how many comparisons are required to find a specific value?

• 1

• n

• between 1 and n

• Not enough info

Multiple Choice

Suppose an unordered list has n elements. In the worst case scenario, how many comparisons are required to find a specific value?

• 1

• n

• between 1 and n

• Not enough info

Multiple Choice

Suppose an unordered list has 1,000 elements, and it takes up to 1 second to search through the entire list.

Then, more items are added to the list so that it now has 1,000,000 elements. How many seconds will it take to search this list?

• 1

• 1,000

• 1,000,000

• Not enough info

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.

Multiple Choice

You choose a number between 1 and 1,000. Roughly how many guesses will I take to guess your number, if you tell me to go higher or lower?

• 1

• 10

• 100

• 1000

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

Multiple Choice

Suppose an ordered list has n elements. In the best case scenario, using binary search, how many comparisons are required to find a specific value? (In CS, log is usually base 2.)

• 1

• log n

• n/2

• n

Multiple Choice

Suppose an ordered list has n elements. In the worst case scenario, using binary search, how many comparisons are required to find a specific value? (In CS, log is usually base 2.)

• 1

• log n

• n/2

• n

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?

Multiple Choice

Suppose an ordered list has 1,000 elements, and it takes up to 1 second to binary search through the entire list.

Then, more items are added to the list so that it now has 1,000,000 elements. How many seconds will it take to search this list?

• 1

• 2

• 10

• 500

• 1,000

Multiple Choice

Suppose an ordered list has 1,000 elements, and it takes up to 1 second to binary search through the entire list.

How many seconds will it take to search a list of 1,000,000,000?

• 3

• 6

• log (1000)

• log (1,000,000)

• 1000

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.

Multiple Choice

The table shows the computer time it takes to complete various tasks on the data of different sized towns.

Based on the information in the table, which of the following tasks is likely to take the longest amount of time when scaled up for a city of population 1,000,000?

• Backing up data

• Sorting data

• Searching through data

• Entering data

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

Multiple Choice

Which type of algorithms may be replaced by heuristics?

• Decision problems

• Optimization problems

• Both

• Neither

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

Multiple Choice

In which of the following problems is a heuristic solution appropriate?

• Find the best combination of ingredients for spaghetti sauce.

• Find the biggest item in a list.

• Find the combination to a lock with n numbers.

• Playing chess.

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.

Multiple Choice

How long will this sequential program take to run?

• 4

• 6

• 8

• 18

Multiple Choice

Careful! How long will this parallel program take to run?

• 6

• 8

• 14

• 18

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)