Fall 2006 - CSCI1001 - Introduction to Computer Science

CSCI1001 -- Introduction to Computer Science
Part II -- Robert Hochberg

Notes from class can be found here.

NP-Complete Problems

The traveling salesman problem is an example of an NP-complete problem
A problem is called NP-complete if:

It is a yes/no question.
It is possible to quickly verify a given solution
Any solution to the problem yields a quick solution to all problems which have solutions that can be quickly verified
We didn't talk about any of this in class, so I won't be testing you on anything from item 2. here.

Other NP-Complete problems include:

Can the vertices of a given graph be colored with 3 colors so that vertices which are connected by an edge get different colors?
Given a knapsack which can hold 100 ounces of loot and a list of items with known weights and values, can a thief fit $1,000,000 worth of loot into the knapsack?
Minesweeper

NP-Complete problems have the following two characteristics:

They are hard! All currently-known solutions to these problems are not a lot better than the brute force method of trying all possibilities
If you find a solution to one NP-complete problem, then you have a solution to all other NP-complete problems as well.

Question 6: What is the least number of colors required to color the vertices in the graph below, so that vertices which are connected by an edge get different colors?	Question 7: What is the least number of colors required to color the vertices in the graph below, so that vertices which are connected by an edge get different colors?

Question 8: What are two important ideas related to NP-complete problems?
Question 9: What is the Traveling Salesman Problem?

Deterministic Finite Automata (DFA's)

Also called "Finite State Machines."
A DFA consists of:

Some collection of states

A state is drawn as a circle in our diagrams
There must be one start state, indicated in the diagram with an arrow into it coming from nowhere
And there can be any number of accept states, indicated by a double-circle

Transitions between those states

A transition is drawn as an arrow from one state to another.
There must be exactly two transitions out of each state (including the start and accept states), a transition for "0" and a transition for "1".
A transition can loop back to the state it came from, and an arrow (or loop) may have more than one label on it.

Note that:

Every state must have exactly one "1" transition and one "0" transition leaving it
But a state may have any number of "0" or "1" transitions entering it.

These are "machines" which process an input string and move from state to state as they process the string.

The machine begins computation in the start state
The machine then reads an input string one symbol at a time, and transitions according to the symbol that it reads.
Computation stops when the end of the string is reached. If the DFA is in an accept state at that point, then the string is considered accepted by the machine. Otherwise the string is considered rejected.

Question 1: Build a DFA which accepts all strings.
Question 2: Build a DFA which accepts no strings. (We've done these in class already...)
A string is a sequence of symbols.

In this class, all of our symbols are the binary digits "0" and "1".

Such strings are called binary strings, or bit strings.

The length of a string is the number of symbols it has. For example, the string 11011 has length 5.
The empty string is the string with no symbols. It is denoted by epsilon: .
The number of binary strings of length k is 2^k.

For example, there are exactly 8 binary strings of length 3.
They are 000, 001, 010, 011, 100, 101, 110, 111

The number of binary strings of length at most k is 1 + 2 + ... + 2^k, which equals 2^k+1.
The important thing to note there is that the number of strings of length at most k is finite
Therefore, any infinite language (see below) must have arbitrarily long strings in it.

A language is a set of strings, and the language of a DFA is the set of strings that the DFA accepts.

The language of the DFA shown above is {11, 110, 111, 1100, 1101, 1110, 1111, 11000, ...}, that is, the set of strings which begin with "11".

Also, in the DFA above, computation on any string which starts with "00" will end in the lower-right state.
Some more examples:

The language of the DFA to the right is: {011, 0011, 1011, 00011, 01011, 10011, 11011, ...}, That is, the set of all strings which end in "011".
The language of the DFA to the right is: {0, 1, 01, 10, 010, 101, 0101, 1010, ...}. That is, the set of all strings which have no two consecutive symbols the same
This DFA accepts the language: {0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 101, 110, 111, 0000, 0001, ...}, That is, the set of all strings which do not contain "011" as a substring.
This DFA accepts the language: {0, 1, 000, 001, 010, 011, 100, 101, 110, 111, 00000, 00001, 00010, 00011, 00100, ...}, That is, the set of strings with an odd number of symbols.
Question 3: What is the language of the DFA shown to the right?
Question 4: What is the language of the DFA shown to the right?

Question 5: Construct a DFA which accepts a string if and only if it starts with "1" and ends with "00".
Question 6: Construct a DFA which accepts a string if and only if its second symbol is a "1", such as {01, 11, 010, 011, 110, 111, ...}

Loops and infinite languages Loops

All of the machines depicted in the table above have infinite languages.

That is, the list of strings accepted by those machines goes on without end.
(Which implies that their languages have arbitrarily long strings, as mentioned above in the discussion on languages)

The two machines shown to the right, however, do not have infinite languages.

In fact, the top language has size 1 (just the empty string is accepted) {}
and the bottom machine has size 2 (just strings "0" and "1" are accepted.) {0, 1}

To show that a machine has an infinite language, you can show a list of strings with "..." at the end, implying that any reasonable reader could extend the shown sequence.

For example, {1, 111, 11111, 1111111, 111111111, ...}
See, for example, the descriptions of the languages in the table above.

You can also describe the language in words

For example, "All strings with an odd number of 1's, and no 0's.
Again, see the descriptions of the languages in the table above.
Question 7: Write in set notation the first few strings in the language "All strings of even length."

How can you tell whether a machine has a finite or infinite language?

We saw that this had something to do with loops. First of all, the machine must have a loop in order to have an infinite language.
But the two machines above have loops, but finite languages
In the first machine, there is no way to get from a loop to an accept state.
In the second machine, you can get from a loop to an accept state, but you cannot get from start to that loop.
We therefore decided, and proved, that a machine has an infinite language if and only if there is some path from start to an accept state which goes through a loop.
Question 8: How big is the language of the machine shown to the right?

Halting Problem

This material can be found in your book, in the last chapter.
It can also be found at www.wikipedia.org. Search for "halting problem."
The halting problem asks: Does there exist a program Halt(program P, input I) which looks at program P, with input I, and asks whether program P will halt if its input is I.
We proved that the program Halt cannot exit. Because if it did exist, then we would be able to construct another program called "trouble" (name taken from Wikipedia's article) which works as follows:

Trouble takes a single input, which is just a string, S, of 0s and 1s. These 0s and 1s can be thought of as a program stored in memory or as a number represented in binary.
Trouble runs Halt(program S, input S) to see whether program S would halt if its input is S.

If the answer is "No," then Trouble halts
If the answer is "Yes," then Trouble goes into an infinite loop.

This is fine, until we ask what happens when we run Trouble with itself as input.

If it halts, then it doesn't halt.
If it doesn't halt, then it halts.

This is a big, fat paradox

Like the sentence: "This sentence is false" which can be neither true nor false

The implication is that a program such as Halt cannot be written. It could not exist.

So the halting problem, to write a program which does what Halt, described above, should do, can never be solved by computers.
This leads to a whole host of problems which computers will never be able to solve, such as

Determining if another program will ever print "x" or not
Writing computer programs to prove mathematical theorems

Question 9: What is the Halting problem
Question 10: Is it possible to write a computer program which reads another program as input and determines whether that program has an infinite loop or not?

ml>