Prof. Christos

What is a decision problem?

A problem whose answers are only yes xor no.
What does it mean for a decision problem to be decidable

There exists at least one algorithm that answers all problem inputs correctly.
What is the class P? What is the class NP?

Decision probems easily solvable in polynomial time. Solution verifiable in polynomial time.
What is the intuitive meaning of the "P versus NP" question?

Whether all NP have shortcuts to be computed as P.
If you resolve the P versus NP question, how much richer will you be?

A lot.

Theory guy that teaches:
1. 251 Great Theoretical Ideas in CS (required)
2. 451 Algorithm Design and Analysis (required)
3. 455 Undergraduate Complexity Theory (Interesting)
4. Formal Languages Automata and Computability (Interesting)
He talked about 3 situations corresponding to situations in CS Theory:
1. Ahmed in Municipality designing maps for sweeping truck. Eulerian cycle: P = efficiently solvable
2. Batoul in Q-Post designing maps for delivery point. Hamiltonian cycle: NP = not efficiently solvable, but solvable
3. Saif in Apple predicting program crashes. Halting problem: unsolvable
Overall takeaway: CS Theory is so important and interesting. Definitely want to learn more about it. It is also important to apply theories to application (from Professor Khaled).

Questions for Professor Christos's Lecture