Unit 3 Sections 17-18 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.
Decidable problems are those for which an algorithm exists that can solve the problem in a finite amount of time, while undecidable problems are those for which no such algorithm exists. An example of a decidable problem is determining whether a given number is even or odd as shown below:
x = int(input("Type a number: "))
if x % 2 == 1:
print(x, "is odd")
else:
print(x, "is even")
And an example of an undeciable problem is the Halting Problem which basically a program and its input are given, and it needs to be determine whether or not the program will run forever. This problem is undecidable because it is possible for a program to contain an infinite loop that never halts.
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
The answer is C since first the 3 and 8 are multiplied giveing 24. Second the previous result is squared (24^2) which give 576. Giving a result of 576. And this takes a total of three steps.
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
}
}
}
}
This was a bit difficult and I didn't really know how to do this, but I tried my best.
function peak_finder(array) {
for (let i = 0; i < array.length; i++) {
if (i === 0) {
if (array[i] >= array[i + 1]) {
return `The ${i} indexed number, ${array[i]} is a peak`;
}
} else if (i === array.length - 1) {
if (array[i] >= array[i - 1]) {
return `The ${i} indexed number, ${array[i]} is a peak`;
}
} else {
if (array[i] > array[i - 1] && array[i] > array[i + 1]) {
return `The ${i} indexed number, ${array[i]} is a peak`;
}
}
}
}
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)
data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
print("Unsorted Data: ", data)
data.sort()
print("Sorted Data: ", data)
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))
from itertools import permutations
data = [1, 2, 3]
for i in permutations(data):
print(i)