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?

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 is too cold 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?
It is too cold outside!

Examples

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

Example 2

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

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.

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 even

Step 1

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)
choose value for x
7

Step 2

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)
choose value for x
1.0

Step 3

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
8
4.0
2.0
1.0
1.0

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.

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

HW

import random

num1 = random.randint(1,20)

num2 = random.randint(1,20)

num3 = random.randint(1,20)


def NumberGame():
    print("You got:", num1, num2, num3)
    if num1 > num2 and num1 > num3: 
        print("Your score is", num1)
    else:
        if num2 > num3:
            print("Your score is", num2)
        else:
            print("Your score is", num3)

NumberGame()
You got: 17 12 20
Your score is 20

Here is a link to my google drawing of the algorithm. Thank you for grading.