Homework/Challenges and Notes for 3.9 and 3.11
Here is the homework that we were assigned to do for 3.9 and 3.11, as well as some notes that I took from the lesson.
- 3.11 Developing Algorithms (Python)
- 3.9 Binary Search Introduction
- 3.9 Developing Algorithms (JavaScript)
- Important Notes for Lessons 3.9 and 3.11
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.
Consider the following algorithm.
def mystery(num, num2):
if (num % num2 == 0):
print("True")
else:
print("False")
mystery(20, 4)
- What does the algorithm do? Please explain in words. The algorithm essentially prints true if the remainder of the two numbers (%) is equal to 0. Otherwise, if the remainder is not 0, False will be printed.
- What if I put in 30 as num and 4 as num2. What would be the output? False because the remainder of 30 and 4 is not equal to 0. 30/4 = 7.5, which means that these two numbers do not go into each other evenly.
What is the output of this algorithm? "It is too hot outside" would be the output of this algorithm because 95 is greater than or equal to 90.
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")
What is the output of this algorithm? it looks similar but the output is different! There will be two things: "It is too hot outside" and "I will go 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")
temp = int(input("Please enter a temperature in degrees Fahrenheit"))
if (temp >= 90):
print(f'{temp} degrees outside. It is too hot!')
if (temp >= 65 and temp <= 90):
print(f'{temp} degrees outside. I will go outside!')
if (temp < 65):
print(f'{temp} degrees outside. It is too cold!')
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
sum = 0
for i in range (1, 10, 2):
sum = sum + i
print(sum)
Homework 3.11 (Algorithms in Python)
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:
- start with any positive integer
- if the number is even, divide by 2
- if the number is odd, multiply by 3 and add 1
- 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
def collatz(num: int) -> int:
# if the number is even and its remainder when divided by 2 is 0, the user's original input will be divided by 2
if num % 2 == 0:
return num // 2
# otherwise, if the input is an odd positive number, that number will be multiplied by 3 and have 1 added to it
else:
return 3 * num + 1
while True:
# prompts for a positive number
num = int(input('Please enter a positive integer: '))
# if the user types in a valid input, the collatz conjecture will come into play beginning from that inputted value
if num >= 0:
print("Starting Value: ",num)
break
# If the user tries to input a negative number, the code will prompt them with this and allow them to try again.
else:
print("Invalid input. Please try again and enter a positive integer:")
# the collatz conjecture continues to perform its necessary operations on the numbers until it finally reaches 1
while num != 1:
num = collatz(num)
print(num)
print("That's all folks!")
What is searching?
In certain computer programs and applications, one might find the need to locate and retrieve a data value and/or it's index. Searching algorithms could be done in either intervals or sequences, and certain algorithms could be more efficient than others, with benefits and drawbacks to each.
3.9 Binary Search Introduction 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.
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?
Run the very last code segment below to load test cases and submission function
from math import sqrt as sq
def sqrt(N: int) -> int:
low = 0
high = N
while low <= high:
mid = (low + high) // 2
if mid * mid <= N:
low = mid + 1
else:
high = mid - 1
return low - 1
from math import sqrt as sq
# these are all of the numbers that will be tested on to see if each one passes the test
test_cases = [0,1,4,85248289,22297284,18939904,91107025,69122596,9721924,37810201,1893294144,8722812816,644398225]
# these are the expected values for the square root of each number
answers = [int(sq(x)) for x in test_cases]
def checkValid():
for i in range(len(test_cases)):
# if the number from test_cases returns the expected value from the answers, it will print that the check number [number] has passed
if sqrt(test_cases[i]) == answers[i]:
print("Check number {} passed".format(i+1))
# if the number from test_cases does not return the expected value from the answers list, it will print that the check number [number] has failed
else:
print("Check number {} failed".format(i+1))
# calls the checkValid() function
checkValid()
3.9 Developing Algorithms (JavaScript)
As much as I would have liked to try the challenge of making an algorithm that takes in an IP address and a subnet mask and computes the network address, my JavaScript kernel has continued to not be working properly. I have tried several solutions that I found online to fix the problem, but no matter what I have tried, it still does not work. Although my kernel does not work, here is how I would have tried to go about doing this challenge (note: no output is shown since the kernel doesn't work)
Update: My JavaScript Kernel has just started working, but even when I run the code, I still get that there is a syntax error in how I declared the function "computeNetworkAddress". I have tried looking up solutions to this problem online and have tried them, but I still get the same error no matter what.
function computeNetworkAddress(ipAddress, subnetMask) {
// Convert the IP address and subnet mask to binary
var binaryIpAddress = convertToBinary(ipAddress);
var binarySubnetMask = convertToBinary(subnetMask);
// Perform a bitwise AND operation on the binary IP address and subnet mask
var networkAddressBinary = binaryIpAddress & binarySubnetMask;
// Convert the result back to decimal
var networkAddress = convertToDecimal(networkAddressBinary);
// Return the network address
return networkAddress;
}
function convertToBinary(address) {
// Split the address into its octets
var octets = address.split(".");
// Convert each octet to binary
var binaryOctets = octets.map(function(octet) {
return parseInt(octet).toString(2);
});
// Concatenate the binary octets into a single binary string
return binaryOctets.join("");
}
function convertToDecimal(binary) {
// Split the binary string into octets
var binaryOctets = binary.match(/.{1,8}/g);
// Convert each binary octet to decimal
var octets = binaryOctets.map(function(binaryOctet) {
return parseInt(binaryOctet, 2);
});
// Concatenate the octets into a single decimal string
return octets.join(".");
}
var ipAddress = "192.168.0.1";
var subnetMask = "255.255.255.0";
var networkAddress = computeNetworkAddress(ipAddress, subnetMask);
console.log(networkAddress); // Output: "192.168.0.0"
3.9 Binary Search Notes
- Searching when it comes to computer programs and applications involves locating and retrieving a data value/and or its index
- Searching algorithms can be done in intervals or sequentially
- Sequential Search - checks every value of the given array
- Cannot keep up with increasing input sizes, as the longer the array, the more time that it will take for the search to check
- In other words, as the input lists gets larger, the runtime of the program increases "linearly" as well
- Binary Search - a more efficient way to check through a sorted list to find a specific value
- Involves checking the medium or middle value of a list and checking if the requested value is higher or lower than the middle value
- If the list is not sorted or in a proper order, the binary search algorithm cannot work anymore
- The maximum number of cycles in a binary search is equivalent to the log base 2 of the closest, next power of 2, to the length of the list
- When it comes to execution time, using the binary search method will overall take less time than using the sequential search method and is therefore more efficient and worthy of one's time
3.11 Algorithms (Can be Applied to both Python & JavaScript) Notes
- Algorithms are specific steps designed to accomplish a certain task
- In developing algorithms, it is crucial to understand what the question is asking
- Example: if one wanted to sum up the first five integers, they would probably think about how...
- The sum of the first integer is 1
- Increase that integer by 1 before adding 2 to the existing sum. At this point, the new sum is 3
- This process would be repeated until 5 is added to the sum. To recap, this thought process would look something like this for humans:
- 1+2+3+4+5 = 15
- The resulting sum of the first five integers is 15.
Here is what this thought process would look like in Python:
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