Lesson 17 and 18 Unsolvable Problems

Secton 17

  • Unsolvable problem: There is no code that can be written that will give an answer.
  • Undecidable problem: There is no code that can find the answer, but there is an answer, just too complex.
  • undecidability example is that there is no way to prove the collatz conjecture as true for all real numbers or if it is false.
  • Hailstone numbers is the list of numbers returned by running the Coltaz code.
  • Algorithm Efficiency measures how many steps it takes to complete an algorithm where less steps means more efficient.
  • Algorithms can make life easier

Hacks

Unit 3 Section 18

  • Take the two codes above and combine them so one imput gives the output that contains both the hailstone numbers and the number of iterations it takes i = 1. The more efficient the code, the higher your grade will be. (Algorithm Efficency) (.25)
def collatz(i):
    while i > 1:
        if (i % 2):
            i = 3*i + 1
            list_.append(i)
        else:
            i = i//2
            list_.append(i)
    return list_


print('Please enter a number:')
while True:
    try:
        k = int(input())
        list_ = [k]
        break
    except ValueError:
        print('Invaid selection, try again: ', end='')


l = collatz(i)

print('Number of iterations:', len(l) - 1)
print('Sequence: ', end='')
print(*l, sep=" ")

Please enter a number: 
Number of iterations: 5
Sequence: 32 16 8 4 2 1

Unit 3 Section 17 Hacks

  • Write 2 algorithms: One is efficent and one is innefficent, then explain why one is efficent while the other isn't. (.25)
fruit1 = "apple"
fruit2 = "banana"
fruit3 = "grape"
fruit4 = "strawberry"
print(fruit1, fruit2, fruit3, fruit4)

apple banana grape strawberry

fruits = ["apple", "banana", "grape", "strawberry"]
print(fruits)

['apple', 'banana', 'grape', 'strawberry']

The first example was inefficient as I had to define each fruit while and print each one. but the second example is much more efficient as I was able to create a list of fruits and print the list.

  • Explain why one algorithm is more efficient than another using mathematical and/or formal reasoning. (.25)
  • One way that an algorithm is more efficient than another is if one completes the task quicker than the other. If two algorithms complete the same task yet one can do it in half the time, that algorithm is more efficient as it saves time.
  • use variables, if statements, and loops to program your algorithm and upload to jupyter notebooks/ fastpages. (.25)
fruits = ["apple", "banana", "grape", "strawberry"]
x = "strawberry"
def search(fruits, x):
    for i in range(len(fruits)):
        if fruits[i] == x:
            print("I have not found the strawberry yet")
            return True
    return False
if search(fruits, x):
    print("I found the strawberry")

I have not found the strawberry yet
I found the strawberry