\documentstyle[11pt,fullpage]{article}

\setlength{\parindent}{0pt}
\setlength{\parskip}{7pt plus 1pt}

\begin{document}
\begin{center}
{Foundations of Computing} \\
{Depth Examination}\\
{Fall 1995}\\
\end{center}

Directions: Answer any FOUR of the six questions below.

\begin{enumerate}
\item
Given an undirected graph, a subset of the nodes is
{\it independent} if and only if no pair of nodes in the subset is
connected by an edge. A {\it cycle} is a connected, undirected
graph in which every node has exactly two adjacent edges.

Determine the number of independent sets in a cycle of size $n$.
\item
For this problem you are to consider deterministic finite automata
that are chosen randomly.  This is done as follows.  Let $\Sigma$
be a finite alphabet, and $K_n = \{q_1,\ldots,q_n\}$ a set of $n$ states.
For each pair $(q_i,a) \in K_n \times \Sigma$, we assign the
next state $\delta(q_i,a)$
to be a random (i.i.d. uniform) element of $K_n$.  We let $q_1$ be 
the initial state and $q_n$ be the final state.  Let 
$L_n$ be the language accepted by this machine.

\begin{enumerate}
\item
Show that if $|\Sigma| = 2$, then $L_n$ is empty with probability
bounded away from 0 (as $n \rightarrow \infty$).
\item
What happens for larger alphabets?
\end{enumerate}

\item
A class of languages (such as P or NP) is said to have a 
{\em recursive enumeration} if there is a recursive algorithm that enumerates
every language in the class, where a language is represented by a 
Turing machine that accepts it. A language in the class may appear more 
than once in the enumeration, but every language in the class must
eventually appear in the enumeration.)
\begin{enumerate}
\item
Show that the class NP has a recursive enumeration.
\item
Show  that the class of NP-complete languages has a recursive enumeration.
\end{enumerate}

\item
An undirected graph $G=(V,E)$ is a {\em split graph}
if its vertex set can be partitioned into two disjoint
subsets $U$ and $W$ such that the graph induced by $U$ 
has no edges and the graph induced by $W$ is a complete
graph (i.e., all the edges are present).
Design a linear-time algorithm to determine whether
a given graph is a split graph.

\newpage

\item
Let $L$ and $M$ be two languages.  We say that $L$ and $M$
are {\it polynomial-time isomorphic} if there are two polynomial-time
computable maps $f: L \rightarrow M$ and $g : M \rightarrow L$ for
which $f \circ g$ and $g \circ f$ are identity maps.  If this holds,
we write $L \cong M$.

Let $\Sigma_n$ stand for the alphabet of size $n$, where $n \ge 1$. 
Characterize the pairs $(m,n)$ for which $\Sigma_m^* \cong \Sigma_n^*$.

\item 
The  Maximum Independent Set (MIS) problem is to find an independent
set of maximum size in an undirected graph.
The naive algorithm for the MIS problem
examines all $2^n$ possible subsets of the $n$ nodes of the graph,
checking each for independence. It outputs the largest subset 
which is independent. 

Your task is to design an algorithm for the MIS problem with 
running time at most a polynomial in $n$ times $3^{n/2}$.  Show that your
algorithm correctly finds the maximum independent set.

Hint: note that if two nodes are connected by an edge, only one
can be in the independent set. You may want to use matching.


\end{enumerate}

\end{document}