CPS616

W2017 Lab 8

Ryerson University

Worth: 7%

Algorithm Limitations and NP-Completeness

Due: April 25


Team size

This lab can be done in teams of 1 or 2.

Lab Description

Question 1 - Decision Tree

This 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)
  1. Draw a decision tree for the Findfake2 algorithm for a coinpile C of size 13.
  2. 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?
  3. 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?
  4. Based on this decision tree what can you conclude about the worst case performance of this algorithm? Explain your answer.

Question 2 - Adversary Argument

  1. 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

  2. Based on this argument what can you conclude about the worst case performance of this algorithm? Explain your answer.

Question 3 - Problem Reduction

Problem 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).

  1. Reduce Q to P. In other words, describe an algorithm for solving problem Q by using a solution to problem P
  2. 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.
  3. is Omega(n log n) a tight lower bound for P? explain your answer.

Question 4 - Turing Machines

In 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.
Notes:
  • 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.
  1. Deterministic Turing Machine
  2. In the second tab of your spreadsheet, describe a 3-tape DTM which calculates n! for any positive integer n

    Exact Specifications: All positive integers are represented in unary notation using the input symbol "1". For example 7 is represented as "1111111"

    • Input in Tape 1: [unary representation of n]
    • Output in Tape 3: [unary representation of n!]
    • Tape2 is used as temporary storage for calculations.
    At the end of the calculations, n does not need to be on Tape 1 anymore. Therefore, n can be gradually erased from Tape 1 as n! is being calculated.
  3. Non-Deterministic Turing Machine
  4. In the third tab of your spreadsheet, design a 3-tape NTM which verifies whether a simplified exact knapsack problem has a solution:

    Given a knapsack of non-negative capacity C (i.e. C is positive or 0) , and n objects with non-negative weights w1, w2, ... , wn, where n is a positive integer,
    can you put some of these objects in the knapsack so as to completely fill the knapsack? (i.e. so that there is no room left in the knapsack)

    Exact Specifications: All positive integers are represented in unary notation using the input symbol "0". For example 7 is represented as "0000000"

    • 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[w1 0's]1[w2 0's]...1[wn 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.
    Note that if the problem does not have an exact solution, then the NTM will never accept the input string and the contents of Tape3 won't matter.

    Extra Challenge: Try to minimize the number of rows in your transition table. (I have 11, 3 of which are explicit rejections that can be removed.)

  5. 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?

Additional Material

Hand In

This lab is a paper submission to be handed in at the Computer Science office.
  • Hand in a printout of your marking sheet (docx or pdf) and written solution.
  • In addition to the lab itself you will need to also submit the Lab Submission Declaration on D2L. This lab will not be graded unless this declaration has been submitted


This page is maintained by Sophie Quigley (cps616@scs.ryerson.ca)
Last modified Tuesday, 11-Apr-2017 21:46:57 EDT