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

  • Decision problem - finding an answer
  • instance - a decision problem with an input
  • efficiency, how much a computer needs to solve a problem.
  • simplest solution
  • polynomial efficiency (good)
  • exponential efficiency (bad)
  • decided problem - decision problem solved
  • undecided problem - decision problem not solved

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.

# 1.1s after changes
# 0.8s for "evenFaster"
# 0.4s for "stupidFast"
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):
    low = 0
    high = len(array)-1
    while high >= low:
        mid = (high + low) // 2
        if array[mid] == value:
            return mid
        elif array[mid] > value:
            high = mid-1
        else:
            low = mid+1
    else:
        return False
def evenFaster(value,array):
    for a in numlist:
        for b in valuelist:
            if a == b:
                return True
    return False
def stupidFast(value,array):
    return True if value in array else False
def LMAO(value,array):
    return True if value in array else False
starttime = time.time()
for i in range(100000):
    for i in range(len(valuelist)):
        isvalue(valuelist[i],numlist)
endtime = time.time()
print(endtime-starttime,'seconds')

starttime = time.time()
for i in range(100000):
    for i in range(len(valuelist)):
        evenFaster(valuelist[i],numlist)
endtime = time.time()
print(endtime-starttime,'seconds') 

starttime = time.time()
for i in range(100000):
    for i in range(len(valuelist)):
        stupidFast(valuelist[i],numlist)
endtime = time.time()
print(endtime-starttime,'seconds')

1.1119401454925537 seconds
0.8105871677398682 seconds
0.3999779224395752 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