To do: March 24

Warm-up #2

myList <- [1, 2, 3, 4, 10, 11, 16, 25, 32, 33, 45, 47, 51, 69, 75]

• Suppose we used LINEAR search and looked for 30 in the list, how many guesses/iterations would it take before knowing that 30 is NOT in the list?
• Suppose we used BINARY search and looked for 30 in the list, how many guesses/iterations would it take before knowing that 30 is NOT in the list?

​

​

Warm-up #2

myList <- [1, 2, 3, 4, 10, 11, 16, 25, 32, 33, 45, 47, 51, 69, 75]

• Suppose we used LINEAR search and looked for 30 in the list, how many guesses/iterations would it take before knowing that 30 is NOT in the list? 15 guesses or iterations
• Suppose we used BINARY search and looked for 30 in the list, how many guesses/iterations would it take before knowing that 30 is NOT in the list? 4 guesses or iterations

15/2 = 7, 7/2 = 3, 3/2 = 1, 1/2=0 -> log₂15 ≅ 4.

​

Binary Search Algorithm

myList <- [1, 2, 3, 4, 10, 11, 16, 25, 32, 33, 45, 47, 51, 69, 75]

• Best guess? Middle number in the list.
• Compare guess (middle number) with target value.
• If midde = target, YOU FOUND IT! Congrats and return true.
• If middle < target, remove all numbers to the left of middle number including the middle number
• If middle > target, remove all numbers to the right of middle number including the middle number
• If you removed all the numbers and didn’t find target, return false.

Linear Search Algorithm

myList <- [0,10,2,9,11,4,2]

result <- Contains(myList,2)

DISPLAY(result)

​

PROCEDURE Contains(list, target)

{

FOR EACH item IN list

{

IF(item = target)

{

RETURN (true)

}

}

RETURN (false)

< AFTER searching entire list and target value was not found >

}

If the list is not sorted, then you must check each item in the list, one-by-one. The convention is that we start at the left and move to the right.

If we find the target value, we immediately return true.

If we traverse entire list and didn’t return true, target value is not in the list and we return false.

TEXT MODE

3a) What is the advantage of Linear Search algorithm?

​

b) What is the advantage of Binary Search algorithm?

Warm-up #3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

15

14

13

12

11

10 9 8 7 6 5 4 3 2 1

LINEAR

Binary Search

Efficiency: a measure of how many steps are needed to complete an algorithm - it is typically expressed as a FUNCTION of the size of the input.

​

Linear Search: a search algorithm which checks each element of a list until the desired value is found or all elements in the list have been checked. List does NOT have to be sorted.

​

Binary Search: a search algorithm that starts at the middle of a sorted set of items and removes half of the data; this process repeats until the desired value is found or all elements have been eliminated.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

15

14

13

12

11

10 9 8 7 6 5 4 3 2 1

LINEAR

Binary Search

Go over homework:

• 4th period - Submit image/pdf of U6L03 Activity Guide - Unreasonable Time
• Write Unit 6 Key words in IN glossary and submit image/pdf
• Efficiency, Linear Search, Binary Search, Reasonable Time, Unreasonable Time
• Submit Guessing Game notes

5th period: Complete 2nd side of U6L03 Activity Guide

Algorithms solve Problems

Problem: a general description of a task that can (or sometimes cannot) be solved with an algorithm

Algorithm: a finite set of instructions that accomplish a task.

​

• There are usually many algorithms to solve the same problem.
• And there are many ways to write or express an algorithm including natural language, pseudocode, diagrams, and a programming language.
• All algorithms can be created by combining steps in three different ways.

​

Efficiency of Algorithms -> what is considered unreasonable?

Both linear and binary search algorithms are considered reasonable algorithms - they are able to be executed in a reasonable amount of time. Their efficiency is expresses as a function:

• Linear Search: f(n) = n
• Binary Search: f(n) = log(n)

Let’s take a look at a function which is considered UNREASONABLE.

Exponential growth == NOT polynomial

The group raffle activity is an example of an algorithm whose efficiency is described by an exponential function (inverse of the logarithmic function)

If n items took 2ⁿ -1 steps, this would be considered an algorithm which takes an unreasonable amount of time.

Polynomial function

f(n) = n² is a polynomial function - thus the algorithm is considered to run in reasonable time.

Other example of polynomial functions:

f(n) = 2n² + n + 5

f(n) = 3n + 2

f(n) = n³

Linear Reasonable

Log (Binary Search)

Reasonable

Polynomial

Reasonable

Exponential

Unreasonable

Polynomial and Exponential both “curve up”.

Why do you think only exponential is considered “unreasonable”?

Size of input

Number of steps

MC practice:

What function describes relationship between input (# of items) and output (# of steps)?

MC practice:

What function describes relationship between input (# of items) and output (# of steps)?

n²

​

Unit 6 Lesson 4 - Activity

Problem:

A problem is a description of any task that may (or may not) be solved with an algorithm.

​

Algorithm:

An algorithm is a finite set of instructions that accomplish a task.

​

Searching for a target value within a list is a problem CAN be solved with an algorithm.

​

Unit 6 Lesson 4 - Activity

We can categorize problems as either:

• a Decision problem
• or Optimization problem

​

Decision Problems

​

“Is there a path?”

Optimization Problems

​

“What’s the shortest path”?

Traveling Salesman

How many different possible pathways are there to visit all of your friends' houses?

• You must start and end at your own house.
• You can only visit each house once.

​

⌂

⌂

your house

friend's house

A

Traveling Salesman

How many different possible pathways are there to visit all of your friends' houses?

• You must start and end at your own house.
• You can only visit each house once.

​

⌂

⌂

your house

friend's house

A

Traveling Salesman

How many different possible pathways are there to visit all of your friends' houses?

• You must start and end at your own house.
• You can only visit each house once.

​

⌂

⌂

your house

⌂

A

B

Traveling Salesman

How many different possible pathways are there to visit all of your friends' houses?

• You must start and end at your own house.
• You can only visit each house once.

​

⌂

⌂

your house

⌂

A

B

Traveling Salesman

How many different possible pathways are there to visit all of your friends' houses?

• You must start and end at your own house.
• You can only visit each house once.

​

⌂

⌂

⌂

⌂

A

B

C

Traveling Salesman

How many different possible pathways are there to visit all of your friends' houses?

• You must start and end at your own house.
• You can only visit each house once.

​

⌂

⌂

⌂

⌂

A

B

C

Traveling Salesman

How many different possible pathways are there to visit all of your friends' houses?

• You must start and end at your own house.
• You can only visit each house once.

​

⌂

⌂

⌂

⌂

A

B

C

⌂

D

Traveling Salesman

How many different possible pathways are there to visit all of your friends' houses?

• You must start and end at your own house.
• You can only visit each house once.

​

⌂

⌂

⌂

⌂

A

B

C

⌂

D

Prompt: What if we had a lot more places to visit? How would we determine the best path?

​

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

⌂

Unit 6 Lesson 4 - Activity

This is known as the Traveling Salesman Problem.

​

For every new place to visit, the number of options for possible paths increases VERY quickly - the function to describe this change is the factorial function.

​

THIS IS UNREASONABLE algorithm

(too many steps)

That's a lot of possible paths to check for only 10 houses!

Unit 6 Lesson 4 - Activity

The Traveling Salesman Problem can be solved with an algorithm, which checks each possible option.

​

BUT, it would take massive amounts of computing power to compare every single option, especially as the number of homes to visit (otherwise known as nodes) increases.

​

Therefore, it would take an unreasonable amount of time for the solution to be calculated for most instances of the problem.

Unit 6 Lesson 4 - Activity

Welcome to heuristics!

​

• Provide a "good enough" solution to a problem when an actual solution is impractical or impossible

​

In a Unit 1 activity, we explored an optimization problem when we played with the Text Compression widget.

What was the problem we tried to solve?

Unit 6 Lesson 4 - Activity

Optimize lossless text compression to get best (lowest) compression rate

Unit 6 Lesson 4 - Activity

• What is a possible heuristic approach for the Traveling Salesperson problem?

​

Unit 6 Lesson 4 - Activity

• What is a possible heuristic approach for the Traveling Salesperson problem?

​

For each step in the pathway choose to go the closest house. This will give you a pathway that is "good enough".

​

​

Traveling Salesman: an Optimization Problem

• Use the "closest house" approach to find a good enough pathway to visit all of your friends' houses.

What is the total distance?

​

​

⌂

⌂

⌂

⌂

A

B

C

⌂

D

7

4

6

10

7

10

7

9

5

12

Unit 6 Lesson 4 - Activity

Takeaways:

​

The Traveling Salesman Problem is an optimization problem. We are attempting to find the best path.

​

It is also unreasonable because there is not an algorithm that can solve the problem in a reasonable amount of time.

​

We need to use a heuristic to come up with a solution that is "good enough" for most instances of the problem.

​

Use a heuristic if optimal solution takes unreasonable amount of time

EK 4.2.1B: Reasonable time means that the number of steps the algorithm takes is less than or equal to a polynomial function (constant, linear, square, cube, etc.) of the size of the input.

EK 4.2.D Some problems can be solved but not in a reasonable amount of time. In these cases, heuristic approaches may be helpful to find solutions in reasonable time.

Homework

• Per 5 - Submit image/pdf of U6L03 Activity Guide - Unreasonable Time
• AP Classroom - Algorithms practice - comparing efficiencies #1-10
• Complete online
• Show work for each problem in IN and submit image/pdf to Hub
• Submit 3/24 Notes - Traveling Salesperson table