Unit 3 Lesson 17 - 18 Hacks and Notes
Algorithm Efficiency and Undecidable Problems
Notes:
-
Collatz: The Collatz conjecture is one of the most famous unsolved problems in mathematics. The conjecture asks whether repeating two simple arithmetic operations will eventually transform every positive integer into 1.
-
Hailstone numbers: The sequence of integers generated by Collatz conjecture are called Hailstone Numbers. Examples:Input : N = 7 Output : Hailstone Numbers: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 No.> ### Iteration The action or a process of iterating or repeating:such as. : a procedure in which repetition of a sequence of operations yields results successively closer to a desired result.
-
Undecidable problems: An undecidable problem is one that should give a "yes" or "no" answer, but yet no algorithm exists that can answer correctly on all inputs.
-
Unsolvable problems: An unsolvable problem is one for which no algorithm can ever be written to find the solution.
def collatz(i):
while i != 1:
if i % 2 > 0:
i =((3 * i) + 1)
list_.append(int(i))
else:
i = (i / 2)
list_.append(int(i))
return list_
print('Please enter a number: ', end='' + "\n")
while True:
try:
i = int(input())
list_ = [i]
break
except ValueError:
print('Invaid selection, try again: ', end='')
l = collatz(i)
print('Sequence: ')
print(*l, sep=" ")
print('Number of iterations:', len(l) - 1)
Inefficient:
numbers = [100,99,98,97,96,95,94,93,92,91,90]
diff = numbers[0] - numbers[1] - numbers[2] - numbers[3] - numbers[4]- numbers[5] - numbers[6] - numbers[7] - numbers[8] - numbers[9] - numbers[10]
print(diff)
Efficient:
numbers = [99,98,97,96,95,94,93,92,91,90]
diff = 100
for i in numbers:
diff -= i
print(diff)
The first one is less efficient than the second one because the inefficient one has to be done by individually typing each number. On the other hand the second algorithm uses a for loop to subtract which makes it easier for the person writing the code and it is less redundant.
tasks = ["shower", "brush teeth", "skincare", "sleep"]
def complete_tasks(tasks):
for task in tasks:
if task == "shower":
print("Take a shower!")
elif task == "brush teeth":
print("Go brush your teeth!")
elif task == "skincare":
print("Do your skincare!")
elif task == "sleep":
print("Go to bed!")
complete_tasks(tasks)