Study your flashcards anywhere!
Download the official Cram app for free >
 Shuffle
Toggle OnToggle Off
 Alphabetize
Toggle OnToggle Off
 Front First
Toggle OnToggle Off
 Both Sides
Toggle OnToggle Off
 Read
Toggle OnToggle Off
How to study your flashcards.
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
13 Cards in this Set
 Front
 Back
what is an algorithm?

wellordered 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: Pclass, NP (easy)
intractable: NPcomplete (hard) noncomputable 

what are pclass 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 (Nondeterministic 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 NPComplete problems?

have the easy to verify property
but if someone can find polynomial time algorithm for one problem it would apply to all NPComplete 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 noncomputable 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? 