Study your flashcards anywhere!

Download the official Cram app for free >

  • Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle 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


Play button


Play button




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)
what are p-class problems?
-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)
-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?