Posted by: atri | December 15, 2009

Lect 40: Wrap-up (post #2)

(Guest post by Richard Carpenter)

In the final lecture we started out by finishing up the discussion on longest vs. shortest path. We came to the conclusion that while the shortest path problem can be solved in polynomial time, the longest path problem can only be done if there is a witness to state a path.  Then the path can be verified in polynomial time.

We then went on to discuss the broader topic of $\mathrm{P}$ vs. $\mathrm{NP}$ problems. Where $\mathrm{P}$ type problems can be solved in polynomial times and $\mathrm{NP}$ problems can’t. [Actually, it is not known if $\mathrm{NP}$ problems cannot be solved in polynomial time. –Atri] Currently is has not been proven whether $\mathrm{P}$ equals $\mathrm{NP}$ or whether $\mathrm{P}$ does not equal $\mathrm{NP}$.

In order to prove $\mathrm{P}\neq \mathrm{NP}$ you must pick any one problem in $\mathrm{NP}$ and show it can’t be solved in polynomial time
OR
To prove $\mathrm{P}=\mathrm{NP}$, you can take one of the problems in the $\mathrm{NP-Complete}$ subset of $\mathrm{NP}$ problems and solve it in polynomial time.

Doing either of these will get you \$1,000,000!

From there we started a discussion on coding theory, and more specifically error correction. When data is transmitted from place, there is always some error introduced.

$y = C(x) + \mathrm{error}$

There are many different ways to correct this.  Transmissions over the Internet for example use a checksum, and if there is an error, a request is made to resend the data. All the ways for error correction try to balance redundancy vs. effectiveness

• Repetition code: repeat every bit say $100$ times
• good error correction
• too much redundancy (will take way too long)
• Parity code: Add a parity bit (keeps track of the sum of the bits; either $0$ or $1$)
• minimum amount of redundancy
• bad error correction ($2$ errors go completely undetected)

Code words:  pick a lot of code words that differ from each other significantly

• efficient decoding
• naive algorithm; check received word with all code words

Datastream Algorithms:

Question: Given $n-1$ distinct numbers from $\{1,...,n\}$ what number is missing?

Solution: sum the values in the range and the values given, then subtract
This can be done in $O(n)$ time.

Another major advantage of this is that it only uses $O(log n)$ space, because the sum of the values is given as $\frac{n(n+1)}{2} - i$. The amount of time is takes to compute each of these numbers is $O(\log^2 n)$.  Every packet is seen only once.

And thus does the semester end!