Formal Methods II

Practice exam:
i T. All NP complete problems are NP hard. (see section 3 of supp notes) Look at the stack. The NP-Complete problems contain some of the EXP, all the P and linear problems. The NP complete problems are the easiest of the NP-Hard problems.

iii) F - Kolmogorov complexity - length of a computer program to compute something, like sqroot 2. Or π. It's not - you can write something finite program to do it. Related to randomness. Shortest possible program to produce something. If that program is shorter than the string, then you have compressed the string.

Krafts inequality. Says that you can actually place proper codes in the tree so that its prefix.

iv F: {0, 1, 101} Violates Krafts inequality, because you have some binary tree with Some code with exactly these lengths,

ix) F There are far more random integers.

Something is algorithmically random

x)F (but won't ask a programming question like this)

Prob 2
Simplify
i O(1) It's a constant!
ii The whole thing goes to 1, (testing knowledge of limit theory)


v. Smaller terms dissapear



Something on information theory, but somewhat less


Euler problem - the perturbation of bridges (as opposed to city)

Perturbation operators
For the maximal clique problem: Like 2-opt or mutation or any number of things you can do to evaluate what to do next while searching.

Stochastic
Just means random - algorithms that have some random aspect to them. (Politics?) Just one bit aglorithmic RULE with some random variables. It would be predictable if all the pollys made the same decision in a predicable manner. But they don't so the algorithm as defined by each law becomes random!

There are degrees of randomness.