3.9 and 3.11 Lesson
3.9 Part 1
Lesson 1 | Defining Algorithms
What is an algorithm? An algorithm is a process or set of rules to be followed through CODE.
-
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.
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?
Conditionals vs. Booleans
The condition and instructions are what differ, that's where the magic happens. The condition is a boolean expression when an expression outputs either true or false. Boolean values are another type of data type in programming languages, and they can only ever hold true or false.
IsHoliday = False
IsWeekday = True
if IsHoliday:
driveWork = True
else:
if IsWeekday:
driveWork = True
else:
driveWork = False
print(driveWork)
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)
3.9 Part 2
Flowcharts
-
Flowcharts can help you visualize the functionality of an algorithm
-
They are a good way to double check whether or not your algorithm is achieving its purpose
Selection vs. Iteration
-
Selection:
-
A process used in algorithms where a conditional if-statement leads to one of two outcomes
-
Outcome 1: if the conditional statement is true, something will happen
-
Outcome 2: if the conditional statement is false, something else will happen
-
Ex: see Example A
-
-
-
Iteration
-
A process used in algorithms that allows certain things to happen until a condition is satisfied
-
Once the condition is satisfied, then an outcome is produced
-
This can take the form of a for-loop, while-loop, and/or if-statement
-
-
print("choose value for x")
varx = int(input("Enter any positive Integer"))
new = 0
while (new != 1):
if (varx %2 == 0):
new == varx / 2
print("your new number is: " + str(new))
else:
new == varx * 3 + 1
print("Your new number is " + str(new))
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)
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)
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
Takeaways
- You can use code you've previously wrote in order to make a project easier.
- Breaking algorithms down into steps can make things easier and more simple.
Hacks
- create another algorithm using a famous mathematical algorithm such as the "collatz conjecture." and explain your steps in a post on a blog.
3.11 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
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")
-
We have created a function called binary_search() function which takes two arguments - a list to be sorted and a number to be searched.
-
We have declared two variables to store the lowest and highest values in the list. The lowest is assigned initial value to 0, the highest to len(list1) 1 and mid as 0.
-
Next, we have declared the while loop with the condition that the lowest is equal and smaller than the highest. The while loop will iterate if the number has not been found yet.
-
In the while loop, we find the mid value and compare the index value to the number we are searching for.
-
If the value of the mid-index is smaller than n, we increase the mid value by 1 and assign it to the low. The search moves to the left side.
-
Otherwise, if the value of mid index is larger than n, we decrease the mid value by 1 and assign it to the high. The search moves to the right side.
-
If the n is equal to the mid value then return mid.
-
This will happen until the low is equal and smaller than the high.
-
If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.
Hacks
Using my example above and steps below, create your own iteration using binary search
Steps
- Compare x with the middle element.
- If x matches with the middle element, we return the mid index.
- Else if x is greater than the mid element, then x can only lie in the right (greater) half subarray after the mid element. Then we apply the algorithm again for the right half.
- Else if x is smaller, the target x must lie in the left (lower) half. So we apply the algorithm for the left half.
def binary_search(arr, x):
low = 0
high = len(arr)-1
mid = 0
if low<=high:
mid = (low + high) // 2 #integer part
if x == arr[mid]:
return mid
elif x < arr[mid]:
high = mid - 1
return high
else:
low = mid + 1
return low
else:
return -1
arr = [1,2,3,4,5,6,7,8,9,10,11]
x = 11
result = binary_search(arr, x)
if result != -1:
print("Found at position : ",str(result))
else:
print("Not in the array!")
Homework Assignment (DUE FRIDAY 12/09 BY 5:00 PM)
-
Consider this situation:
-
You're playing a short game using a random number generator from 1 to 20
-
On each turn, a player will generate 3 random numbers
-
They get to keep the highest number that they generate as their score
-
-
Your TASK:
-
Create a flowchart that can be used to write an algorithm that calculates a player's score after a turn
- NOTE: Don't forget the syntax for Flowcharts! (each shape represents an action)
https://docs.google.com/drawings/d/1ofUBFenlmnreeF1W4Y8ZuEizLodMV6FNycQRQRarGbs/edit?usp=sharing
-
Write the working algorithm in Python
-
Make sure to initialize / define any variables you may need
-
Add comments to your code!
-
import random
Num = []
Score = 0
num1, num2, num3 = random.sample(range(1, 20), 3) #generates a random number and equates it to num1, num2, and num3
Num.extend([str(num1), str(num2), str(num3)]) #adds num1, num2, and num3 to the list ‘Num’
for i in Num: #iterates through each number in the list Num
newScore = (max(map(int, Num))) #map makes the list a list of integers. uses max syntax to find the largest number in the list Num.
print("You rolled the numbers " + str(Num) + ". Your score is: " + str(newScore)) ##prints new score