## Due: Monday, May 3, at the beginning of class. Turn in physically or by email to Thach.

Remember to take a look at the grading guidelines.

In solving the problem sets, you are allowed to collaborate with fellow students taking the class, but remember that each submission can have at most one author. If you do collaborate in any way, you must acknowledge, for each problem, the people you worked with on that problem.

The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools.  Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.

Most of the problems only require one or two key ideas for their solution.  It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details.

A final piece of advice:  Start working on the problem sets early!  Don’t wait until the day (or few days) before they’re due.

## Problems

Each problem is worth 15 points unless otherwise noted.

1. Let $A$ be the language of properly nested parentheses. For example (()) and (()()(())) are in $A$, but )( is not. Show that $A$ is in L.
2. Let CONNECTED denote the language consisting of directed graphs which are strongly connected: there is a path from $a$ to $b$, for every pair of vertices $a,b$. Show that CONNECTED is NL-complete.
3. An undirected graph is bipartite if the vertices can be partitioned into two sets such that all edges go from a node in one set to a node in the other. A graph is bipartite if and only if it does not have any cycles of odd length. Let BIPARTITE denote the language consisting of bipartite graphs. Show that BIPARTITE $\in$ NL.
4. Show that SAT $\notin TISP(n^c, n^d)$ for all constants $c,d$ such that $c(c+d)<2$.
5. If $S = \{ S_1,S_2,\dotsc,S_m \}$ is a collection of subsets of a finite set $U$, the VC dimension of $S$ is the size of the largest set $X \subset U$ such that for every $X' \subset X$, there is a set $S_i$ in $S$ for which $S_i \cap X = X'$. A boolean circuit $\mathcal{C}$ represents collection $S$ if $S_i$ consists of exactly those elements $x \in U$ for which $C(i,x) = 1$. Define the language VC-DIMENSION to consist of those pairs $$ such that $C$ is a circuit representing a family of VC dimension at least $k$. Show that VC-DIMENSION is in $\Sigma_3^p$, and is complete for this class.