Sections 17 and 18
Notes and Hacks
- Notes
- HACK 1
- HACK 2
- HACK 3: Rewrite this JavaScript Code in a More Efficient Way (Hint: Use Binary Search)
- HACK 4: Rewrite this Python Code in a More Efficient Way
- HACK 5: Rewrite this Python Code in a More Efficient Way
- Reflection
Notes
- Learning Objective: Explain the difference between algorithms that run in reasonable time and those that do not.
- problem: a description of a task that may or may not be able to be solved through the use of an algorithm.
- instances of problems include specific inputs
- decision problem: a problem with a binary answer (yes or no)
- optimization problem: a problem with the objective of finding the BEST solution amongst many possibilities to solve a problem
- the efficiency is determined through formal and mathematical reasoning
- two-step algorithm consists of an integer to the power of the variable 'n'
- three-step algorithm is an algorithm where there is a variable multiplied by an integer, all to the power of 2
- a four-step algorithm is a variable factorial
- if an algorithm is linear or square
- it runs in a reasonable amount of time
- categorize the run time of an algorithm according to how the number of steps increases as the input size increases
- constant increase: a very fast run time
- exponential increase: a very slow run time
- algorithm runs in constant time
- it means that it always takes a fixed number of steps despite how large the input size increases
- algorithm grows in linear time
- its number of steps increases in direct proportion to the input size
- algorithm grows in quadratic time
- its steps increase in proportion to the input size squared
- selection sorts runs in quadratic time
- algorithm starts from the front of the list, then keeps finding the next smallest value in the list and swapping it with the current value
- nested loop: it loops through each items in the list, and loops again through the remaining items for each of those items
- algorithm grows in superpolynomial time
- its number of steps increases faster than a polynomial function of the input size
- often requires superpolynomial time when it must look at every permutation of values
- unreasonable time
- exponential
- factorial efficiencies
- reasonable time
- constant
- linear
- square
- cube
- undecidable problem: no algorithms can be built that can provide a correct yes or no answer
- have some instances of algorithmic solutions, but no algorithmic solutions that can solve all instances of the problem
- Halting problem: best known problem that has proven to be undecidable, no program can solve the Halting problem for sufficiently general computer programs
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 is a problem for which algorithms can be written to solve and produce a correct output for all inputs and an example of a decidable problem is if a store bought 100 apples, then their balance would be 100 apples. Whereas an undecidable problem is a problem for which no algorithms can be built that can provide a correct yes or no answer or a solution. An example of an undecidable problem is if you were given a computer program that calculates grades, the user will input their current grade. So, the program will loop forever until the user receives their output.
Which of the following is a 3 step algorithm?
A. 2 x 6 x 8
B. 4^5
C. (3 x 8)^2 </p>
D. None of the above E. All of the above Answer: I attempted doing this hack, however, I got stuck and did not understand so, I looked the answer to gain a better understanding. After, looking at the answer I noticed how the code in the answer is condensed in a simpler and shortened format and way, however still has the same function. In addition, the answer code does not set the peak, counter, and peak_index to 0 since using the counter function already assumes that it begins at the value 0 and that there is no reason in for typing in the 0. There are also array.slice and mid_index, which I observed were being used in substitution for the if else statement. The if else command is also used to reverse the array and to find the peak. Ultimately, the code is written in a shortened and simpler format in order to be efficient and easily understand for the user. Answer: Here, I used the Python function "sort" to order the list of number from lowest to greatest. Answer: In this code, I imported the permutation function from the library itertools, so I can make the permutation command. Then, I used a loop so I can iterate all the potential permutations to print permutations. In this section, I learned about all the different types of algorithms. I learned the difference between each one and how to use new Python functions. I learned how different algorithms differ from each other and also when to use certain algorithms and when not to use them. Since particular algorithms are used based on situation by situation. The lesson was also presented well, all the examples were extremely helpful and helped me understand the material and complete the hacks thoroughly.
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
}
}
}
}
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]
}
}
}
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)
givendata = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
print("data unsorted:", givendata)
print (".....")
givendata.sort()
print("data sorted", givendata)
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 # import permutations with library function
data = [1,2,3] # all the possible permutations
for a in permutations(data):
print(a) # print permutations