Notes and Takeaways

  • Sometimes algorithms can be written ways that are more efficient saving time and lines of code
  • Algorithms can be divided into 4 types
    • 1 step
    • 2 step
    • 3 step
    • 4 step
  • First step is integer being multiplied by a variable “n”.
  • Two step is integer to the power of n
  • Three step is integer being multiplied by n, all to the power of 2
  • Four step is variable factorial (!)
  • Linear and square runs in reasonable amount of time, while exponential and factorial run in unreasonable amounts of time
  • Reasonable time:
    • n^2
    • 2n
    • n
    • n^10
    • n^20
    • log(n)
  • Unreasonable time:
    • 2^n
    • 10^n
    • 5^n
  • Decidable problems: Problems where algorithms can be written and solved for the correct output
  • Undecidable problems: No algorithms can be built for a correct yes or no answer
  • Don’t necessarily need to be able to tell if problem is undecidable for now, just need to know that they exist.

Hacks

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.

A decidable problem has a solution. Algorithms can be written and solved for a correct output. Undecidable problems, however, are like paradoxes that don’t have a solution which makes sense.

Decidable problem:

x = 1

if x == 1:
    print("x is equal to 1")
else:
    print("x is not equal 1")

This problem is decidable because it can produce a correct output every time.

Undecidable problem:

x = 1
i = 2

while i > x:
    print(i)
    i += 1

This problem is undecidable because if you were to run it the loop would continue counting up forever and a correct output could never be generated

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

I chose C because it is two integers being multiplied all to the power of 2 which is what a 3 step algorithm is. A is one step (i think) and B is two step.

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

I’m not gonna lie I don’t understand a single thing this code was supposed to do and I’ve been staring at it for like 30 minutes, so I just decided to look at the answer:

function peak_finder2(array){
    if (array.length)=== 0{
       return  `Array cannot be empty`
     }else if (array.length === 1){
       return array[0]
     }else{
       let mid_index = Math.floor(array.length*0.5)
      if (array[mid_index +1]>array[mid_index]){
         return peak_finding(array.slice(mid_index + 1 ))
       }else if (array[mid_index -1]>array[mid_index]){ 
        new=array.reverse().slice(mid_index+1).reverse()
        return peak_finding(new)  
        }else{
         return array[mid_index]
        }
      }
}

I still don’t understand much but it seems to be a lot shorter and has a lot less variables making it more efficient while still performing the same function.

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)

Since the data is short it doesn’t make any difference to just use the default python sorting function, instead having to write out the huge sorting algorithm

data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
data.sort()
print(data)

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

I wrote a simpler permutation algorithm

def permute(data):
  if len(data) == 0:
    yield []
  else:
    for i in range(len(data)):
      for permutation in permute(data[:i] + data[i+1:]):
        yield [data[i]] + permutation

data = [1, 2, 3]
for permutation in permute(data)
    print(permutation)