Unit 3 Flashcards
What two factors do computer scientists have to consider when creating an algorithm?
Time (number of steps) and space (memory needed)
What is a heuristic?
A reasonable time algorithm that provides an approximate solution to a problem. It’s “good enough”
- Finding routes between two towns
- Finding files in a list of docs
- Simulated annealing to solve TSP
Heuristic examples
Reasonable or non-reasonable time: O(1)
Reasonable
Reasonable or non-reasonable time: O(n)
Reasonable
Reasonable or non-reasonable time: O(n^2)
Reasonable
Reasonable or non-reasonable time: O(n^c)
Reasonable
Reasonable or non-reasonable time: O(log(n))
Reasonable
Reasonable or non-reasonable time: O(nlog(n))
Reasonable
Reasonable or non-reasonable time: O(c^n)
Non-reasonable
Reasonable or non-reasonable time: O(n!)
Non-reasonable
O(1)
Constant
O(n)
Linear
O(n^2)
Quadradic
O(n^c)
Polynomial
O(log(n))
Logarithmic
O(nlog(n))
Quasilinear
O(c^n)
Exponential
O(n!)
Factorial
True or false: Every problem with an initial condition can be solved in a reasonable amount of time using a modern computer.
False
True or false: Every problem can be solved using a computer and an algorithmic method, but some solutions require much more time than others
False
True or false: To show that a problem is undecidable, you need to show that there exists an instance of the problem that cannot be solved via an algorithm
True
True or false: One can use the Python programming language to create a program that determines whether any program/function and any input will descend into an infinite loop.
False
Suppose you are working on a project that leads to a problem that you and your group determines to be undecidable. What consequences are most likely to be true based on that fact?
There is no algorithm that can definitely solve the problem.
Compares and orders elements pairwise until the list is ordered. The method is better for a list of 10 numbers. (O(n^2))
Bubble sort
Splits the list into multiple sublists then sorts them as it puts the lists back together. The method is better for a list of 150 numbers. (O(nlog(n)))
Merge sort
Looks through a list one element at a time until it finds the target value. Also known as linear sort.
Sequential search
Takes a sorted list and splits it in half, eliminating half of the list based on whether the target is above or below. This is more efficient than sequential search.
Binary search
What are the criteria for binary search to work
Sorted list of the same type
How many guesses would it take to guess a number between 1 and 600?
10, 2^10 is 1024
