CPS 109 Lecture Notes - Lecture 9: Big O Notation, Loop Unrolling, Computational Problem
4 Aug 2016
School
Department
Course
Professor
Document Summary
Consists of the domain of possible instances + their expected answers: domain determines what input the problem is defined for. Placeholder variables giving these some values provides 1 possible instance of the problem. Eg: primality problem: is the integer x a prime number? would have the 1 possible instance of. Decision problem: a problem whose answer is always true or false, all computational problems can be reduced to a series of decision problems. Interesting computational problems tends to have an infinite number of possible instances: or else it could be solved via a lookup table. Unambiguous and deterministic series of instructions: their execution is guaranteed to produce the correct answer, for a particular instance in finite time (which would depend on the particular instance, eg: brute force algorithm for primality. Checks all possible divisors of n, going up to the square root of n.
