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

CS 456/656 Assignment 5
Due date: December 5, 2006, 4:00.
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.
-
In three sentences or less, explain the importance of the halting problem.
-
In three sentences or less, explain the importance of a Universal
Turing machine.
-
True or False - (statements in parentheses can be take as given)
-
Every regular language can be enumerated by some output DFA.
(A deterministic finite state machine with output is called an
output DFA.)
-
A multi-tape Turing machine can emulate a single tape Turing machine.
-
A single tape Turing machine can emulate a multi-tape Turing machine.
-
Every PDA can be emulated by a machine with just one queue of unbounded size
and only finite additional memory.
-
Every PDA can be emulated by a machine with just three queues of
unbounded size and only finite additional memory.
-
Every Turing machine can be emulated by a 2-PDA (that is, a machine with
two stacks of unbounded size and only finite additional memory).
-
The language of all decimal numerals for composite positive integers
is recursive. (A positive integer n is said to be
composite if it is the product of
p and q, both of which are positive
integers less than n.)
-
With currently known algorithms, an RSA code can be broken in polynomial time.
-
For each of the following problems, state whether it is known to be
polynomial, known to be NP, known to be NP-complete, known to not be NP.
-
The traveling salesman problem.
-
Boolean satisfiability.
-
The clique problem.
-
Minimal spanning tree problem.
-
Minimal spanning tree problem, where the spanning tree may not have
degree more than 3.
-
The halting problem.
-
Finding the next best move in chess.
-
Determining whether a given integer has a prime factor less than a given
number.
-
Determining whether a given string is generated by a given context-free
grammar.
Back to
Course Page