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 problems where algorithms can be used to solve or produce outputs in a finite number of steps. In contrast, undecidable problems are problems where there is no algorithm that can be built to provide a solution.
number = 20 #set number equal to random value
if number > 10: # if the number is greater than 10
print("greater than 10") #print
else: # if less than 10
print("not greater than 10") # print
num = 1
while num == 0: # the number will never equal 0 since we set it to 1, so this is undecidable
print(num)
num = num + 1
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
- this is the correct answer because a three step algorithm is an algorithm where you multiply a variable and integer, all to the power of two. This algorithm fits this criteria.
D. None of the above
E. All of the above
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
}
}
}
}
Hack 3 Answer
I wasn't really sure how to do this cause the output from the example wasn't running so I wasn't sure what it would print, but I would use a recursion like it said in the comments. A recursion is when a function calls itself until someone stops it. If no one stops it then it'll recurse (call itself) forever. Recursive functions let you perform a unit of work multiple times. This would be much more efficient and faster than the code above because, there is much less code and you don't need to keep calling the function, it will just do it automatically.
function peak_finder(array){
let counter = 0
let peak = 0
let peak_index =0
recurse(peak_finder);
// function code
}
recurse();
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] # list of numbers not in order
print("unsorted data:", data) # print unsorted data
print ("---------------------------------------------")
data.sort() # sort function to sort through data
print("sorted data", data) # print sorted 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))
Hack 5 Answer
- I imported the itertools module to use the permutations function. This function take a list as an input and returns an object list of tuples that contains all permutations in a list form. I used the list [1,2,3] from the example above and set a parameter of 3 which would be the length of the permutation. There are 3 numbers, so the length is 3. Then I used a for loop to loop through all possible permutations. It is also easier to look at than the example because it goes through permutations starting with 1, then 2, then 3.
# permutations using library function
from itertools import permutations
# Get all permutations of [1, 2, 3]
perm = permutations([1, 2, 3], 3) # the 3 outside the bracket is all the permutations of the length 3
# if we changed it to 2 it would show all the permutations of the length 3.
# Print the obtained permutations
for i in list(perm):
print ([i])
Extra
I was interested by the permutation method so I tried experimenting with the combination function.
I did some extra research and used this website to help: link
# A Python program to print all combinations
# with an element-to-itself combination is
# also included
from itertools import combinations_with_replacement
# Get all combinations of [1, 2, 3] and length 2
comb = combinations_with_replacement([1, 2, 3], 3)
# Print the obtained combinations
for i in list(comb):
print ([i])
# Python3 code to demonstrate working of
# All possible items combination dictionary
# Using loop + set()
# initializing Dictionary
test_dict = {'gfg' : [1, 3], 'is' : [5, 6], 'best' : [4, 7]}
# printing original dictionary
print("The original dictionary is : " + str(test_dict))
# All possible items combination dictionary
# Using loop + set()
temp = [set([key]) | set(value) for key, value in test_dict.items() ]
res = {}
for sub in temp:
for key in sub:
res[key] = list(sub - set([key]))
# printing result
print("The all possible items dictionary : " + str(res))
Explanation: I learned how to return an all possible items dictionary. Using loop + set() method, we extract all items flattened in list of sets. Then we construct each dictionary using set subtraction.