Homework #1 Solution

Description

1. In the class we showed how to construct the binary representations for numbers 1, 2, 3, …, n by doing binary addition:

BINARYONETON(n)

X 0

for i 1 to n
starting from right to left in X , find the first digit that is 0 and assume it is the kth digit

X flip the kth digit of X to 1 and flip 1, 2, . . . , (k 1)th digit of X to 0 print X

The bit complexity of an algorithm counts the number of bit operations in terms of the length of the input. What is the bit complexity of the algorithm BINARYONETON?

2. Suppose you are playing the game of NIM. This game begins with a placement of n rows of matches on a table. Each row i has mi matches. Players take turns selecting a row of matches and removing any or all of the matches in that row. Whoever claims the final match from the table wins the game. This game has a winning strategy based on writing the count for each row in binary and lining up the binary numbers (by place value) in columns. We note that a table is favorable if there is a column with an odd number of ones in it, and the table is unfavorable if all columns have an even number of ones.

Example: Suppose we start off with three rows of matches of 7, 8 and 9. The binary representa-tions of number of matches are 7 = 0111, 8 = 0111, 9 = 1001. Therefore, the board will look like
this
2 3
0 1 1 1

41 0 0 05

1 0 0 1

Since the third row from the right and the second row from the right, each has odd numbers of ones, the table is favorable.

(a) Prove that, for any favorable table, there exists a move that makes the table unfavorable. Prove also that, for any unfavorable table, any move makes the table favorable for one’s opponent. Write the algorithm that on an input of favorable table outputs the row and the number of matches to remove from that row, in order to make the table unfavorable.

(b) Given an input of favorable table, can you determine whether there exist multiple ways to make the table unfavorable? How?

(c) Design an algorithm that always wins the game if given a favorable table.

3. Recall that a knight can make one of eight legal moves. A closed knight’s tour on an 8 8 chess-board, that is, a circular tour of knight’s moves that visits every square of the chessboard exactly once before returning to the first square. Such a tour is also known as a Eulerian tour.

1

A closed knight tour for 8 8 chessboard

(a) Given a graph G = fV, Eg. G contains two cycles C1 and C2 where each cycle visits half of the vertices exactly once and C1 and C2 do not share any vertex. Suppose there exists a circle S in G made of four edges: S = f(va, vb), (vb, vc ), (vc , vd ), (vd , va)g, where (va, vb) is an edge in cycle C1 and (vc , vd ) is an edge in cycle C2, while the two other edges are neither in C1 nor in C2. Show that then there exists a single cycle in G that visits every vertex in G exactly once.

(b) Give an algorithm generates a closed knight’s tour on a 16 16 chessboard. (Hint: you may use a closed knight’s tour for 8 8 as a starting point)

(c) Give an algorithm generates a closed knight’s tour on any 2k 2k chessboard for all k 3.

4. Given an array B[1..n] that stores a binary representation of a positive integer, where each B[i] is either 0 or 1. For example, B = [1, 1, 0], which represents 6 in binary.

(a) Design a recursive algorithm that evaluates the actual value of the array B represents. Your

algorithm is NOT allowed to use any pre-calculated table for powers of 2. For example, your algorithm cannot use 23 = 8 or 24 = 16 as a known fact without actually calculating it.
(b) Unfold the recursive algorithm (in which a procedure call on itself with a different parame-ter) into an iterative algorithm that does not call any procedure.

Æ Express your algorithm in a well-structured manner. Pseudo code in the textbook has good ex-amples to follow. Avoid using a long continuous piece of text to describe your algorithm. Start each problem on a NEW page. Unless specified, you should justify the time complexity of your algorithm and why it works. For grading, we will take into account both the correctness and the clarity. Your answers are supposed to be in a simple and understandable manner and sloppy answers are expected to receiver fewer points.

Æ Homework assignments are due on Gradescope. Email attachments or paper submissions are NOT acceptable.

Æ Raw photo is NOT acceptable. Upload your homework as a PDF scan by using a scanner or mobile scanner app. Match each problem with your answer on Gradescope. Use dark pen or pencil and your handwriting should be clear and legible.
Æ We recommend using LATEX, LYX or other word processing software for writing the homework. This is NOT a requirement but it helps us to grade and give feedback.

2