Final Exam Review Fall 2003: Questions on Complexity
Questions, comments, answers?
Back to Fall2003 Final Exam Review
1) Alan Turing was a brilliant mathematician and computer scientist that came up with a mathematical definition of what a computer could do before one was even built, and proved the halting problem had no solution.
2) Optimization in intractable, in that it has a known solution but it is so hard and big that it can’t be solved in a reasonable amount of time.
3) The Traveling Salesman problem is not completely impossible to solve, but it would take so long that it seems impossible. There may be an answer in Class P, but we haven’t found it yet.
4) A binary search is when you look for something in a list by first splitting the list in half and seeing if the something is below or above that point, therefore eliminating half the list. Then you split the rest in half and compare there and continue until you find the something you were looking for. A linear search is different in that it starts in the beginning and goes along the list all the way to the end until it finds the something. In “Big-O” terms, a linear search is O(n) and a binary search is O(log n).
I dont know if i worded #4 very well but i tried haha
| "intractable" is a bit bigger and meaner than described in (2). Mark Guzdial |
does intractable mean that we know for sure that we cannot come up with a better solution? if it does, would optimization be class P?
what does O(n) mean and what does O(log n) mean
C
| Number of steps in the solution algorithm is roughly the size of the input (O(n)) or the logarithm (base 2) of the size of the input (O(log n)) Mark Guzdial |
so, optimization is class NP? because we do not currently know a solution that executes in a reasonable amount of time (class P?), but there is still a possibility of finding one (so not intractable?)?
.-------------.------------------------------.
| | KNOWN SOLUTIONS |
| |.-------------. .-----------. |
| IMPOSSIBLE || INTRACTABLE | | P | |
| |'-------------' '-----------' |
'-------------'------------------------------'
NP (middle, we're not sure)
2.Optimization is class P, but it would take a long time to solve. Could that work?
oh, nevermind, it's intractable
it depents on the problem to be optimezed. Some simple optimization problems are class P.
| Agreed, but the song optimization that I gave you is intractable. Mark Guzdial |
A binary search is a way of narrowing down sorting by dividing the size of the search results from the previous search into halves until the word or whatever you are looking for is found. In linear search, the sorting is done through each element in the list where as in binary search, sorting is done by dividing search results in half until something that you are looking is found. In Big-O terms, linear search will take n2 steps where as binary search will take n log n steps where n is the number of elements in the entire list.
Pls. correct me if I am wrong.
i got n2 and nlogn from slide 16 from complexity
| A linear search is O(n) and a binary search is O(log n). I think you're looking at SORTING. Many sorts are O(n^2), but better sorts are O(n log n). Mark Guzdial |
Link to this Page
