University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
Department of Computer Science
My Home Page
Course Page

CSC 456/656 Assignment 9
Due date: Tuesday, November 26, 2013, 1:00 PM.
All assignments must be handwritten (not typed or printed from a computer
file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper.
Write your name on each sheet, and do not fold the pages or crimp the corners.
(You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.
-
Answer these questions
by filling in the blanks. (Print out the pages,
fill in the blanks, and turn the pages in.)
In postscript format.
Thu Nov 21 18:32:39 PST 2013:
The file has been changed. I removed two
duplicate questions.
What is a context-sensitive language?
postscript format
-
Consider the Boolean expresssion:
x1⇒x2*!x1 (That's "implies" not "equal.")
-
Convert that expression
to an equisatisfiable Boolean expression in 3-CNF form, using the parse tree
method we did in class. (When I did it, I got a 3-CNF expression with nine
clauses.)
-
Find a satisfying assignment of the original Boolean expression, and
give a corresponding satisying assignment of the 3-CNF expression.
-
Consider the 3-CNF expression:
(x1+x2+x3)*(!x1+!x2+x4)*(!x3+x4+!x2)
-
The reduction we did in class
maps that expression to an instance of the k-independent
set problem. Draw the graph for that instance, and state the value of k.
-
Select a k-independent set of nodes of that graph, and give a corresponding
satisfying assignment of the Boolean expression.
-
Prove that integer factorization is in both NP and co-NP.
(You will need to use the result that primality is in P, which
was first proved in 2002 by Agrawal, Kayal, and Saxena.)
Do not be ashamed to go to the internet, but write the proof in your
own words and your own handwriting.
Assignment 9 is now finished.

Back to
Course Page