University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
Department of Computer Science
My Home Page
CSC 456/656 Assignment 7
Due date: Monday, April 17, 2017, 11:30 AM.
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.
-
Give a polynomial time reduction of the knapsack problem to the partition
problem. Your reduction should be
accompanied by a discussion;
not a formal proof of correctness, but a discussion that convinces the
casual reader that the reduction is correct.
-
Let
L be
the the language of all strings over the unary alphabet of positive
square length.
L is recursive, hence
clearly recursively enumerable. Give a general grammar which generates L.
Include a discussion, not
necessarily a formal proof, which convinces the reader that
your grammar generates L.
-
Work problems 1 and 2 on
the NC handout. I fixed the problem.
You should be able to print it now.
Back to
Course Page