3.17 - 3.18 Hacks
Hacks
Come up with one situation in which a computer runs into an undecidable problem. Explain why it is considered an undecidable problem.
An example of an undecidable problem is determining how many even numbers exist. There are an infinite number of even numbers, so the algorithm would just keep running forever and producing higher and higher values.
3.17 Homework
Your homework for Algorithmic Efficiency is pretty simple.
- Use the 1st code below and graph it (Desmos, TI Inpire Cas, e.t.c), change the x value only! (Plot 5 Points Minimum)
- Label the number of loops done as x and the time (microseconds) to find the index as y
- Connect the points
- Do the same thing with the 2nd code
- Compare the two graphs and explain which one of the two is more efficient and why (min. 2 sentences)
- Insert images of the graph either in your blog or on review ticket
import time
def linear_search(lst, x):
start_time = time.perf_counter_ns() # records time (nanoseconds)
for i in range(len(lst)): # loops through the entire list
if lst[i] == x: # until the x value we are looking for is found
end_time = time.perf_counter_ns() # records time again
total_time = (end_time - start_time) // 1000 # subtracts last recorded time and first recorded time
print("Found element after {} loops in {} microseconds".format(i+1, total_time)) # prints the results
return print("Your number was found at", i)
end_time = time.perf_counter_ns() # records the time again
total_time = (end_time - start_time) // 1000 # subtracts last recorded time and first recorded time
print("Element not found after {} loops in {} microseconds".format(len(lst), total_time)) # prints the results
return "Your number wasn't found :("
lst = list(range(1, 10001)) # list with numbers 1-10000
x = 3000 # replace with an integer between 1 and 10000 (I suggest big numbers like 500, 2000, so on)
linear_search(lst, x) # runs procedure
import time
def binary_search(lt, x):
start_time = time.perf_counter_ns() # starts timer
low = 0 # sets the lower side
mid = 0 # sets mid value
high = len(lt) -1 # sets the higher side
num_loops = 0 # number of loops the search undergoes to find the x value
while low<=high: # Loop ran until mid is reached
num_loops += 1 # adds one loop each time process is repeated
mid = (low + high) // 2 # takes the lowest and highest possible numbers and divides by 2 and rounds to closest whole #
if lt[mid] == x:
end_time = time.perf_counter_ns() # records time
total_time = (end_time - start_time) // 1000 # time in microseconds
print("Element found after {} loops in {} microseconds".format(num_loops, total_time)) # prints the results
return mid # returns the index value
elif lt[mid] > x: # if mid was higher than x value, then sets new highest value as mid -1
high = mid -1
elif lt[mid] < x:
low = mid + 1 # if mid was lower than x, sets the new low as mid + 1
end_time = time.perf_counter_ns()
total_time = (end_time - start_time) // 1000
print("Element not found after {} loops in {} microseconds".format(num_loops, total_time)) # prints the results
return "Your number wasn't found :("
lt = list(range(1, 10001)) # list with numbers 1-10000
x = 149 # replace with an integer between 1 and 10000 (I suggest big numbers like 500, 2000, so on)
binary_search(lt, x) # runs procedure
3.18 Homework:
- Use the Jupyter notebook to write an algorithm that solves a decidable problem. You can use math or whatever else you would like to do.
- Write code to get the computer to run forever. Check this example if you need help, but please come up with your own idea.
Homeworks, hacks, and classwork(filled in blanks) for both 3.17 and 3.18 are due on Thursday at 9:00 pm. -0.1 points for each day late.
def checkEven(number):
if number % 2 == 0:
print(str(number) + " is even")
else:
print(str(number) + " is not even")
print(checkEven(30))
print(checkEven(15))
i = 0
number = 1
def integerTest(n):
# Testing if the number is an integer
if n%1 ==0:
return True
else:
return False
# Using while loop to keep searching an a non-integer above 1. Note that the computer runs forever.
while i == 0:
number += 1
if integerTest(number) == False:
i +=1
print("Done")