3.17 Algorithmic Efficiency

Vocabulary

I filled in the vocabulary below.

  • 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

  • We can check efficiency by seeing how long it takes to run a function. For example, using the time module below, we can see how long it takes to run this process one million times.
import time

def toint(x):
    x = int(x)
    return(x)

def tostr(x):
    x = str(x)
    return(x)

def add(x,y):
    x = toint(x)
    y = toint(y)
    z = x + y
    z = tostr(z)
    return(z)
starttime = time.time()
for i in range(1000000):
    x = "1"
    y = "2"
    answer = add(x,y)
print(answer)
endtime = time.time()
print(endtime-starttime,'seconds')

3
1.6013290882110596 seconds
  • There's some amount of difference between systems on efficiency. It only took me 1.6 seconds while it took the instructor's computer around 3.75 seconds.
  • In general, exponential is much less efficient than polynomial because the amount of necessary cycles increases by a lot more each time.
  • A Heuristic Approach sacrifices optimal solutions to improve efficiency and ease of programming

Challenge

We were asked to make this code more efficient using only the code between the two provided lines. I did so below by making it a binary search algorithm.

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):
    #----------
    high = (len(array) - 1)
    low = 0
    while high >= low:
        mid = (high + low) // 2
        if array[mid] == value:
            return True
        elif array[mid] > value:
            high = mid - 1
        else:
            low = mid + 1
    return 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.9853568077087402 seconds

I managed to decrease the execution time to about 0.98 seconds using binary search.

3.18 Undecidable Problems

Notes

  • The Halting Problem is essentially a paradox. Whenever a computer gets a paradoxical problem, it doesn't know when to stop trying to solve it.
    • This is the reason why computers time out when a site will not load.

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,
        'RanchoBernardo':50
    },
    'Westview':{
        'DelNorte':15,
        'MtCarmel':35,
        'Poway':25,
        'RanchoBernardo': 45
    },
    'MtCarmel':{
        'Westview':35,
        'DelNorte':20,
        'Poway':40,
        'RanchoBernardo':30
    },
    'Poway':{
        'Westview':25,
        'MtCarmel':40,
        'DelNorte':35,
        'RanchoBernardo':15
    },
    'RanchoBernardo':{
        'Westview':45,
        'MtCarmel':30,
        'Poway':15,
        'DelNorte':50
    }
}

def fastestroute(start, data):
    drivetime = 0
    order = [start]
    temploc = ""
    for i in range(len(data) - 1):
        temptime = 10000
        for loc, time in data[order[(len(order) - 1)]].items():
            if (time <= temptime) and (loc not in order):
                temploc = loc
                temptime = time
        drivetime += temptime
        order.append(temploc)
    drivetime += data[order[(len(order) - 1)]][start]
    order.append(start)
    return (drivetime, order)

start = 'DelNorte'
results = fastestroute(start, dataset)
print("Route Order:")
i = 0
while i < len(results[1]):
    print(str(i + 1) + ".", results[1][i])
    i += 1
print("Drive Time:", results[0], "minutes")

Route Order:
1. DelNorte
2. Westview
3. Poway
4. RanchoBernardo
5. MtCarmel
6. DelNorte
Drive Time: 105 minutes

To calculate the fastest route, I started by putting the start as the first entry in order. It then runs a for loop that detects the dictionary assigned to the furthest-back index of order within the given data set, finds which destination has the shortest travel time (as long as it isn't already in the order), and then adds it to the order. It ends by putting the initial destination to the end of the order.

All the while, it adds the calculated least travel time to the drivetime variable, which is returned at the end.

I made sure that it worked very efficiently, primarily running entirely through a single for loop.

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