A. Palindrome

Problem Description

A palindromic number is an integer that is the same when the digits are reversed. For example, 121 and 625526 are palindromic, but 625 is not a palindromic number.

Input:

The input is in palindrome.txt. The first line of the input contains the line count m (1 m 1,000), which is the number of lines that follows the first line. Each of the following lines contains an integer of n digits (1 n 5,000). Sample input:

3.

12333.

92837465.

1000000000000000123.

Output:

The output consists of m lines. Each line transforms the corresponding input line into a palindrome by concatenating the input and its digits in reversed order. To minimize the output length, you must not repeat the trailing digit (or, digits if there are multiple occurrences of the same digit) of the input integer.

Sample output:

1233321.

928374656473829.

1000000000000000123210000000000000001.

Submission and Grading Information

1. The expected complexity is O(n).
2. Your can assume that the input integers are positive, and does not start with zero. Write a code A.YourNSID.java that reads palindrome.txt and writes the output in a file called A.YourNSID.txt. Only submit the file A.YourNSID.java in Moodle.
3. The score will be 0 if your program does not terminate within 10 seconds. If your output is correct for k out of m inputs, then you will receive a score of .

Every palindrome of 4 digits is divisible by 11 (good to know, but not related to this assignment). Can you prove it in a midterm question?

B. Beer Time

Problem Description

A group of n students of CMPT360 is standing around a circle, but there are (n1) bottles of water and only 1 bottle of beer. They came up with an algorithm to solve their problem (yes, this is how those students are). They will start counting clockwise, starting at position 1, removing every second remaining person to get out of the circle and have a bottle of water. As the process goes on, the circle becomes smaller and smaller, until only one lucky student remains, who can have that only bottle of beer. A smart student quickly computes the position J(n) that would get the bottle of beer and stand in that position.

For example, if there are 10 people numbered 1 to 10 in clockwise order around the circle, then the order of getting a water bottle is 2, 4 , 6, 8, 10, 3, 7, 1, 9, as follows (* indicates the position where the counting starts):

*1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (initial state)

1, *3, 4, 5, 6, 7, 8, 9, 10

1, 3, *5, 6, 7, 8, 9, 10

1, 3, 5, *7, 8, 9, 10

1, 3, 5, 7, *9, 10

*1, 3, 5, 7, 9

1, *5, 7, 9

1, 5, *9

*5, 9

*5 (survivor)

Here the person at the 5th position survives. Therefore, J(10) = 5. A quick way to find the J(n) is to use the following:

J(1) = 1

J(2^m + x) = 2x +1,

where m 0 and 0 x < 2m.

For example, if n = 10, then J(n) = J(10) = J(2³+2). Therefore in this case, m = 3 and x = 2, and hence J(10) = 22+1 = 5. Similarly, if n = 16, then J(n) = J(16) = J(2⁴+0). Therefore, m = 4,x = 0, and J(16) = 2 0+1 = 1.

Input:

The input is in beer.txt. The first line of the input contains the line count c (1 c 1,000), which is the number of lines that follows the first line. Each of the following lines contains an integer n (1 n 10,000). Sample input:

2.

16. 10.

Output:

The output consists of c lines. Each line prints the lucky position J(n) of the corresponding input.

Sample output:

1.

5.

Submission and Grading Information

1. The expected complexity is O(logn).
2. Write a code B.YourNSID.java that reads beer.txt and writes the output in a file called B.YourNSID.txt. Only submit the file B.YourNSID.java in Moodle.
3. The score will be 0 if your program does not terminate within 3 seconds. If your output is correct for k out of m inputs, then you will receive a score of .

C. Recursion

Recursion may appear in various contexts and in different forms. For fast implementation, we should always aim at transforming recursions into a simpler form of computation. In this assignment, the task is to evaluate X(), which is defined as follows:

0,if m = 0 or n = 0

is odd and m is even n is even otherwise.

Input:

The input is in recursion.txt. The first line of the input contains the line count c (1 c 1,000)_{, which is the number of lines that follows the first line. Each of the following lines} contains a pair of integers m,n (1 m,n 10,000). Sample input:

3.

102,21.

10000,10000.

Output:

The output consists of c lines. Each line prints X(m,n). Sample output:

2060.

100010000.

Submission and Grading Information

1. The expected complexity is O(1).
2. Write a code C.YourNSID.java that reads recursion.txt and writes the output in a file called C.YourNSID.txt. Only submit the file C.YourNSID.java in Moodle.
3. The score will be 0 if your program does not terminate within 3 seconds. If your output is correct for k out of m inputs, then you will receive a score of .

D. Software Testing (Time Limit: 10 Seconds)

Murphys law states that things will go wrong in any given situation, if you give them a chance, or more commonly, whatever can go wrong, will go wrong. Many automated software testing tries to test for all possible inputs, whenever the number of possibilities are reasonably small.

An image is normally processed by a set of three satellite modules m₁,m₂,m₃ in this order. The image might get corrupted during the transfer. During this process, a module m_j can request any of its predecessor m_i, where 1 i < j 3, to resend the information. Upon receiving a resend request, m_i must pass the data to the next module m_i+1.

A normal processing must start at m₁ and end at m₃. If the maximum number of total resend requests exceeds n, then the system generates an alarm.

We want to count the number of different ways with exactly n resend requests. If n = 1, then there are exactly 3 different ways (* denotes the resend request).

12*123 [2 gets the corrupt data and decides to ask from 1]

123*23 [3 gets the corrupt data and decides to ask from 2]

123*123 [3 gets the corrupt data and decides to ask from 1] If n = 2, then the number of different ways is 8.

12*12*123

12*123*123

12*123*23

123*23*23

123*23*123

123*123*23

123*123*123

123*12*123

Input:

The input is in software.txt. The first line of the input contains the line count m (1 m 1,000), which is the number of lines that follows the first line. Each of the following lines contains an integer n (1 n 10,000). Sample input:

2.

1.

2.

Output:

The output consists of m lines. Each line prints the number of different ways that exactly n resend requests can happen.

Sample output:

3.

8.

Submission and Grading Information

1. The expected complexity is O(n).
2. Write a code D.YourNSID.java that reads software.txt and writes the output in a file called D.YourNSID.txt. Only submit the file D.YourNSID.java in Moodle.
3. The score will be 0 if your program does not terminate within 10 seconds. If your output is correct for k out of m inputs, then you will receive a score of .

E. World of Unknowns, Time limit: 3 seconds

The Collatz conjecture is about a sequence: start with any positive integer n. Then each term is obtained from the previous term as follows: if the previous term is even, the next term is one half the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that no matter what value of n, the sequence will always reach 1.

is odd f(n/2),otherwise.

Your task is to count the number of terms in the sequence. For example, if n = 12, then the sequence has 10 terms: 12,6,3,10,5,16,8,4,2,1.

Input:

The input is in sequence.txt. The first line of the input contains the line count m (1 m 1,000), which is the number of lines that follows the first line. Each of the following lines contains an integer n (1 n 10,000). Sample input:

2.

12.

27.

Output:

The output consists of m lines. Each line prints the number of terms in the sequence of f(n). Sample output:

10.

112.

Submission and Grading Information

1. The complexity is unknown, but try your fastest algorithm 🙂
2. Write a code E.YourNSID.java that reads sequence.txt and writes the output in a file called E.YourNSID.txt. Only submit the file E.YourNSID.java in Moodle.
3. The score will be 0 if your program does not terminate within 10 seconds. If your output is correct for k out of m inputs, then you will receive a score of .