Unit 3.9 & 3.11
- Unit 3.9
- Unit 3.11 Binary Search (Claire)
Unit 3.9
3.9.1 Algorithms (Claire)
A little review on Algorithms:
what are the three components of an algorithm?
- selection
- sequence
- iteration
Today we will be looking at algorithms from another standpoint.
Main Idea 1: Algorithms can be written in different ways and still do the same thing
- However, Algorithms that look similar might not always have the same result
- Different algorithms can be used to solve the same problem
Examples
The goal with the two algorithms below is to show "Wow! Good job!" when you get an A and show "Nice!" when you get a B or C (pass), if you don't pass (lower than 70) it will show "Do Better"
print("What Grade Did You Get?")
grade = int(input("Enter Grade:"))
if grade >= 90:
print("Wow! Good job!")
if 70 <= grade < 90:
print("Nice!")
elif grade < 70:
print("Do Better")
Yay! it worked! Lets look at the next one. Do you notice any differences? Do you think this algorithm will still achieve the same goal? If not, what is the flaw?
print("What Grade Did You Get?")
grade = int(input("Enter Grade:"))
if grade >= 90:
print("Wow! Good job!")
elif 70 < grade < 90:
print("Nice!")
elif grade < 70:
print("Do Better")
So, why is this important? Why are we even doing this?
When 2 algorithms look extremely similar, it is easy to assume they do the same thing. However, that is not the case and we have learn how to notice small differences in code and pretty much debug.
- just know that codes that look similar don't always produce the same things :)
Real-life situation (Storytime)
Tommy and Billy are working on solving the same issue with an algorithm
Tommy creates a functioning code and yells "I did it!"
He looks over at his friend Billy which is having a bit of trouble and he offers help
However, Billy's code looks basically the same! which confuses them
Then they remeber that they were taught that algorithms that look similar don't always have the same results and they collaborate to do further investigation:)
Now, without running, investigate the algorithm below. This one looks different. Do you thing it will still achieve the same goal as above?
print("What Grade Did You Get?")
grade = int(input("Enter Grade:"))
A = grade >= 90
B = 70 <= grade < 90
C = grade < 70
if A:
print("Wow! Good job!")
elif B:
print("Nice!")
elif C:
print("Do Better")
Why is this important?
When collaborating or working on group projects, two people might come up with two different ways to solve a problem, and that happens a lot.
- know that same goal can be achieved in many ways (the possibilities are endless)
- make notes in you code! (explain how it works to others or you future self)
isHoliday = False
isWeekday = True
#if holiday, dont go to school
if isHoliday == True:
print("don't go to school!")
# otherwise, if it is a weekday, go to school
else:
if isWeekday == True:
print("go to school!")
# but if it is neither a weekday or holiday, don't go to school
else:
print("don't go to school")
isHoliday = False
isWeekday = True
# setting variables here (same as above to make comparison easier)
driveSchool = not(isHoliday) and isWeekday
if driveSchool == False:
print("don't go to school!")
if driveSchool == True:
print("go to school!")
# now we can make a regular conditional/ if statement without having a nested conditional
3.9.2 Developing Algorithms (Annika)
Developing Algorithms
- When creating an algorithm, its good to outline its process before coding
- This ensures that it is sequenced correctly
- You should represent the algorithm using a flowchart or natural language
- Visualization can help you better see the flow of the whole algorithm
- This may allow for the coding process to be more efficient and effective
Review of Selection and Iteration
- Algorithms with iteration repeat a function until a goal is reached
- To more easily represent an algorithm without showing all the repeated steps, we can use iteration
- Algorithms with selection only go through certain functions if certain things are true or false
Example 1
- Start
- The number of pretzels in the pack is 6
- Eat one pretzels, number of pretzels in pack goes down by 1
- How many pretzels are left?
- Repeat step 3 until number of pretzels is 0
- Display that pack is empty
- Finish
pretzel = 6
while (pretzel > 0):
pretzel -= 1
print(pretzel)
if pretzel == 0:
print("All done!")
Example 2
The parking rate for a garage is as follows:
Less than one hour: Free
1-2 hours: $5 <br>
2-3 hours: $8
3-4 hours: $10 <br>
4+ hours: $12
- Start
- Input number of hours parked
- If hours is less than 1, cost is free
- If hours is between 1 and 2, cost is $5
- If hours is between 2 and 3, cost is $8
- If hours is between 3 and 4, cost is $10
- If hours is more than 4, cost is $12
- Display cost and goodbye
- Finish
print("The parking rate is as follows: \n Less than one hour: Free \n 1-2 hours: $5 \n 2-3 hours: $8 \n 3-4 hours: $10 \n 4+ hours: $12")
time = float(input("How many hours have you parked at this garage?"))
print("How many hours have you parked at this garage?")
print(time, "hours costs:")
if time < 1 :
print("Free")
elif time >= 1 and time < 2 :
print("$5")
elif time >= 2 and time < 3 :
print("$8")
elif time >= 3 and time < 4 :
print("$10")
else:
print("$12")
print("Have a good day!")
Hacks
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
3.9.3 Using preexisting algorithms (Grace)
Main Idea
- Knowing existing algorithms can help construct new ones
- simple existing algorithms can include
- determining min or max of two or more numbers
- computing the sum or average
- identifying if an integer is even or odd
- Using existing correct algorithms can help as building blocks to reduce development time, testing, and identification of errors
Create an algorithm that will start with any positive integer n and display the full sequence of numbers that result from following the Collatz Conjecture.
Example: 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
What does this function do?
if (n MOD 2 = 0)
{
display("n is even")
}
else
{
display("n is odd")
}By modifying the preexisting code, we can write create new code that follows th Collatz Conjecture.
DISPLAY ("Choose a value for n")
n <- INPUT ()
REPEAT UNTIL (n = 1)
{
IF (n MOD 2 = 0 )
{
n <- n/2
}
ELSE
{
n <- n * 3 + 1
}import random
#sets variables for the game
num_guesses = 0
user_guess = 0
upper_bound = 100
lower_bound = 0
#generates a random number
number = random.randint(1,100)
# print(number) #for testing purposes
print(f"I'm thinking of a number between 1 and 100.")
#Write a function that gets a guess from the user using input()
def guess():
#add something here
return #add something here
#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 guess < number:
print("You are bad at guessing") #change this
lower_bound = guess
elif guess > number:
print("You suck :(") #change this
upper_bound = 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)
print(f"Guess a number between {lower_bound} and {upper_bound}.")
print(f"You guessed the number in {num_guesses} guesses!")
Unit 3.11 Binary Search (Claire)
Binary Search:
repeatedly dividing a search interval in half
Binary Search Steps:
- first put the numbers in order
- ascending
- descending
- find the middle number first
- this is found by taking the highest index number plus the lowest index number and divide by 2
- the numbers on the right will be greater and the numbers on the left will be smaller
- this can be represented with a binary tree
- middle number with the smaller number branched off on the left and bigger numbers branched off on the right
- middle number with the smaller number branched off on the left and bigger numbers branched off on the right
- this is found by taking the highest index number plus the lowest index number and divide by 2
- these lists are not always numbers
- lists can be made with strings
- ex. ["apple", "banana", "cherry", "peach", "watermelon"]
- alphabetical order
- a-z
- z-a
Practice:
- What is the middle number in a Binary Search given the following set of numbers in order: 1, 5, 19, 44, 89
- 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
Hacks:
- 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
- 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?
-
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"]
Rubric:
All 4 hacks are graded the same way
0.25/0.25 - shows full understanding of the lesson, completes all hacks assigned with explanation to go above and beyond, any extra hacks to show more understanding
0.23/0.25 - shows understanding of algorithms/binary search and completes all hacks
0.20/0.25 - does not understand algorithm/binary search and has not completed hacks