Algorithms can be written in different ways and still accomplish the same tasks. Algorithms that look similar often yield differnet outputs. To solve the same problem, many different algorithms can be used.

Therefore, algorithms are very important for programmers, and today we're going to explore how to determine the outcome of algorithms, how to deteremine the output of similar algorithms, how to edit existing algorithms, and how to develop our own algorithms.

Determine the outcome of algorithms

Consider the following algorithm.

def mystery(num, num2):
    if (num % num2 == 0):
        print("True")
    else:
        print("False")

mystery(20, 4)
True
  1. What does the algorithm do? Please explain in words.

The algorithm determines whether or not the number is divisible by 2. It

  1. What if I put in 30 as num and 4 as num2. What would be the output?

The output would be "False"

Determine the outcome of similar algorithms

What is the output of this algorithm?

It is too hot outside

temp = 95
if (temp >= 90):
    print("it is too hot outside")
else:
    if (temp >= 65):
        print("I will go outside")
    else:
        print("it is too cold outside")
it is too hot outside

What is the output of this algorithm? it looks similar but the output is different!

temp = 10
x = "it is too hot outside" # define it as x and command all of the functions to print x
if (temp >= 90):
    print(x)
elif (temp >= 65): # turn it into an elif to get the desired output
    print(x)
if (temp < 65):
    print(x) # All results will yield "it is too hot outside"
it is too hot outside

Editing Algorithms

Task: Please edit the algorithm above to have it yield the same results as the previous algorithm! (no matter what temp you put in)

Developing Algorithms

To develop algorithms, we first need to understand what the question is asking. Then, think about how you would approach it as a human and then try to find what pattern you went through to arrive at the answer. Apply this to code, and there you have it! An algorithm!

Let's say you wanted to sum up the first five integers. How would you do this in real life? Your thought process would probably be:

  • The sum of the first integer is 1.
  • Then, increase that integer by 1. I now add 2 to my existing sum (1). My new sum is 3.
  • Repeat until I add 5 to my sum. The resulting sum is 15.

Now let's translate this into code.

sum = 0 # start with a sum of 0
for i in range (1, 6): # you will repeat the process five times for integers 1-5
    sum = sum + i # add the number to your sum
print(sum) # print the result
15

Task: Write an algorithm in python that sums up the first 5 odd integers. You can use the following code as a starter.

sum = 0
counter = 1
for i in range (0, 5): # integers 0-5 for first 5 odd integers 
    sum = sum + counter # so that it will loop 5 times
    counter = counter + 2 # to make it odd if it begins at 1, then 3, then 5, and so on
    print(sum) # print result
1
4
9
16
25

Homework

Create an algorithm that will start with any positive integer n and display the full sequence of numbers that result from the Collatz Conjecture. The COllatz Conjecture is as follows:

  1. start with any positive integer
  2. if the number is even, divide by 2
  3. if the number is odd, multiply by 3 and add 1
  4. repeat steps 2 and 3 until you reach 1

Example: if the starting number was 6, the output would be 6, 3, 10, 5, 16, 8, 4, 2, 1

n = int(input('enter any positive integer: ')) # prompting user to input the positive integer (n) of their choosing
print (n)
while n >= 1: # if it is greater than or equal to 1
    if n % 2 == 0: # determining whether the integer is even with modulo operator
        n = int(n / 2) # dividing by 2 in that case
    elif n % 2 != 0: # determining whether the integer is odd
        n = int(n*3 + 1) # multiplying by 3 and adding one in that case
    print (n)
    if n == 1:
        break # breaking the loop and printing the sequence of numbers when it is 1
30
15
46
23
70
35
106
53
160
80
40
20
10
5
16
8
4
2
1

Challenges and Homework

You have one homework problem.

Yes just one.

Don't get excited though.

Problem: Given a specific integer N, return the square root of N (R) if N is a perfect square, otherwise, return the square root of N rounded down to the nearest integer

Input: N (Integer)

Output: R (Integer)

Constraints: Do not use any built-in math operations such as sqrt(x) or x**(0.5), Try complete the problem in logarithmic time.

Hint 1: Maybe you can use Binary Search to try and reduce the number of checks you have to perform?

Hint 2: Is there a mathematical pattern amongst numbers and their square roots that could help you reduce the number of searches or iterations you must execute? Is there some value or rule you can set before applying binary search to narrow the range of possible values?

def sqrt(n):
    low = 0 # lowest value is 0
    high = n # highest value is the integer itself, this will narrow the range of possible values (thanks hint!)
    if n > 1: 
        high = (n // 2) # dividing in half to narrow the value range even more
    while high >= low:
        x = (high + low) // 2 # this is what will divide the integer and round it to a whole number
        if (x**2) == n: # This determines whether x is the square root of n
            return x
        elif (x**2) > n: 
            high = x - 1
        else:
            low = x + 1
    return n  
    # I could not get it to print :|
    # I tried "print(sqrt(n)) and print(n) but in both cases it said n was not defined for some reason"
from math import sqrt as sq
test_cases = [0,1,4,85248289,22297284,18939904,91107025,69122596,9721924,37810201,1893294144,8722812816,644398225]
answers = [int(sq(x)) for x in test_cases]

def checkValid():
    for i in range(len(test_cases)):
        if sqrt(test_cases[i]) == answers[i]:
            print("Check number {} passed".format(i+1))
        else:
            print("Check number {} failed".format(i+1))

checkValid()
Check number 1 passed
Check number 2 passed
Check number 3 passed
Check number 4 passed
Check number 5 passed
Check number 6 passed
Check number 7 passed
Check number 8 passed
Check number 9 passed
Check number 10 passed
Check number 11 passed
Check number 12 passed
Check number 13 passed