Developing Algothims (Python)

An algorithm is a set of actions that are taken to achieve a certain result. There are many algorithms that can be used to achieve a certain result.

Determining Outcomes

Below are some cells that we had to determine the outcomes of.

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 checks if the first number num is evenly divisible by the second number num2, and if it is, prints "True". If else, it prints false.

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

The output would be "False", as 30 is not evenly divisible by 4 (since 30 / 4 = 7.5).

Editing Algorithms

See the code cells below.

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

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

it is too hot outside
i will go outside

We were asked to edit the second algorithm to make it the same as the first and to make it work with any number. Here it is:

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

it is too hot outside

And this shows that it works the same with any number:

import random
temp = random.randrange(30, 100)
print("The temperature is {} degrees.".format(temp))
if (temp >= 90):
    print("it is too hot outside")
elif (temp < 65):
    print("it is too cold outside")
else:
    print("i will go outside")

The temperature is 71 degrees.
i will go outside

Task

We were given this code as an example. It is supposed to do this:

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

We are expected to make an algorithm to add up the first five odd integers. I did it with the step aspect of the range function.

sum = 0
for i in range(1, 11, 2): #skips from 1 to 3, 5, 7, and finally 9 (11 is the cap)
    sum = sum + i
print(sum)

25

Homework

We were asked to use an algorithm to make the Collatz Conjecture. Conditions:

  • Start with any positive integer
  • If the number is even, divide by 2
  • The number is odd, multiply by 3 and add 1
  • Repeat steps 2 and 3 until you reach 1
integer = 5

while integer != 1:
    if (integer % 2 == 0):
        integer = int(integer / 2)
    else:
        integer = (integer * 3) + 1
    print(integer)

16
8
4
2
1

Developing Algorithms (JavaScript)

This is the same basic concept as before but in JavaScript. Vocab carries over. I skipped review becauses it's all review and I'm solid on it.

Conditionals vs. Booleans

Conditionals can be used in conjunction with Booleans. This is a cell from their lesson.

sunny = true;
rainy = false;
if (sunny) {
    umbrella = false; 
} else if (rainy) {
    umbrella = true; 
} else {
    umbrella = false; 
}

console.log(umbrella);

It is the same as this.

umbrella = !sunny && rainy;

console.log(umbrella);

A way to check if they're the same is to see if the outputs of the four possibilities result in the same outcomes.

Challenge

We were asked as an extra credit challenge to create a system that uses an IP address and a subnet mask to determine a network address. Here is my working JavaScript code.

const IP = "251.84.0.1";
const SNM = "255.255.255.0";

function DecimalToBinary(deci) {
    var i = 7;
    var binary = "";
    while (i >= 0) {
        if (deci % (2**i) === deci) {
            binary += "0";
            i -= 1;
        } else {
            binary += "1";
            deci -= 2**i;
            i -= 1;
        };
    };
    return binary;
};

function BinaryToDecimal(bin) {
  var i = 0;
  var deci = 0;
  while (i < 8) {
    if (bin[i] === "1") {
      deci += (2**(7 - i));
    };
    i += 1;
  };
  return deci
};

function AddressToBinary(ad) {
  tempdeci = "";
  templist = [];
  binaddress = "";
  for (let i = 0; i < ad.length; i++) {
    if (ad[i] !== ".") {
      tempdeci += ad[i];
    } else {
      templist.push(tempdeci);
      tempdeci = "";
    };
  };
  templist.push(tempdeci);
  for (let i = 0; i < templist.length; i++) {
    binaddress += DecimalToBinary(Number(templist[i]));
    if (i < 3) {
      binaddress += ".";
    };
  };
  console.log(binaddress);
  return binaddress;
};

function AddressToDecimal(ad) {
  tempdeci = "";
  templist = [];
  deciaddress = "";
  for (let i = 0; i < ad.length; i++) {
    if (ad[i] !== ".") {
      tempdeci += ad[i];
    } else {
      templist.push(tempdeci);
      tempdeci = "";
    };
  };
  templist.push(tempdeci);
  for (let i = 0; i < templist.length; i++) {
    deciaddress += BinaryToDecimal(templist[i]);
    if (i < 3) {
      deciaddress += ".";
    };
  };
  console.log(deciaddress);
  return deciaddress;
};

function NetAddressConvert(ip, snm) {
  tempnetadd = "";
  ip = AddressToBinary(ip);
  snm = AddressToBinary(snm);
  for (let i = 0; i < 35; i++) {
    if((ip[i] === "1") && (snm[i] === "1")) {
      tempnetadd += "1"
    } else if (ip[i] === ".") {
      tempnetadd += ".";
    } else {
      tempnetadd += "0";
    };
  };
  console.log(tempnetadd);
  tempnetadd = AddressToDecimal(tempnetadd);
  return tempnetadd;
};

NetAddressConvert(IP, SNM)

11111011.01010100.00000000.00000001
11111111.11111111.11111111.00000000
11111011.01010100.00000000.00000000
251.84.0.0

How it Works

I know it's pretty complicated and I didn't make any code comments, but here's how it works.

I made four functions for convenience, two being ones I already made (though one was just in Python before): DecimalToBinary(), which converts a decimal input to 8-bit binary; BinaryToDecimal(), which converts an 8-bit binary input to decimal; AddressToBinary(), which converts an IP address or subnet mask from decimal to binary; and AddressToDecimal(), which converts an IP address or subnet mask from binary to decimal.

The NetAddressConvert() function that satisfies the conditions of the assignment takes a decimal IP address and decimal subnet mask (in any order) as parameters, converts them to binary, then procedurally creates the network address by checking (using &&) if both bits at a certain index on the IP and subnet mask are "1" (adding a "1" if true), and if they aren't, it adds a "0" to the network address. Where there are periods in the IP, to ensure the same formatting, a period is placed in the network address.

The example above uses 251.84.0.1 as the IP address and 255.255.255.0 as the subnet mask. The program works with all other IP addresses and subnet masks, however, as long as they stay within the legitimate bounds of 8-bit binary.

Searching Introduction

Searching algorithms exist to find data in a program. This can be done with sequences or intervals.

Here is an example of a sequential search algorithm.

def sequentialSearch(arr, target):
    N = len(arr)                     # Declare N as length of array
    for i in range(N):               # Iterate over the list
        if arr[i] == target:         # Check for match
            return i                 # Match found, return index and end function call
    return -1                        # Element not found

Binary search essentially checks for how close data is relative to what is being looked for. If an array exists and looks like this ([1, 2, 3, 4, 5, 6, 7]) (and it's important for it to be ordered in this case), a search that is looking for 6 and starts in the middle (returns 4), the program knows 4 < 6 and would loop only further up. Same if it was a lower number.

Copied from their blog:

This algorithm is extremely efficient as the maximum number of cycles in binary search is equal to log base 2 of the closest, next power of two, to length of list.

If the array is 8 items long, the maximum possible cycles would be 3 (log base 2 of 8 is 3)

If the array is 7 items long, the maximum possible cycles would STILL be 3 as the closest power of 2 to 7 is 8.

If the array is 9 items long, the maximum possible cycles INCREASES to 4, as the closest, next power of two, is 16."

Here's a code example they provided:

def binarySearch(array, target):
    low = 0
    high = len(array)-1
    while high >= low:
        mid = (high + low) // 2 #floor division, rounds it down to the nearest whole
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            high = mid-1
        else:
            low = mid+1
    return False

And here it is in action.

examplearray = [3, 4, 5, 6, 7, 8, 9, 10, 11]
binarySearch(examplearray, 11)

8

Here's a version of it in a recursive loop. We already talked about converting between while and recursive loops, so no need to go crazy over it. It requires more parameters.

def BinarySearchRecursion(arr, target, lo, hi):
    if lo > hi:
        return False
    mid = (lo+hi)//2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return BinarySearchRecursion(arr, target, lo, mid-1)
    elif arr[mid] < target:
        return BinarySearchRecursion(arr, target, mid+1, hi)

Homework

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.

Run the very last code segment below to load test cases and submission function.

def sqrt(N):
    low = 0
    high = N
    if N > 1:
        high = (N // 2)
    while high >= low:
        mid = (high + low) // 2 #floor division, rounds it down to the nearest whole
        if (mid**2) == N:
            return mid
        elif (mid**2) > N:
            high = mid - 1
        else:
            low = mid + 1
    return False   

print(sqrt(49))

7

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

Explanation

I used binary search by setting the low to 0 and the high to the target squared (N), and mid started with half of that squared number (rounded). Mid moves up/down based on how the squared number compared to the number in question squared.

The Process

I started by making a system that listed all values between 0 and the number in question, which obviously took a lot longer because that process had to run before the search. I then tried a sequential search, which made it take even longer and felt a whole lot more amateur.

I talked with Alex and realized how stupid the list thing was. I ended up just using the number that was being rooted as the high for a binary search and checked the units between 0 and it squared.