| Instructor | ||||
| Robert Hochberg Spring Semester, 2003 Office: Austin 325B Phone: 328-0126 Email: hochberg@cs.ecu.edu Website: www.cs.ecu.edu/~hochberg |
|
|||
| Grades | |
| Exams | None scheduled at this point, but I may add a midterm and a final if it seems necessary |
| Homework (see below for assignments) |
Homeworks will be assigned from time to time. You will be
given problems from the book to do worth 5 points each. An unlimited number of retires for each problem is allowed, but the last day to turn in retries is the date of our final exam, May 5. |
| Final Grade | Your final grade is determined as follows:You will receive:
|
| Homework Assignments | |
| Please use the <Discussion
Board> to ask questions about the homework.
Click on <Communication>, then <Discussion Board> ()()Sets of problems in parentheses count as a single, five-point problem.()() |
|
| Due January 27 | Problems 1.24, 1.26 and 1.32 |
| Due February 9 | Problems 1.33, 1.36, (1.38, 1.41), and
show that L={x in {0, 1}* | the first two symbols of x equal the last two} is regular. |
| Due February 26 | Problems (2.16 and 2.17), 2.25, 3.13, and
the following: A DFAQ is a DFA endowed with an unbounded queue. Items are popped from the front of the queue and pushed to the end of the queue, and the transition function is no longer d:Q×Sigma-->Q, but d:Q×Gamma-->Q×Gamma, where Gamma is the queue alphabet (which includes Sigma), the second coordinate in the domain is the symbol popped from the queue, and the second coordinate in the codomain is the item that is pushed onto the queue. Note that that epsilon may be read from or pushed to the queue, and that this does not wreck the deterministic nature of the DFAQ. Also note that our DFAQ does not read an input string: The "input" must be placed on the stack prior to the start of computation. Prove that a DFAQ is equivalent to a Turing machine. |
| Due March 24 |
4.10, 4.11, 4.18 |
| Due April 14 |
(5.9 and 5.10), 5.12, 5.13, (6.5 and 6.6), 7.12 |
| Hand in at least 3 of these by April 28 Everything else due May 5 |
B3: a. Use stirling's approximation:
"n! is about (n/e)^n * sqrt(2*pi*n),"
to show that "n choose n/3" is exponential in n. b. The SQRT-SUBSET problem asks if a given collection of n positive integers has a subset of size sqrt(n) (rounded down) whose sum is exactly T. (The input is the set and the integer T.) Show that the brute-force approach to this problem does not yield a polynomial-time algorithm. B4: A language L is said to be in P-SPACE if there exists a polynomial p(n) and a TM which can decide it using a tape of size p(n), where n is, as usual, the size of the input. Show that L in P implies L in P-SPACE. B5: A language is said to be in co-NP if it's complement is in NP. a. Prove that P is a subset of co-NP b. Show that if co-NP contains an NP-complete problem, then NP = co-NP. c. We mentioned in class that PRIMES is in P. Use this fact to show that FACTOR is in both NP and co-NP. (The FACTOR problem has as input some positive integers n and b, and the problem is to decide if n has a factor less than b, aside from '1'.) B6: a. Use the fact that 3-COLORABLE is NP-Complete to prove that 3-CLUSTERING is NP-Complete. b. Prove that 2-COLORING is in P. Extra credit: Prove that 3-COLORABLE is NP-Complete. B7: Some theory questions a. Does NP contain any undecidable languages? b. How about co-NP? c. Suppose language L can be decided in time n^4, and language M can be reduced to language L in time n^5. Furthermore, language N can be reduced to language M in time n^3. We therefore have a polynomial decider for language N which runs in polynomial time and ultimately uses the decision algorithm for language L. What is the running time for this decider for language N? |