Vocab

  • algorithms: a process of set of rules to be followed through code
  • flowcharts: help us visualize the functionality of an algorithm
  • binary Search Algorithm: a search algorithm that finds the position of a target value within a sorted array

Algorithms

  • An algorithm is a process or set of rules to be followed through CODE
  • Set limitations
  • 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?
# when I inputted 54, the output was "It is too cold outside!"
# when I inputted 95, the output was "It is too hot outside!"

It's too hot outside!

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?
# # when I inputted 54, the output was "It is too cold outside!"
# when I inputted 95, the output was "It is too hot outside!" AND "Sure I will play outside!"

It's too hot outside!
Sure I will play outside!

Conditionals vs. Booleans

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

Flowcharts

  • help us visualize the functionality of an algorithm
  • good way to double check whether or not the 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

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

Combining Algorithms

benefit of combining algorithms:can reduce development time, testing time, and simplify the identification of errors

Rules of Collatz Conjecture

  1. start with any positive integer
  2. if the preceding term is even; divide by 2
  3. if the preceding term is odd; multiply by 3 and add 1
  4. repeat steps until you arrive at 1
  5. 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

choose value for x
the number is odd

Binary Search Algorithm

  • a search algorithm that finds the position of a target value within a sorted array
  • compares the target value to the middle element of the array.
  • algorithm for iterating to find a value inside a data set
  • starts in the middle of a data set of numbers and eliminates half the data. This process repeats until the desired value is found or until all elements have been eliminated
  • In order to use binary search effectively and properly, data must be stored in order
  • must set numbers in an increasing or decreasing order

How Binary Search Works

Binary Search finds the desired element by continuously chopping the search area in half

Example

[a b c d e f g h] , we are looking for the element f

  1. start in the middle at element d
  2. our target element is greater than d, so we will eliminate everything to the left of d including d

[a b c d e f g h] --> [e f g h]

  1. chop in half again, and when we iterate through we'll have to eliminate g and h
  2. eliminate g and h

[e f g h] --> [e f]

  1. chop in half again to get the desired element

[e f] --> [f]

binary_search() Function

  • Made up of 2 arguments:
    • A list to be sorted
    • A number to be searched
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

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