Change Contents of the Bubble
Welcome to CS1315. Click on the python to add comments.


This page removed for FERPA compliance
View this PageEdit this Page (locked)Uploads to this PageHistory of this PageHomeRecent ChangesSearchHelp Guide

Final Exam Review Spring 2004: Questions on Complexity

REMOVEDnk back to Sp2004 Final Exam Review

Questions and Answers?


1. Who's Alan Turing and what did he do of interest to us?
und. degree in math and bio., phd in CS, jazz guitarist. Saw object-oriented programming as a way of developing software that could truly scale 2 large systems. Described objects as being like biological cells that work 2gether in well-defined ways 2 make the whole organism work. developed Squeak (cross platform multimedia tool-check out http://www.squeak.org) w/ others.
2. Is optimization (e.g., the ``song'' problem) class P or
intractable? What does intractable mean? Intractable= problems w/ hard and big solutions that take a long time 2 solve. ex. optimization
3. Is the Traveling Salesman problem impossible to solve in
reasonable amounts of time? The T.Salesman prob. is an ex. of classNP (problems in which there may be a solution in class P (many problems solved w/ an algorithm whose running time has a complexity that's a polynomial ex. sorting)that has yet 2 b found. NO it's NOT imossible thanks 2 the use of algorithms...O(n!) solves the salesman prob.!
4. What is a binary search? REMOVEDw do linear and binary searches
differ? In "Big-O" terms?
binary search=remember the dictionary example? where one keeps splitting the dictionary 2 find a word until one gets close to the first letter of the word. think ABC order w/ binary.
linear search=dictionary ex. of looking for a chosen word page by page starting with the first page up until the word has been found. Could wind up being a slow, medium, or fast search depending on whether the word is at the beg, mid., or end of the dictionary.
Big-REMOVED Notation=refers 2 the magnitude of running time of an algorithm, expresses how much slower the program gets as the input data gets larger. focuses on the # of steps 2 b executed rather than interpreting languages. GOOD LUCK ON THE FINAL!!! HAVE A WONDERFUL SUMMER!
Mireille Murad
so optimization is an example of class P? which would be class "polynomial" and a solveable complex problem?

Mireille, you've confused Alan Turing with Alan Kay. Optimization is definitely not in class P. Mark Guzdial

OOPS sry. guys. here we go. . .
Alan Turing- he showed that such a setup (refer 2 pg292) would announce that the program would halt only if it loops 4ever, and would halt only if it announces that it would loop 4ever. came up w/ 1936 proof almost 10yrs b4 the 1st computers were built. he defined mathematical concept of a comp. called a turing machine that he was able to make such proofs about b4 physical computers were ever built Mireille Murad

so optimization is class intractable
YES optim is intractable =) Mireille Murad
Alan Turing was arrested and came to trial on 31 March 1952, after the police learned of his sexual relationship with a young Manchester man. He made no serious denial or defence, instead telling everyone that he saw no wrong with his actions. He was particularly concerned to be open about his sexuality even in the hard and unsympathetic atmosphere of Manchester engineering. Rather than go to prison he accepted, for the period of a year, injections of oestrogen intended to neutralise his libido.

eick!

Alan Turing in Time Magazine http://www.time.com/time/time100/scientist/profile/turing.html
http://www.time.com/time/time100/scientist/profile/turing.html

is that the guy that had the idea about personal comuters? ...and everyone laughed at him and walked out on his lecture, or was that the other Alan?
That's the other Alan – Alan Kay invented our current notion of personal computers. Alan Turing did most of his most famous work before computers were even invented. Mark Guzdial

1. Who's Alan Turing and what did he do of interest to us?
Alan Turning was a mathematician and computer science and he came up with the mathematical defination of what a computer could do—before one was even built! The Turing machine was built to answer what the limits of mathematics were. He proved that the Halting problem had no solution in 1936, which was almost 10 years before the first computer was built!
Student1113

mark, is this the right definition of binary search?
it searches the data within a range. One examples is binary chop: that keeps bisecting the data till it finds the answer.
Anu
An intractable problem is one with a known solution, but the solution is so difficult and complex taht it can't be solved in a reasonalbe amount of time (based on ploynomial) for a reasonable about of data.
Anu, all searches search within a range. A binary search partitions the range in a useful way. Your description of the "binary chop" is useful. A solution to an intractable solution is not necessarily complex – it just takes a LOOOONNNGGG time to run, even for a reasonable amount of data. Mark Guzdial




Link to this Page