• Shuffle
Toggle On
Toggle Off
• Alphabetize
Toggle On
Toggle Off
• Front First
Toggle On
Toggle Off
• Both Sides
Toggle On
Toggle Off
Toggle On
Toggle Off
Front

Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key

Up/Down arrow keys: Flip the card between the front and back.down keyup key

H key: Show hint (3rd side).h key

A key: Read text to speech.a key

Play button

Play button

Progress

1/13

Click to flip

13 Cards in this Set

• Front
• Back
 what is an algorithm? well-ordered collection of precise and computable operations that when executed produces a result and halts in a finite amount of time -an approach to solving a problem what is computer science? -study of algorithms: their formal mathematical properties, their realization in hardware, and their applications what is the complexity of an algorithm? -how much time it takes to run -how good the algorithm is at solving the problem what is computability? deals with question of if an algorithm can be executed in a reasonable amount of time on the computer what are some classifications of problems? and describe if they're easy or hard tractable: P-class, NP (easy) intractable: NP-complete (hard) noncomputable what are p-class problems? -tractable -algorithm can solve problem in a polynomial amount of time what is intractable? -no algorithm runs with a polynomial runtime -takes exponential time what are NP problems? NP (Non-deterministic Polynomial time): problems we don't know how to efficiently find a solution for, but if we had one we could verify it easily what are NP-Complete problems? -have the easy to verify property -but if someone can find polynomial time algorithm for one problem it would apply to all NP-Complete problems why can't we deal with intractability? computers get faster at a linar rate, algorithms are exponentially growing -also limitations of computers ->speed of electricity and size of atom -parallel computing doesn't work either, b/c still have to do exponential amount of work what can we do about intractability? heuristic algoithms (common sense rules) -approximations -special cases what is an example of a non-computable problem? halting problem -can compiler tell you its going to go into an infinite loop on some inputs? - three questions can be used to categorize problems, what are they? 1)can a problem be solved? 2)can it be solved in a reasonable time? 3) can its solution be verified in reasonable time?