3.9 Algorithms

Essential Knowledge

  • Algorithms can be written in different ways and still accomplish the same tasks
  • Algorithms that appear similar can yield different side effects or results
  • Some conditional statements can be written as equivalent Boolean expressions
  • Some Boolean expressions can be written as equivalent conditional statements
  • Different algorithms can be developed or used to solve the same problem
  • Algorithms can be created from an idea, by combining existing algorithms, or by modifying existing algorithms.
  • Knowledge of existing algorithms can help in constructing new ones. Some existing algorithms include: Determining the maximum or minimum value of two or more numbers. Computing the sum or average of two or more numbers. Identifying if an integer is or is not evenly divisible by another integer. Determining a robot’s path through a maze.
  • Using existing correct algorithms as building blocks for constructing another algorithm has benefits such as reducing development time, reduce testing, and simplifying the identification of errors.

Big Ideas and Vocab

  • Small changes/mistakes can have a big impact on the result
  • There is often more than one way to achieve the same result
  • Algorithm: A process or set of rules to be followed in calculations or other problem solving operations, especially by a computer.
  • Sequential Search (Inefficient search): compare each number to the number you want to find until you get to the number you want to find
  • Binary Search (Efficient search): repeats the process of finding a median and evaluating
  • Boolean Expressions: expression that evaluates to either true or false
  • Truth Tables: displays the logical operations on input signals in a table format, identifies all possible input combinations and the output for each

Comparing Algorithms

  • The algorithms below are to sum the odd numbers from 1 to 9 (1+3+5+7+9). Do they each work as intended?
  1. sum⟵1
    • counter⟵3
    • REPEAT 4 TIMES
    • sum⟵sum + counter
    • counter⟵counter + 2 - DISPLAY sum
  2. sum⟵0
    • counter⟵9
    • REPEAT UNTIL counter < 1
    • sum⟵sum + counter
    • counter⟵counter - 2 - DISPLAY sum
  • Why is it important to understand that algorithms can be written in different ways and still accomplish the same tasks? Both of them work but algorithms can differ but achieve the same result

Practice

  • Uses selection and/or iteration to determine the cost of one item in the store is correct

  • The display at the store says the following:

  • All Green Tag Items - 25% off All Red Tag Items - 60% off

  • Suppose that the tax on all items is 10%

  • Algorithm A:

    • DISPLAY (“What is the cost of the item?”)
    • cost←INPUT ()
    • IF (greenTag)
    • {
    • cost ← 0.75 * Cost
    • }
    • IF (redTag)
    • {
    • cost ← 0.40 * Cost
    • }
    • cost ← 1.10 * cost
print("What did you roll on the dice?")
diceRoll = int(input())
if diceRoll >= 4:
    print("Nice roll!")
if diceRoll >= 2 and diceRoll < 4:
    print("Meh... You can do better")
if diceRoll < 2:
    print("That was not a great roll!")

What did you roll on the dice?
Nice roll!

3.11 Binary and Sequential Search

Learning Objective:

  • For binary search algorithms
  • Determine the number of iterations required to find a value in a data set.
  • Explain the requirements necessary to complete a binary search.
  • The binary search algorithm starts at the middle of a sorted data set of numbers and eliminates half of the data; this process repeats until the desired value is found or all elements have been eliminated.
  • Data must be in sorted order to use the binary search algorithm
  • A binary search is often more efficient than sequential/linear search when applied to sorted data.

Essential Knowledge

  • Sequential Search (Inefficient search): compare each number to the number you want to find until you get to the number you want to find
  • Binary Search (Efficient search): repeats the process of finding a median and evaluating
  • Both most be in either ascending or descending order to work

Practice

  1. How many checks would it take to print out 20 using sequential search

[1, 3, 4, 5, 7, 8, 10 ,20] 7, because there are 7 other numbers

  1. How many checks would it take to print out 30 using binary search

[1, 2, 3, 4, 6, 8, 9, 11, 30] 1, because it is in the middle

Hacks

  1. Write this Boolean statement in the form of a conditional (if/else) statement: stayInside⟵((isCold) OR (isRaining))
IF (isCold or isRaining) {
    stayInside <- True
}
ELSE {
    stayInside <- False
}

  1. Create an algorithm that uses selection and/or iteration that will represent one player’s complete turn.

    During a turn, each player gets 4 attempts/chances to get the greatest number possible.

    During each attempt, the player will use a random number generator to select a random number from 1 to 10.

    After they have had 4 chances, their score is the greatest number they received from the random number generator, and their turn is over.

import random

randomNumber = []
i = 1 
while i <= 4:
    num = random.randint(0,10) 
    randomNumber.append(num)
    i = i +1 

def sort(randomNumber):
    for index in range(1,len(randomNumber)): # repeats through length of the array
        value = randomNumber[index]
        i = index - 1
        while i >= 0:
            if value < randomNumber[i]:
                randomNumber[i+1] = randomNumber[i] # shift number in slot i to the right
                randomNumber[i] = value # shift value left into slot i
                i = i - 1
            else:
                break

sort(randomNumber)
print(randomNumber)


# print("Length", len(randomNumber))
print("Maximum score:", randomNumber[len(randomNumber)-1])

[1, 3, 5, 6]
Maximum score: 6
  1. Create an algorithm that will allow the arrow to reach the gray square:
Repeat until reach gray square:

If (can_moveForward) 
    Move_Forward
Else (can_moveRight) {
    Rotate_Right
    Move_Forward
}

  1. Make a binary search tree of different the list [1,2,3,4,6,9,11,69]

  2. Explain thoroughly how to find the number 69 in the list above (use key words)

  • To find 69 in the list above, using sequential search, you would just iterate through the list, looking at each element until it matches 69. This would take 7 iterations.
  • In the binary search you would add the first index and last index and divide that by 2, and that quotient would be the position of the median. If that is not 69, then you ignore it, and examine the left and the right of that index, repeat that process until you list all of the elements.
  1. Make a diagram explaining how you found the list (not tree, include equation)
  • I do not really understand this question.
  • But I would do...
newIndex = (1+arr[len(arr)-1])/2
  • Repeating this equation until it lists out each element
  1. Put this list of strings in a order that can be used for binary search [“store”,”Market”,”Walmart”,Target”,”Ralphs”] sortedList = ["Market", "Ralphs", "store", "Target", "Walmart]
  1. Explain why Binary Search is more efficient than Sequential Search
  • Binary search is more efficient than Sequential search because it examines from midpoints of the lists over certain intervals of indices instead of looking at each element and comparing it to the target.
  • Binary search is more efficient than the linear search in the case of large data sets.
  1. [64,36,16,11,9] Explain which number you are finding, how many check it would take, and make a binary search tree