3.17-18
Hacks and Notes
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)