Developing 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 algorithim sees if the first mystery number is divisible by 4. Since 20 is divisible by 4, it prints true.
- What if I put in 30 as num and 4 as num2. What would be the output? False since 30 is not perfectley divisible by 4.
Additional Algorithim Notes
- Algorithms are specific steps designed to accomplish a certain task
- In developing algorithms, it is crucial to understand what algorithim is doing
Editing Algoirthims: Task: Please edit the algorithm above to have it yield the same results as the previous algorithm! (no matter what temp you put in)
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")
Task: Write an algorithm in python that sums up the first 5 odd integers. You can use the following code as a starter.
n = 9
sum = 0
for i in range(1,n+1):
if i%2!=0:
sum+=i
print(sum)
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:
- 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 cc(n):
while n > 1:
print(n, end=' ')
if (n % 2):
n = 3*n + 1
else:
n = n//2
print(1, end='')
n = int(input('Enter n: '))
print(end='')
cc(n)
Java Script
To determine if two conditionals and booleans are the same, you can substitute the four possibilities that the two booleans (sunny and rainy) can be (listed below) into the conditional and boolean and see if both cases match:
- sunny = true, rainy = true
- sunny = true, rainy = false
- sunny = false, rainy = true
- sunny = false, rainy = false
Challenge
Using JavaScript, create an algorithm that takes in an IP address and a subnet mask and computes the network address.
Overview
As we've seen in Unit 4.1, an IP address is a 32 bit number that uniquely identifies each device. (See this for a recap). Something extra is that an IP address also comes with a subnet mask. A subnet mask is also a 32 bit number that identifies what network an IP address in in through a process that uses the bitwise AND.
In ANDing:
0 + 0 = 0
0 + 1 = 0
1 + 0 = 0
1 + 1 = 1
The following are the steps to determine the network that an IP address is in given the subnet mask:
Example: IP address: 192.168.0.1
Subnet mask: 255.255.255.0
- Convert the IP address into binary: 192.168.0.1 -> 11000000.10101000.00000000.00000001
- Convert the subnet mask into binary: 255.255.255.0 -> 11111111.11111111.11111111.00000000
- Do a bitwise AND operation on the binary IP address and subnet mask:
11000000.10101000.00000000.00000001
+11111111.11111111.11111111.00000000
=11000000.10101000.00000000.00000000- Convert the result back to decimal: 11000000.10101000.00000000.00000000 -> 192.168.0.0
The network address is 192.168.0.0
Binary Search
Notes on seqeuential search:
- Searching when it comes to computer programs and applications involves locating and retrieving a data value/and or its index
- Although for selection sort is fast for smaller inputs, it cannot keep up with increasing input sizes.
- Because sequential search checks every value of the given array, the algorithm's overall runtime increases
Notes on Binary Search
- an efficient way to iterate through a sorted list to find a value.
- This is done through checking the middle value of a list and checking if the requested value is greater than or less than the middle value
- If list is not sorted, binary search algorithm will not work
- In every iteration the algorithm is making a binary decision; if the selected element is larger or smaller than the target
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?
Run the very last code segment below to load test cases and submission function
def sqrt(N):
x = N
y = (x+1) // 2
while y < x:
x = y
y = (x + N //x) //2
return x
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()