First Things First: WGET

  • wget allows you to essentially clone someone elses file on Github into a directory of your choosing
    • You are able to edit your own copy of the file without affecting the original

Here's a quick how-to

  1. Open your VSCode terminal (Terminal > New Terminal)

  2. Navigate to your Fastpages Blog using cd

  3. Navigate to the _notebooks directory in your Fastpages

  4. Copy and paste this into the terminal: wget https://raw.githubusercontent.com/Azeem-Khan1/TripleAJ/master/_notebooks/2022-12-06-lessonComplete.ipynb

  5. You're all set! you can use this copy of our notebook to help you take notes and participate during the lesson

    • Please raise your hand if you are having trouble with wget and we will come around and help you
  • Note: if you have a separate notebook that you take notes on and you also want to do your practice in that notebook, you can copy and paste cells from this notebook by left clicking next to any markdown or code cell (indicating that it is selected), do ctl+c or cmd+c, and go to the desired notebook and do ctl+v or cmd+v (if that doesn't work, try just c and v with no ctl or cmd)

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?

print("Input: ")
print(temp)

temp1 = int(input("Select a temperature from 0 to 99 degrees F"))
if (temp1 >= 90):
    print("It's too hot outside!")
else:
    if (temp1 >= 65):
        print("Sure I will play outside!")
    else: 
        print("It is too cold outside!")

print("Input: ")
print(temp1)

It is too cold outside!
Input: 
54
It's too hot outside!
Input: 
95

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?

print("Input: ")
print(temp)

temp1 = int(input("Select a temperature from 0 to 99 degrees F"))
if (temp1 >= 90):
    print("It's too hot outside!")
if (temp1 >= 65):
    print("Sure I will play outside!")
if (temp1 < 65):
    print("It is too cold outside!")
    # Input 54 and then Input 95, what do you notice?

print("Input: ")
print(temp1)

It is too cold outside!
Input: 
54
It's too hot outside!
Sure I will play outside!
Input: 
95

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)

25

Second block 

sum = 0
counter = 9
#iteration
while (counter >= 1): 
    sum = sum + counter
    counter = counter - 2
print(sum)

25

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

  1. label the start point

  2. Define any and all variables you may need

  3. Consider the first question you want the algorithm to ask

  4. Write what you want the algorithm to do if the answer to that question is yes (or true)

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

  6. Write out all necessary steps for the algorithm to function properly

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

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

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) 

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

the number is even

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

4

Step 2

  • step/rule 4; here we add the loop
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)

1.0

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

choose value for x
6
3.0
10.0
5.0
16.0
8.0
4.0
2.0
1.0
1.0

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

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

Element is present at index 1

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] # index 0,1,2,3,4,5,6
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")

Element is present at index 5

  • 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

Your TASK:

  1. 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

  1. Write the working algorithm in Python

    • Make sure to initialize / define any variables you may need

    • Add comments to your code!

How to submit:

  1. Make a shareable link to your Flowchart with commenting access through Google Drive's "Share" feature

  2. Make a comment with the link at the top of the code block that holds your algorithm (use # for comments in Python)

  3. 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.1

  • You will be graded based on:

    • how functional your algorithm is

    • how well your Flowchart is organized

If something comes up, feel free to DM us on Slack

HW 

import random

score = 0

num1 = random.randint(1, 20)
num2 = random.randint(1, 20)
num3 = random.randint(1, 20)

highest = max(num1, num2, num3)

score = highest 

print("Random Generated Numbers:")
print(num1, num2, num3)
print("The highest number aka the score:")
print(score)

Random Generated Numbers:
3 2 20
The highest number aka the score:
20

Hacks 1: 

def binary_search(array, x):
    low = 0
    mid = 0
    high = len(array) - 1

    while low<=high:
        mid = (low + high) // 2 
        
        if x == array[mid]:
            return mid
        elif x < array[mid]:
            high = mid - 1
            return high
        else:
            low = mid + 1
            return low
    else:
        return -1

array = [3,4,5,6,7,8,9,10,11,12,13]
x = 12

result = binary_search(array, x)

if result != -1:
    print("Found at position : ",str(result))
else:
    print("Not in the array!")