Part II of Introduction to Computer Science

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

Notes are now complete

March 1 slides on DFA's
March 3 slides on DFA's
March 10 slides, with HW review

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?

Greedy Algorithms

The Nearest Neighbor and Cheapest Link algorithms given above are examples of greedy algorithms
A greedy algorithm is one which makes all decisions based on what sems best at the time, without worrying about the future consequences of that choice.
Greedy algorithms tend to be fast
But greedy algorithms do not always find the best solution to a given problem

For example, the nearest neighbor algorithm selects at each step the cheapest available edge, but usually the route it gives is not the shortest possible route.

One problem that greedy algorithms do solve optimally is the problem of finding a minimum weight spanning tree in a graph, also called a cheapest connecting network for that graph.

That is, given a graph with costs on the edges of that graph, you want to find the cheapest set of edges which connects all the vertices (nodes, sites) in that graph.
The greedy algorithm for this problem says to select at each step the cheapest edge available such that you don't create a cycle within the edges you have chosen.
Question 10: Use the greedy algorithm described above to find a minimum weight spanning tree in the graph shown above. Indicate the order in which your algorithm selected the edges to put into your minimum weight spanning tree.

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.

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:

he 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, taken from the website: http://www.netaxs.com/people/nerp/automata/dfa1.gif accepts all strings which contain an even number of 0s and an even number of 1s.
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, ...}

Turing Machines

A Turing machine is a DFA with an attached tape from which it reads its input, and onto which it can write
Turing machines are capable of implementing all algorithms which could be programmed into a computer
However, we can prove that there are some tasks which a Turing machine cannot perform

Such as recognizing whether the program on its tape would ever print an "x"
Such as recognizing whether the program on its tape has an infinite loop or not. This problem is called the "Halting problem."

A Turing machine is a simple model of computation. As such, we can prove statements about what is or is not possible on a computer by proving that a Turing machine can or cannot do it.
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?