CSCI 338: Homework 7

Sample Solution

Problems 1 (3 points) and 5/6 (4 points) were chosen for careful grading.

Problems - This homework set is complete.

1. Problem 5.1 on page 239.
2. Problem 5.3 on page 239.
3. Problem 5.4 on page 239.
4. Program the Turing Machine Simulator to simulate a Linear Bounded Automaton (LBA). Assume that Γ = {L, 0, 1, R} where L denotes the leftmost cell in the LBA and R denotes the rightmost cell in the LBA. The LBA should add one to the initial binary number, working like an analog-style car odometer . For example, if the input tape starts with L01011R, it should end with L01100R. As another example, if the input tape starts with L111R, it should end with L000R. You may assume that the binary number will contain one or more digits. Submission Note: To earn points for this answer, place your solution in a .txt file and upload it separately from the answers to the other problems. This allows your solution to be copied and pasted into the Turing Machine Simulator for testing.
5. Suppose that Problem A has a known time complexity of Θ(n²) and is mapping reducible to Problem B in constant time. Note: Θ(n²) means that Problem A has an exact time complexity of n².
   1. True or False. Problem B could have Θ(n) time complexity.
   2. True or False. Problem B could have Θ(n²) time complexity.
   3. True or False. Problem B could have Θ(n³) time complexity.
6. Suppose that Problem A is mapping reducible to Problem B in constant time and Problem B has a known time complexity of Θ(n²).
   1. True or False. Problem A could have Θ(n) time complexity.
   2. True or False. Problem A could have Θ(n²) time complexity.
   3. True or False. Problem A could have Θ(n³) time complexity.

Grading - 10 Points

• To earn points, your answers must be easily readable.
• You will earn 1 point per problem for a reasonable looking solution.
• At least one problem will be selected for careful grading. The rest of the 10 points will be allocated to these problems.
• Solutions to all problems will be posted.

Partners

You may work alone or you may partner with one classmate. If you work with a partner, submit only one solution with both of your names on it.

Submission

Upload your submission to the D2L Dropbox for Homework 7 no later than 7:00 p.m. on Friday, April 15th. Late submissions receive no credit, but partial credit can be earned by making an ontime submission.