Lesson 9 3.17 and 3.18 Notes and Hacks
Joselyn Anda
3.17 Algorithm Efficiency
Key Vocabulary
- A problem is a description of a task that may or may not be able to be solved through the use of an algorithm. An instance of a problem includes a specific input. One example of this type of problem is a sorting problem.
- A decision problem is a problem with a binary answer (yes or no). An optimization problem is a problem with the objective of finding the BEST solution amongst many possibilities to solve a problem.
- An algorithm's efficiency is determine through formal or mathematical reasoning.
Comparing Algorithms
Algorithm #1
In algorithm #1, the program repeatedly compares two elements in an array of values that are right next to each other, and then swaps them if they are in the wrong order.
In this case, the numbers were 4, 5, 7, and 2 (in that order). The code would look a little like this (notice the bubble sort that was covered by another group!):
def bubbleSort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
arr = [4, 5, 7, 2]
bubbleSort(arr)
print("Here is your sorted array:")
for i in range(len(arr)):
print("%d" % arr[i])
def selectionSort(array,value):
for step in range(value):
min_element = step
for i in range(step + 1, value):
if array[i] < array[min_element]:
min_element = i
(array[step], array[min_element]) = (array[min_element], array[step])
cards = [4, 5, 7, 2]
value = len(cards)
selectionSort(cards,value)
print("Here is your sorted array:")
print(cards)
Practice
Q: Which of the following algorithms is a step 1 algorithm?
- A. 3^4
- B. (2 x 4)^2
- C. 2 x 4
D. 6^4
Answer: C, the integer is 2, and it is being multiplied by a value 'n', which is 4
- The first step consists of an integer being multiplied by a variable 'n'. An example of this could be 5 * n.
Q: Which of the following algorithms is a two-step algorithm?
- A. 3^4
- B. (2 x 4)^2
- C. 2 x 4
D. 6 + 4
Answer: A, the integer is 3, and it is being raised to the power of 4
- A two-step algorithm consists of an integer to the power of the variable 'n'.
A three-step algorithm is an algorithm where there is a variable multiplied by an integer, all to the power of 2.
- An example of this would be (2 * n)^2.
Finally, a four-step algorithm is a variable factorial. For instance, 5! = 5 4 3 2 1 = 120.
- 1 step: Linear
- 2 steps: Exponential
- 3 steps: Square
- 4 steps: Factorial
Constant time:
- When an algorithm runs in constant time, it means that it always takes a fixed number of steps, no matter how large the input size increases.
Linear time:
- When an algorithm grows in linear time, its number of steps increases in direct proportion to the input size.
Quadratic time:
- When an algorithm grows in quadratic time, its steps increase in proportion to the input size squared.
Exponential time:
When an algorithm grows in superpolynomial time, its number of steps increases faster than a polynomial function of the input size.
An algorithm often requires superpolynomial time when it must look at every permutation of values. For example, consider an algorithm that generates all possible numerical passwords for a given password length.
Polynomial vs. Superpolynomial
Polynomial time describes any run time that does not increase faster than n^k which includes Constant time, Quadratic time, and other higher degree polynomials
- Algorithms with a polynomial efficiency or lower (constant, linear, square, cube, etc.)
- reasonable
Superpolynomial time describes any run time that does increase faster than n^k which includes Exponential time and factorial time
- often requires more time than available in the universe, even for relatively small input sizes
- unreasonable
- Algorithms with exponential or factorial efficiencies
3.18 Undecidable Problems
Main Idea:
- There are problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.
Key Vocabulary
- undecidable problem- problems for which no algorithms can be built that can provide a correct yes or no answer or a solution
- decidable problem- problems for which algorithms could be written to solve/produce a correct output for all inputs
num = 4
if num % 2 == 0: # divides num by 2 and checks remainder.
print("is even") # if remainder is 0, num is even
else:
print("is not even") # if there is any remainder e.g its odd num: num is odd
x = input()
while x:
pass
def fumo():
a = 0
i = 1
while a != 1:
i = i + 1
print(i)
fumo()
Barber Paradox:
- There was a barber in a small town on Crick Island, and one day he made a rule that he would only cut the hair of people who did not cut their own hair. The barber's rule seemed to make sense, since people cut their own hair, so I do not have to "do more than that", I will give this person a haircut. Initially, there was nothing wrong with this rule, but later, as the barber's own hair grew longer and longer, he found himself in a dilemma: should he give himself a haircut?
- Answer: If he cuts his own hair, then he becomes the "person who cuts his own hair" in his regulations, then he should not cut his own hair; if he does not cut his own hair, then he is not the one in his regulations A person who cuts his own hair", then he should cut his own hair. Combining the above two situations, "he cuts his own hair" if and only if "he does not cut his own hair", which becomes a paradox.
Hacks/Homework
- Difference between decidable and undecidable problems, with examples.
- Decidable problems are ones that algorithms can ensure an answer, yes or no/true or false, for each input value.
- ex. a list of integers and a function is run to figure out if one of the integer variables is even or odd
- each number besides 0 would have an answer
- ex. a list of integers and a function is run to figure out if one of the integer variables is even or odd
- Undecidable problems can still be represented with algorithms, but not every single input has an answer.
- ex. Forever Running Code or the Halting Problem
- A code that keeps adding 1 to the variable number until number is no longer an integer.This code infinitely continues because it will always be an integer if it increases by 1, making the computer run forever. There is no halt to the code.
- ex. Forever Running Code or the Halting Problem
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
Answer: B, because a three-step algorithm is an algorithm where there is a variable multiplied by an integer, all to the power of 2. In this example 3 is being multiplied by 8 and that product is squared.
Rewrite the code in Javascript, use Binary Search
function peak_search(arr) {
//find the median index
let median = Math.floor(arr.length * 0.5);
//it is a peak if median item is greater than or equal to left item and right item
if (arr[median] >= arr[median - 1] && arr[median] >= arr[median + 1]) {
return `The ${median} indexed number, ${arr[median]} is a peak`;
}
//slice is to section off part of the code to check for a peak within
//this is if the median is not greater than the neighboring items
//if the middle element is less than left neighbor, the peak is to the left
else if (arr[median] < arr[median - 1]) {
return peak_search(arr.slice(0, median));
}
//if the right item of the median is greater check for a peak at the right
else {
return peak_search(arr.slice(median + 1));
}
}
- This whole code is a binary search but uses recursion because it calls itself. For this code it checks the median of the data if it is a peak. It is a peak of its value if greater than the two data items next to it and it will stop there if it finds it. If it does not meet those conditions it slices from the beginning index to that median, eliminates the old median and repeats the process for that sliced off section. It repeats that until it finds the peak in that section.
- 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)
def merge_sort(data):
for index in range(1,len(data)): # repeats through length of the array
value = data[index]
i = index - 1
while i >= 0:
if value < data[i]:
data[i+1] = data[i] # shift number in slot i to the right
data[i] = value # shift value left into slot i
i = i - 1
else:
break
if __name__ == '__main__':
data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
merge_sort(data)
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))
from itertools import permutations
data = [1, 2, 3]
for i in permutations(data):
print(i)
- I honestly did not know how to do this one. I looked at various examples of code. But what I understand from this is that it wants to find all of the total different combinations of the data when it is sorted in different order. This code just uses a built in python tool for permutations.