# 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 Θ(n2) and is mapping reducible to Problem B in constant time. Note: Θ(n2) means that Problem A has an exact time complexity of n2.
1. True or False. Problem B could have Θ(n) time complexity.
2. True or False. Problem B could have Θ(n2) time complexity.
3. True or False. Problem B could have Θ(n3) 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 Θ(n2).
1. True or False. Problem A could have Θ(n) time complexity.
2. True or False. Problem A could have Θ(n2) time complexity.
3. True or False. Problem A could have Θ(n3) time complexity.