9 and 11 Notes
Notes for 9 and 11.
- Lesson 1 | Defining Algorithms
- Example 1 | What happens if we test the algorithm with different outputs?
- Examples
- Example 2
- Binary Search
- HW
Lesson 1 | Defining Algorithms
What is an algorithm? An algorithm is a process or set of rules to be followed through CODE. There are set limitations, this is what makes algorithms fun, you can your imagination and create whatever you wan with your own instructions!
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 the same as Boolean expressions (VICE VERSA)
Different algorithms can be developed or use to solve the same problem.
Example 1 | What happens if we test the algorithm with different outputs?
temp = int(input("Select a temperature from 0 to 99 degrees F"))
if (temp >= 90):
print("It's too hot outside!")
else:
if (temp >= 65):
print("Sure I will play outside!")
else:
print("It is too cold outside!")
# Input 54 and then 95, what do you notice?
temp = int(input("Select a temperature from 0 to 99 degrees F"))
if (temp >= 90):
print("It's too hot outside!")
if (temp >= 65):
print("Sure I will play outside!")
if (temp < 65):
print("It is too cold outside!")
# Input 54 and then Input 95, what do you notice?
sum = 1
counter = 3
#iteration
var = 0
while (var < 4): #while the var is <= 4, it executes those commands, once it exceeds it hits the else command
sum = sum + counter
counter = counter + 2
var = var + 1
# now go through the whole thing 4 times, this is an iteration, a vital part of algorithms.
else:
print(sum)
sum = 0
counter = 9
#iteration
while (counter >= 1):
sum = sum + counter
counter = counter - 2
print(sum)
Rules step/rule 1: start with any positive integer step/rule 2: if the preceding term is even; divide by 2 step/rule 3: if the preceding term is odd; multiply by 3 and add 1 step/rule 4: repeat steps until you arrive at 1 fact: the sequence should ALWAYS end up at 1 if repeated.
print("choose value for x")
varx=int(input("Enter any positive Integer"))
if (varx %2 == 0):
print("the number is even")
else:
print("the number is odd")
# Run this cell to see how it works
Step 1
print("choose value for x")
varx=int(input("Enter any positive Integer"))
if (varx %2 == 0):
varx == varx/2 # Change print to the function
else:
varx == varx * 3 + 1 # Change print to the function
print(varx)
Step 2
print("choose value for x")
varx=int(input("Enter any positive Integer"))
while varx != 1:
if (varx %2 == 0):
varx = varx/2 # Change print to the function
else:
varx = varx * 3 + 1 # Change print to the function
print(varx)
Step 3
print("choose value for x")
varx=int(input("Enter any positive Integer"))
print(varx)
while varx != 1:
if (varx %2 == 0):
varx = varx/2
print(varx) # add Display
else:
varx = varx * 3 + 1
print(varx) # add Display
print(varx) # Final # Should be 1 every time
Binary Search
Goals/Objectives:
- detirmine number of iterations required to find vlue in data set.
- explain requirements for binary search
What is Binary Search?
- Binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.
- An algorithm for iterating to find a value inside a data set
About Binary Search:
- Binary Search Algorithm starts in the middle of a data set of numbers and eliminates half the data. This process reapeats until the desired value is found or until all elements have been eliminated.
- In order to use binary search effectivly and properly, data must be stored in order
COLLEGE BOARD INDEX STARTS AT 1 NOT 0
Think about how you would you would try to find a certain number in this set.
Heres an easy way to put it:
- binary search fidns the desired element by continuously chopping the search area in half
-
say the element you are looking for is 'f' [a b c d e f g h]
-
We would start in the middle at element 'd'
- becuase our target is greater than d we will eliminate everything left of 'd' including 'd' (chopping it in half)
[e f g h] is what now remains
- again we would 'chop in half'
- say we iterate through 'g' and 'h', our desired element is still not found so we would eliminate 'g; and 'h' and continue the process [e f]
now we are down to 2 elements 'chopping in half' will give us our desired element [f]
def BinarySearch(array, x, low, high):
# Repeat until the pointers low and high meet each other
while low <= high:
mid = low + (high - low)//2 # find the middle (taking the higest index number plus the lowest and divided by two)
if array[mid] == x: # if desired number is the middle is found return desired number (middle number)
return mid
elif array[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
array = [3, 4, 5, 6, 7, 8, 9]
x = 4
result = BinarySearch(array, x, 0, len(array)-1)
if result != -1:
print("Element is present at index " + str(result))
else:
print("Not found")
import random
num1 = random.randint(1,20)
num2 = random.randint(1,20)
num3 = random.randint(1,20)
def NumberGame():
print("You got:", num1, num2, num3)
if num1 > num2 and num1 > num3:
print("Your score is", num1)
else:
if num2 > num3:
print("Your score is", num2)
else:
print("Your score is", num3)
NumberGame()
Here is a link to my google drawing of the algorithm. Thank you for grading.