Essential Knowledge

--


Examples

  1. What is the middle number in a Binary Search given the following set of numbers in order: 1, 5, 19, 44, 89
  1. What is the middle number in a Binary Search given the following set of numbers that are not in order: 3, 87, 12, 66, 22

Nested Conditionals

  • why is it important to know that algorithms that look different can do the same thing and that algorithms that look the same might have different results?(0.15)
  • for the converted conditional to boolean conversion(0.10)
  • total: 0.25
LotsOfMoney = True
Broke = True

if LotsOfMoney == True and Broke == False:
    print("earn more money")
else:
    if Broke == True:
        print("go to work")
    else:
        print("earn more money")

# Boolean conversion
work = not(LotsOfMoney) or LotsOfMoney and Broke
if work == True:
    print("go to work and earn more")
if work == False:
    print("rich person")
go to work
go to work and earn more

Complex Algorithms

Develop your own complex algorithm using a flowchart and natural language, then code it!

Requirements:

  • Includes both a flowchart AND natural language
  • Working code of the same algorithm
  • Incorporates selection AND/OR iteration
  • Make it creative!

Tips:

  • This site is good for making flowcharts!
  • Natural language should just be a list
  • Think about the whole process, not just the end result

START

money = 45
while (money > 0):
    money -= 30
    print(money)
    if money == 0:
        print("go back to work")
15
-15

Number Game

Fix the number guessing game

  1. Make a flow chart for the algorithm number guessing game
  2. Make a function that gets the user guess
  3. Modify the existing search function to give more encouraging feedback
import random

#sets variables for the game
num_guesses = 0
user_guess = -1
upper_bound = 101
lower_bound = 0

#generates a random number
number = random.randint(1,101)

# print(number)     #for testing purposes
print("test 5")

print("I'm thinking of a number between 1 and 100.")

#Write a function that gets a guess from the user using input()

def guess():
    gnum = input("choose a number between 1 to 100")
    return gnum 

#Change the print statements to give feedback on whether the player guessed too high or too low
def search(number, guess):
    global lower_bound, upper_bound
    if int(guess) < int(number):
        print("too low") #change this
        lower_bound = guess
        return lower_bound, upper_bound
    elif int(guess) > int (number):
        print("too high") #change this
        upper_bound = guess
        return lower_bound, upper_bound
    else:
        upper_bound, lower_bound = guess, guess 
        return lower_bound, upper_bound

while user_guess != number:
    user_guess = guess()
    num_guesses += 1
    print(f"You guessed {user_guess}.")
    lower_bound, upper_bound = search(number, user_guess)
    if int(upper_bound) == int(number):
        break
    else:
        print(f"Guess a number between {lower_bound} and {upper_bound}.")

print(f"You guessed the number in {num_guesses} guesses!")
test 5
I'm thinking of a number between 1 and 100.
You guessed 30.
too low
Guess a number between 30 and 101.
You guessed 60.
too low
Guess a number between 60 and 101.
You guessed 80.
You guessed the number in 3 guesses!

  1. calculate the middle index and create a binary tree for each of these lists
    • 12, 14, 43, 57, 79, 80, 99
    • 92, 43, 74, 66, 30, 12, 1
    • 7, 13, 96, 111, 33, 84, 60
index = [12, 14, 43, 57, 79, 80, 99]
index.sort()
mid = int(len(index) / 2) 
print(mid)
print("middle",index[mid])
3
middle 57
index =[92, 43, 74, 66, 30, 12, 1]
index.sort()
mid = int(len(index) / 2) 
print(mid)
print("middle",index[mid])
3
middle 43
index = [7, 13, 96, 111, 33, 84, 60]
index.sort()
mid = int(len(index) / 2) 
print(mid)
print("middle",index[mid])
3
middle 60
  1. Using one of the sets of numbers from the question above, what would be the second number looked at in a binary search if the number is more than the middle number?

In the third set of numbers, the second number looked at in a binary search if it is more than the middle number would be 96

  1. Which of the following lists can NOT a binary search be used in order to find a targeted value?

    a. ["amy", "beverly", "christian", "devin"]

    b. [-1, 2, 6, 9, 19]

    c. [3, 2, 8, 12, 99]

    d. ["xylophone", "snowman", "snake", "doorbell", "author"]

answer d [is not sorted]