## CPS616 |
## W2017 Lab 8 | |

## Worth: 7% |
## Algorithm Limitations and NP-Completeness |
## Due: April 25 |

## Team sizeThis lab can be done in teams of 1 or 2.## Lab Description## Question 1 - Decision TreeThis question and the next one are based on the Findfake2 algorithm described in lab5. Your coinpile willbe called C. You can refer to each of its n elements as C[1], ..., C[n] and the pile of all elements from a to b inclusive as C[a-b]. (It is easier to start counting at 1 instead of 0)- Draw a decision tree for the Findfake2 algorithm for a coinpile C of size 13.
- Comparison with
2-3 trees
- What does your decision tree have in common with a 2-3 tree?
- How does your decision tree differ from a 2-3 tree?
- Extrapolating from the tree you just built, what will be
- the number of leaves of a decision tree for Findfake2 when the coinpile has n element?
- the height of a decision tree for Findfake2 when the coinpile has n elements?
- Based on this decision tree what can you conclude about the worst case performance of this algorithm? Explain your answer.
## Question 2 - Adversary Argument- Fill out the adversary argument table for the Findfake2 algorithm for a coinpile C of size 14:
You will weigh(x,y) x C[1-7] y C[8-14] Adversary responds - Based on this argument what can you conclude about the worst case performance of this algorithm? Explain your answer.
## Question 3 - Problem ReductionProblem P is the following: given an array of n distinct integers, build a binary search tree for these integers.Problem Q is the following: sort an array of n distinct integers. It is well known that problem Q has a tight lower bound of Omega(n logn). - Reduce Q to P. In other words, describe an algorithm for solving problem Q by using a solution to problem P
- Use a problem reduction approach to show that P also has a lower bound of Omega(n log n) by using the lower bound of problem Q.
- is Omega(n log n) a tight lower bound for P? explain your answer.
## Question 4 - Turing MachinesIn this question you will be designing two Turing Machines, one deterministic and one non-deterministic, both with multiple tapes. These Turing machines have a syntax and operations very similar to the Turing machine simulator demonstrated in class. You will not be able to test your solutions on this simulator because it only has one tape whereas yours will have 3. However, you are encouraged to play with this simulator to better understand the operations of Turing machines.Your two Turing machines will be implemented as transition tables in the last two tabs of this spreadsheet, which is where you should enter your answers to section. - The first tab explains the operations of your two Turing machines and the syntax of your transition tables.
- The second tab is the deterministic Turing machine you are asked to design for part a). Please specify the values of Q and T at the top of the tab.
- The third tab is the non-deterministic Turing machine you are asked to design for part b) Please specify the values of Q and T at the top of the tab.
- You can assume that there are two built-in states called "accept" and "reject", so all you need to do to accept or reject a string at some point during its processing is to make the new state one of these states.
- A string can also be rejected implicitly if the TM reaches a point in its processing of the string when there are no valid transitions for the instantaneous description of the TM. See Explanation tab in spreadsheet for further details.
- Deterministic Turing Machine In the second tab of your spreadsheet, describe a 3-tape DTM which calculates n! for any positive integer n
- Input in Tape 1: [unary representation of n]
- Output in Tape 3: [unary representation of n!]
- Tape2 is used as temporary storage for calculations.
- Non-Deterministic Turing Machine In the third tab of your spreadsheet, design a 3-tape NTM which verifies whether a simplified exact knapsack problem has a solution:
- Input in Tape 1: [C 0's] represents the knapsack capacity
Tape1 head positioned over the leftmost 0 e.g. "000000000000000" represents a knapsack of capacity 15 - Input in Tape 2: 1[w
_{1}0's]1[w_{2}0's]...1[w_{n}0's] representing the n weights, each of which is preceded by a "1" Tape2 head positioned over the leftmost 1 e.g. "10010001010000000000100000" represents weights 2,3,1,10,5 - Output in Tape 3:
if the problem has a solution, the weights that fit the knapsack exacly
will be shown in Tape3
using the same format as the Tape 2 input.
e.g. for the problem above, Tape3 could be "100100010000000000" or "10000000000100000" - If the problem has a solution this solution should be be found in O(C) time.
- Analysis
- If the NTM in part b) accepts an input string on Tape 2 which has n 1's, how many times will it have read a 1 before it accepted the string? The answer should be a function of n. In this question "reading a 1" means that one of the tape heads was over a 1 and moved left or right away from it.
- Why is the previous question asking you to count how many times a 1 is read on tape 2 and not to count how many times a 0 is read on Tape 2?
Given a knapsack of non-negative capacity C (i.e. C is positive or 0) ,
and n objects with non-negative weights w
## Additional Material- Textbook chapter 11.1, 11.2, 11.3
- Class handout on Algorithm Limitations
- Page 2 of the class handout on NP-Completeness.
## Hand InThis lab is a paper submission to be handed in at the Computer Science office. |

Last modified Tuesday, 11-Apr-2017 21:46:57 EDT