Applying an algorithm to a task

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. A teacher has a list of student names and wants to know if "Mia" is in it. Which algorithm fits the task?

A Sort, because the output is a list of names

B Search, because the output is found or not found

2. You want to show a list of race times from fastest to slowest. Which algorithm matches the output you need?

A Sort, because the output is the same data in a new order

B Linear search, because it looks at every time

3. Your data is a list of scores that is already sorted. You need to check if 72 is in it. Which is the better choice?

A Binary search

B Selection sort

4. A list of 1,000,000 unsorted usernames is searched once for "kai_99". Which is the better choice?

A Linear search, because sorting first would take longer than one search

B Binary search, because it is always faster

5. You write a search once and need it for many different lists. What is the best way to reuse the algorithm?

A Copy and paste the code and edit it for each list

B Wrap it in a function with the list and target as parameters

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
1def find_student(names, target): return target in names		APrinting the result of .sort() shows None because .sort() changes the list and returns nothing. Print names, or use sorted(names).
2sorted(scores, reverse=True)		BWraps a search algorithm in a function so you can reuse it on any list of names and any target.
3The task asks 'Is this username already taken?' so the input is a list and a value, and the output is yes or no. Choose a search.		Cif username in all_users:
4The task asks for a leaderboard from highest to lowest, so the input is an unordered list and the output is an ordered list. Choose a sort.		Dleaderboard = sorted(points, reverse=True)
5top_score = sort(scores)		EUsing a sort when the task needs one value found and not an ordered list. Also, sort() is not a built-in function; sorted() or max() should be used.
6names.sort() print(names.sort())		FApplies a sort algorithm to a list of scores to give a new list in order from highest to lowest.

Definitions

algorithm

Fill in the Blanks

Complete each line of code by filling in the missing parts.

scores = [72, 95, 58, 83] ranked = ______(scores) print(ranked)

names = ["Ava", "Ben", "Cal"] found = "Ben" __ names print(found)

___ rank(scores): return sorted(scores) print(rank([4, 2, 9]))

data = [21, 3, 15, 8] data.____() print(data)

linear = 1000 binary = 10 print(linear _ binary)

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A def find(items, target):

B for i in range(len(items)):

C if items[i] = target:

D return i

E return -1

Question 2

A names = ["Zoe", "Ali", "Mia"]

B ordered = names.sort()

C print(ordered)

Question 3

A def is_sorted(nums)

B return nums == sorted(nums)

C print(is_sorted([1, 2, 3]))

Question 4

A def count_steps(items, goal):

B steps = 0

C for item of items:

D steps += 1

E if item == goal:

F return steps

Question 5

A def smallest[nums]:

B return min(nums)

C print(smallest([5, 2, 9]))

Answer Key

Applying an algorithm to a task

Section A: Quick Questions

B — Search, because the output is found or not found

A — Sort, because the output is the same data in a new order

A — Binary search

A — Linear search, because sorting first would take longer than one search

B — Wrap it in a function with the list and target as parameters

Section B: Match the Pairs

def find_student(names, target): return target in names → Wraps a search algorithm in a function so you can reuse it on any list of names and any target.

sorted(scores, reverse=True) → Applies a sort algorithm to a list of scores to give a new list in order from highest to lowest.

The task asks 'Is this username already taken?' so the input is a list and a value, and the output is yes or no. Choose a search. → if username in all_users:

The task asks for a leaderboard from highest to lowest, so the input is an unordered list and the output is an ordered list. Choose a sort. → leaderboard = sorted(points, reverse=True)

top_score = sort(scores) → Using a sort when the task needs one value found and not an ordered list. Also, sort() is not a built-in function; sorted() or max() should be used.

names.sort() print(names.sort()) → Printing the result of .sort() shows None because .sort() changes the list and returns nothing. Print names, or use sorted(names).

Section C: Definitions

algorithm — A step-by-step method for solving a problem, like search or sort. Choose one by matching its input and output to your data, then wrap it in a function to reuse it.

Section D: Fill in the Blanks

scores = [72, 95, 58, 83]
ranked = sorted(scores)
print(ranked)

names = ["Ava", "Ben", "Cal"]
found = "Ben" in names
print(found)

def rank(scores):
    return sorted(scores)
print(rank([4, 2, 9]))

data = [21, 3, 15, 8]
data.sort()
print(data)

linear = 1000
binary = 10
print(linear > binary)

Section E: Spot the Error

C — A single = assigns a value, but a linear search needs to compare each item. It should be == (if items[i] == target:).

B — The .sort() method changes the list in place and returns None, so ordered would be None. To get a new sorted list, use sorted(names).

A — A function definition must end with a colon. It should be def is_sorted(nums):

C — Python loops use the keyword in, not of. It should be for item in items: so the function can count the steps of a linear search.

A — Function parameters go in round brackets, not square brackets. It should be def smallest(nums):