Notes:

  • An algorithm can be made more efficient by reducing the number of steps needed to accomplish the task
    • This is why different correct algorithms for the same problem can have different efficiencies
  • A way to informally measure an algorithm's efficiency is by determining the number of times a statement or group of statements executes
  • Approximate solutions are found when problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them
  • It is possible for there to be some solutions to an input of an undecidable problem

Vocab:

  • Four Types of Algorithms:
    • 1 Step: An integer being multiplied by a variable
    • 2 Step: An integer to the power of the variable
    • 3 Step: A variable multiplied by an integer, all raised to the power of 2
    • 4 Step: A variable factorial
  • Decidable Problems: Problems for which algorithms could be written to solve/produce a correct output for all inputs.
  • Undecidable Problems: Problems for which no algorithms can be built that can provide a correct yes or no answer or a solution
  • Constant Time: Algorithm that always takes a fixed number of steps, no matter how large the input size increases
  • Linear Time: Algorithm in which the number of steps increases in direct proportion to the input size
  • Quadratic Time: Algorithm where the number of steps increase in proportion to the input size squared
  • Exponential Time: Algorithm where the number of steps increases faster than a polynomial function of the input size
  • Polynomial Time: Any run time that does not increase faster than n^k
  • Superpolynomial Time: Any run time that does increase faster than n^k
  • Reasonable Time: Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.)
  • Unreasonable Time: Algorithms with exponential or factorial efficiencies

HACK 1

Please write a short 1-2 sentence explanation describing the difference between decidable and undecidable problems. Make sure to provide at least one example of each.

Decidable Problem: Decidable problems are problems for which algorithms can be written to produce an output for all possible inputs.

Example:

a = True

if a == True:
    print("hello")
else:
    print("bye")

hello

Undecidable Problem: Undecidable problems are problems for which no algorithm can be built that can provide a correct yes or no answer. It is possible for there to be some algorithmic solutions for some inputs of an undecidable problem.

Example (Halting Problem):

def haltingProblem():
    a = 0 
    x = 1
    while a != 1:
        x = x + 1
        print(x)

haltingProblem()

HACK 2

Which of the following is a 3 step algorithm?

A. 2 x 6 x 8

B. 4^5

C. (3 x 8)^2

D. None of the above

E. All of the above

☆ My answer: The correct answer is C. This is because a 3 step algorithm needs to have an integer variable multiplied by another integer which is all raised to the power of 2 and (3 x 8)^2 meets these requirements.

HACK 3: Rewrite this JavaScript Code in a More Efficient Way (Hint: Use Binary Search) 

function peak_finder(array){
  let counter = 0
  let peak = 0
  let peak_index =0
  while (counter <= array.length){
    console.log(counter)
  if (counter === 0){
    if (a[0]>=a[1]){
      peak = a[0]
      peak_index = counter
      counter = array.length
      return `The ${counter-1} indexed number, ${peak} is a peak`
    }else{
      counter+=1
    }
  }else if(counter === array.length-1){
     if (a[array.length-1] >= a[array.length-2]){
     peak = a[array.length-1]
     peak_index = counter
     counter = array.length
     return `The ${counter-1} indexed number, ${peak} is a peak`
     }
   }else{
      if (a[counter]> a[counter+1] && a[counter]> a[counter-1]){
      peak = a[counter]
      peak_index = counter
      counter = array.length
      return `The ${counter-1} indexed number, ${peak} is a peak`
    }else{
      counter += 1
    }
  }
}
}

Rewritten Code: 

function peak_finder(list) {
  var peak = list[0];
  for (i = 0; i < list.length; i ++) {
    if (list[i] > peak) {
      var peak = list[i];
    }
  }
  return peak; # after all comparisons, returns highest value in list
}

var data = [5, 2, 3, 4, 9];
console.log(peak_finder(data)); # prints highest number in list (9)

Hack 3 Reflection:

This hack was a little confusing because I wasn't sure how to use binary search to make the code more efficient. Instead, since I'm pretty sure the code is supposed to find the highest number in a list, I made code that compares elements in the list to each other to determine the highest value in the list.

HACK 4: Rewrite this Python Code in a More Efficient Way 

def merge_sort(data):
    if len(data) <= 1:
        return
    
    mid = len(data) // 2
    left_data = data[:mid]
    right_data = data[mid:]
    
    merge_sort(left_data)
    merge_sort(right_data)
    
    left_index = 0
    right_index = 0
    data_index = 0
    
    while left_index < len(left_data) and right_index < len(right_data):
        if left_data[left_index] < right_data[right_index]:
            data[data_index] = left_data[left_index]
            left_index += 1
        else:
            data[data_index] = right_data[right_index]
            right_index += 1
        data_index += 1
    
    if left_index < len(left_data):
        del data[data_index:]
        data += left_data[left_index:]
    elif right_index < len(right_data):
        del data[data_index:]
        data += right_data[right_index:]
    
if __name__ == '__main__':
    data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
    merge_sort(data)
    print(data)

Intead of writing my own code to sort the list, I can use the sort function to make the code more efficient: 

data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
data.sort() # sort function orders the data from least to greatest
print("Sorted List:", data)

Sorted List: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

HACK 5: Rewrite this Python Code in a More Efficient Way 

def heap_permutation(data, n):
    if n == 1:
        print(data)
        return
    
    for i in range(n):
        heap_permutation(data, n - 1)
        if n % 2 == 0:
            data[i], data[n-1] = data[n-1], data[i]
        else:
            data[0], data[n-1] = data[n-1], data[0]
    
if __name__ == '__main__':
    data = [1, 2, 3]
    heap_permutation(data, len(data))

[1, 2, 3]
[2, 1, 3]
[3, 1, 2]
[1, 3, 2]
[2, 3, 1]
[3, 2, 1]

Rewritten Code:

To do this, we can import permutations module from itertools package.

from itertools import permutations

data = [1, 2, 3]
allPermutations = permutations(data) 

for i in list(allPermutations): 
    print (i) # prints all the permutations

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

Extra Permutations 

if __name__ == '__main__':
    abc = ["a", "b", "c"]
    heap_permutation(abc, len(abc))

['a', 'b', 'c']
['b', 'a', 'c']
['c', 'a', 'b']
['a', 'c', 'b']
['b', 'c', 'a']
['c', 'b', 'a']

from itertools import permutations

abc = ["a", "b", "c"]
abcPermutations = permutations(abc) 

for i in list(abcPermutations): 
    print (i)

('a', 'b', 'c')
('a', 'c', 'b')
('b', 'a', 'c')
('b', 'c', 'a')
('c', 'a', 'b')
('c', 'b', 'a')