3.17 Algorithmic Efficiency

Vocabulary

  • Problem:
    • Decision Problem:
    • Organization Problem:
  • Instance:
  • Efficiency:
    • Polynomial Efficiency (Good):
    • Exponential Efficiency (Bad):
  • Heuristic Approach:
  • Decidable Problem:
  • Undecidable Problem:

Notes

  • _

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
    while exists == False:
        for i in range(len(array)):
            if value == array[i]:
                exists = True
        if exists == False:
            return exists
    return exists
    #--------------------
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') 

6.984534740447998 seconds

3.18 Undecidable Problems

Notes

  • _

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
    }
}

def fastestroute(start,data):
    drivetime = 0
    order = []
    #CODE,CODE,CODE
    return(drivetime,order)

start = 'DelNorte'
# 'dataset' is the name of the nested key value pair

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