Part II of Introduction to Computer Science

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

Notes are now complete

Slides from 9/20
Slides from 9/27
Slides from 10/4

Traveling Salesman Problem
( Some notes from class - pdf )

A salesman wishes to start at one city, visit a number of other cities, and end up back where he started. The cost of travel between each pair of cities is given, and the task is to find the cheapest route which visits all cities.
The brute force approach to solving this problem requires checking 1×2×3×4×...×(n - 1) routes, where n is the number of cities.

Actually, this number could be cut in half by observing that each route has the same length as its reverse, so we would need to check only one direction around each route.
The quantity 1×2×3×4×...×n is called "n factorial," and are denoted n!
Question 1: Is it true that 6!×7! = 10!?
The factorial numbers grow very fast. 1! = 1, 2! = 2, 5! = 120, 10! = 3628800, 20! = 2432902008176640000. This is why the brute force approach is completely hopeless for more than 20 cities.
Question 2: What is the number of routes that would need to be checked by brute force on a map with 13 cities?

So we have some heuristic algorithms for solving this problem. These heuristic methods run very fast (by computer...) on even several million cities, but they are not guaranteed to give the optimal solution

The "nearest neighbor" algorithm has you start at some city, and then at each step go to the nearest city which has not yet been selected. When all cities have been visited, return home.
The "repeated nearest neighbor" algorithm has you run the nearest neighbor algorithm from each possible starting point and then selecting the cheapest one you find
The "cheapest link" algorithm has you select at each step the cheapest edge (connection) available, subject to the conditions of not creating a vertex with 3 edges coming out of it, and not creating a premature cycle (that is, a cycle which does not contain all the cities that need to be visited).
Question 3: Run the nearest neighbor algorithm on the graph shown to the right, starting at vertex A
Question 4: Run the cheapest link algorithm on the graph shown to the right.
Question 5: Can you find a shorter path than either of these two algorithms give?

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.

So one typically rephrases the Traveling Salesman Problem in the form: "Does this graph have a circuit of length less than 100?

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.

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 10: Can you build a DFA with one state which accepts all strings?
A string is a sequence of symbols.

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

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 11: What is the language of the DFA shown to the right?
Question 12: What is the language of the DFA shown to the right?

Question 13: Construct a DFA which accepts a string if and only if it starts with "1" and ends with "00".
Question 14: 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, ...}

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 15: What is the Halting problem
Question 16: 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?