Algorithm Lesson
Unit 3 Sections 9-11
- 3.9 Part 1
- 3.9 Part 2
- 3.9 Part 3
- 3.11 Binary Search
- Homework Assignment (DUE FRIDAY 12/09 BY 5:00 PM)
3.9 Part 1
The lesson will start off with introducing what algorithms are and what they do, moreover, what their significance is.
3.9 Lesson 1 has the objective to teach the student of the outcome of similar algorithmic concepts and similar algorithms. In this lesson, you will see different ways on how algorithms are developed.
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?
The pseudocode above is translated to python for you.
Record what your outputs are when you enter 95 degrees F, does the algorithm yield the same result?
The conditional below is nested
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?
# It will print that it is too cold to play outside
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?
# It will print that it is too hot to play outside
temp = int(input("Select a temperature from 0 to 99 degrees F"))
if (temp >= 90):
print("It's too hot outside!")
elif (temp >= 65):
print("Sure I will play outside!")
else:
print("It is too cold outside!")
# Input 54 and then Input 95, what do you notice?
# It prints that is both too hot to be outside and that it'll play out side this could be corrected with the above changes
# If 54 was inputted it would correctly print that it is too cold to play outside
NOW RECORD with another output
Record what your outputs are when you enter 54, does the algorithm yield the same result this time?
*Now use 95 as an input for the two code blocks above.
Even though an algorithm's code can look the same, you have to be careful, they can always yield different results. When constructing algorithms you want to make sure that your code corresponds with what you want as your output. You set the limit of your code and you decide what the code's output is.
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.
Exercise
Learning how to utilize conditionals and booleans are important for developing algorithms. Use this exercise to help you.
Can either Boolean expression on the right replace the conditional on the left? Assume isWeekday and isHoliday are Boolean variables.
*NOTE = you can edit the variables to check the conditions needed!
IsHoliday = False
IsWeekday = True
if IsHoliday:
driveWork = True
else:
if IsWeekday:
driveWork = True
else:
driveWork = False
print(driveWork)
Logically thinking about conditionals and booleans
Now the problem may seem confusing, but the best way to develop an algorithm is to think about all the possible results that can be potentially be outputted.
So if IsHoliday is set to true, then driveWork is automatically equal to false and it does not matter what value of isWeekday is. This must mean that one of the conditionals must be NOT IsHoliday.
In the case that lets say IsHoliday is set to false, then the variable for weekday needs to be checked. If it's true then driveWork is true, if it's false then driveWork is false. This must mean that the other conditional isWeekday.
Combining both conditionals, you get option 2, which is not IsHoliday and IsWeekday. This is why option 2 is right!
Example 3 | Conditionals vs Booleans
The following algorithms are intended to sum the odd numbers from 1-9. Which algorithms work as intended?
Below, I have translated the block code into python, import this to your jupyter notebook and record the result. What do you notice?
First block
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)
When we start our initializing left sum as 1 counter as 3 we had no iterations yet. Remember we're going to have to repeat this four times because the block code prompts us to repeat 4 times, so we iterate. So as we go through and follow what the block gives us.
So you see that the sum does work, it does sum up the odd numbers from 1-9
Now lets look at the right block.
Sum is set to 0 Counter is set to 9 We must repeat until the counter < 1 is true.
So we keep adding until -1, that is when the counter < 1 is true, so we stop
So why is it important to understand that algorithms can be written in different ways and still accomplish the same task?
An algorithm is beautiful that way, just because you think of solving a problem differently, doesn't mean your wrong,
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
How To Set Up A Flowchart
-
label the start point
-
Define any and all variables you may need
-
Consider the first question you want the algorithm to ask
-
Write what you want the algorithm to do if the answer to that question is yes (or true)
-
Write what you want the algorithm to do if the answer to that question is no (or false)
- Steps 3-5 are the steps to creating code that uses a process called selection (you can convert the question from step 3 to a conditional if-statement in code)
- Steps 3-5 are the steps to creating code that uses a process called selection (you can convert the question from step 3 to a conditional if-statement in code)
-
Write out all necessary steps for the algorithm to function properly
-
You may want your algorithm to iterate some steps until a condition is met
- You can write the steps that need to be repeated, then draw an arrow from the last step to a step above that contains a conditional statement
- You can write the steps that need to be repeated, then draw an arrow from the last step to a step above that contains a conditional statement
- determine a way to reach the end goal
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
-
-
Example A
-
Consider this situation:
-
You are shopping for your favorite food at your favorite supermarket
-
You see that there is a sale on wheat products for 35% off
-
There is another sale on produce for 20% off
-
These sales are mutually exclusive
-
Tax on all items is 8%
-
-
Your TASK:
- Create a flowchart for an algorithm that can be used to calculate the cost of your favorite item
Example A Possible Solution (using Selection)
3.9 Part 3
- For Algorithms
- How to combine and/or modify an existing algorithm.
- Benefits of combining algorithms
- can reduce development time, testing time, and simplify the identification of errors.
Example in Class
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.
Algorithm to Start (Determining Whether a Number is Even or Odd)
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
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
Think about how you would you would try to find a certain number in this set.
One way would be to line up the numbers and count them individually untill you find the desired value.
When working with large data sets with lots of numbers, methods like these wont work
- Instead, a Binary Search would be more effective.
Here we can see the numbers are set in an increasing order. Setting numbers in an increasing or decreasing is needed for a binary search
- Binary search is started with the middle number first
- Middle number is found by taking the higest index number plus the lowest and divided by two
- Binary Search can be represented using a tree as shown below
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")
-
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 BinarySearcher(sortedlist, x):
beginning = 0
mid = 0
end = len(sortedlist)-1
while beginning <= end:
mid = (beginning+end)//2
if sortedlist[mid] == x:
return mid
elif sortedlist[mid] > x:
end = mid - 1
else:
beginning = mid + 1
return -1
x = int(input("Integer to search through"))
sortedlist = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
result = BinarySearcher(sortedlist,x)
if result != -1:
print("Element is present at index " + str(result))
else:
print("Not found")
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)
-
Try to implement selection and/or iteration in your algorithm
-
Please do this using Google Drawing. It can be found in your Google Drive if you click
New > More > Google Drawings
-
-
Write the working algorithm in Python
-
Make sure to initialize / define any variables you may need
-
Add comments to your code!
-
How to submit:
-
Make a shareable link to your Flowchart with commenting access through Google Drive's "Share" feature
-
Make a comment with the link at the top of the code block that holds your algorithm (use
#for comments in Python) -
Submit a link to your algorithm (with the commented link to Flowchart) in the comment/issue found on the schedule
Grading
-
DUE FRIDAY 12/09 BY 5:00 PM
-
LATE PENALTY: -0.2
-
You will be graded based on:
-
how functional your algorithm is
-
how well your Flowchart is organized Tirth Thakkar FlowChart
-
If something comes up, feel free to DM us on Slack
import random
def game():
num_rounds = int(input("Rounds: "))
player1_score = 0
player2_score = 0
for i in range(num_rounds):
player1_numbers = (random.randint(1, 20), random.randint(1, 20), random.randint(1, 20))
player2_numbers = (random.randint(1, 20), random.randint(1, 20), random.randint(1, 20))
if max(player1_numbers) > max(player2_numbers):
print("On round "+ str(i+1) +" Player 1 won with a score of " + str(max(player1_numbers)) + " compared to Player 2 with a score of " + str(max(player2_numbers)))
elif max(player1_numbers) < max(player2_numbers):
print("On round "+ str(i+1) +" Player 2 won with a score of " + str(max(player2_numbers)) + " compared to Player 1 with a score of " + str(max(player1_numbers)))
else:
print("Both players tied with a score of " + str(max(player1_numbers)) + " on round " + str(i))
game()