Description
1. Prove the correctness of the following algorithm of binary addition.
Input: n (in binary representation)
Output: n + 1 (in binary representation)
find the first digit that is 0 starting from right to left. Denote the position of first “0” to i.
flip the i
th digit to 1 and flip the 1, 2, . . . ,(i 1)th digit to 0
return the flipped number n0
2. A binary tree is a tree that every node has at most 2 children. The depth of a tree is the longest path that
starts from the root and ends at a leaf. Give a recursive and iterative algorithm that compute the depth of
a binary tree. Justify the correctness and the complexity of your algorithms.
3. You are given integers n and d in decimal representation. Describe a recursive and iterative version of
elementary-school long division to divide n by d. Your primitives are addition, subtraction, multiplication
of integers a and b, and integer division of a by b if a < 10b. Analyze the complexity (number of operations)
of your algorithm. An operation is using any of the primitives between a and b.
4. 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 the 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 representations of
number of matches are 7 = 0111, 8 = 0111, 9 = 1001. Therefore, the board will look like this
2
4
0111
1000
1001
3
5
Since the third row from the right and the second row from the right, each have 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, to make the table unfavorable.
(b) Give a winning strategy for this game.
∆ Homework assignments are strictly due on the exact time indicated. Please submit a hard copy of your
homework solution with your Name, Bruin ID, Discussion Number, clearly indicated on the first page.
If your homework consists of multiple pages, please staple them together. Email attachments or other
electronic delivery methods are not acceptable.
∆ We recommend to use LATEX, LYX or other word processing software for submitting the homework. This is
not a requirement but it helps us to grade the homework and give feedback. For grading, we will take into
account both the correctness and the clarity. Your answer are supposed to be in a simple and understandable
manner. Sloppy answers are expected to receiver fewer points. Unless specified, you should justify your
algorithm with complete proof of correctness and complexity.
