3.17 Algorithmic Efficiency

Vocabulary

  • Problem: a general description of a task that can or cannot be solved algorithmically
  • Decision Problem: A problem with a yes or no answer
  • Organization Problem: a problem with a goal of finding the best answer
  • Instance: a problem with a specific input
  • Efficiency: amount of computing needed to solve a problem
  • Polynomial Efficiency (Good): more work takes a proportional amount of time (1 job is +2 time)
  • Exponential Efficiency (Bad): more work takes an exponential amount more time (1 job is 2x time)
  • Heuristic Approach: When optimal solutions are inefficient, look for a possibly optimal solution that is more efficient
  • Decidable Problem: A decision problem that has a clear solution that will always make a correct output
  • Undecidable Problem: A decision problem with no solution that is not gaurenteed to produce the correct output

Notes

  • different levels of polynomial efficiency
  • less code makes efficiency higher
  • polynomial=linear increase
  • exponential=exponential increase

Challenge

Try and fix this ineficcient code! Only change the code between the two commented lines. Fully programmed solution will improve your grade, at a minimum show that you tried.

import time
numlist = [1,3,5,7,9,11,13,15,17,19]
valuelist = [0,3,6,9,12,15,18,21]
def isvalue(value,array):
    #--------------------
    exists = False
    #--------------------
starttime = time.time()
for i in range(100000):
    for i in range(len(valuelist)):
        x = isvalue(valuelist[i],numlist)
endtime = time.time()
print(endtime-starttime,'seconds') 

0.11729001998901367 seconds

3.18 Undecidable Problems

Notes

  • paradoxes are made by contradicting statements
  • paradoxes will keep going forever

Homework!

Make an algorithm that finds the fastest route that hits every location once starting and ending at Del Norte. Make sure to show your thinking. If you are strugling, try using a huristic approach. Remember, what matters more than having perfectly functioning code is that you tried your hardest.

dataset = {
    'DelNorte':{
        'Westview':15,
        'MtCarmel':20,
        'Poway':35,
        'RanchoBernrdo':50
    },
    'Westview':{
        'Del Norte':15,
        'MtCarmel':35,
        'Poway':25,
        'RanchoBernrdo': 45
    },
    'MtCarmel':{
        'Westview':35,
        'Del Norte':20,
        'Poway':40,
        'RanchoBernrdo':30
    },
    'Poway':{
        'Westview':25,
        'MtCarmel':40,
        'Del Norte':35,
        'RanchoBernrdo':15
    },
    'RanchoBernardo':{
        'Westview':45,
        'MtCarmel':30,
        'Poway':15,
        'Del Norte':50
    }
}

#didn't understand how to do this I tried to many different things and couldn't complete it. I have spent over 2 hours on this

Grading:

Challenge Homework
.15 pts for attempt .65 for attempt
.20 pts for complete .70 for complete
.25 pts for above and beyond .75 pts for above and beyond