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?

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?

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)

Second block

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)
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
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
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

How can we modify this code to match our goal

Hint: uses arithmetic operations
Hint: look at the steps of the equation and try and modify it to fit them
Must display all numbers used in it

Solution

Step 1

steps/rules 2 & 3.

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

step/rule 4; here we add the loop

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

Display all values throughout the algorithm

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 = 8

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.

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

import random       # module for generating random item from a list

nums = list(range(1, 21))       # list of numbers

num1 = int(random.choice(nums))     # int takes the integer, random utilizes the module
num2 = int(random.choice(nums))     # the three numbers are generated here
num3 = int(random.choice(nums))

def end():          # procedure for endgame 
    print("Okay I guess")

rd = input("Are you ready? y/n")        # useless prompt to initiate the game       

if rd == "y":  
    print(num1)
    print("continue?y/n")       # basically a checkpoint
    cn = input()
    if cn == "y":
        print(num2)
        print("continue?y/n")
        cn2 = input()
        if cn2 == "y":
            print(num3)
            if num1 > num2 and num1 > num3:         # checks if num1 is the greatest
                print("Your Score:" , num1)
            else:
                if num2 > num1 and num2 > num3:         # checks if num2 is the greatest
                    print("Your Score:" , num2)
                else:
                    if num3 > num1 and num3 > num2:         # checks if num3 is the greatest
                        print("Your Score:" , num3)
        else:
            end()
    else:
        end()
else:
    end()

13
continue?y/n
5
continue?y/n
9
Your Score: 13