Assignment 3
CS-GY 6003 INET Spring 2022
Due date:
11:55pm on April 15th 2022 on Gradescope.
Instructions:
Write or type out your solutions and hand in on Gradescope before the deadline. Justify your answers!
Question 1: Counting
.
(a) 5 points Use a combinatorial argument to prove each of:
(4n)!
22n · n! · n!
=
(
4n
2n
)
(2n− 1)2(2n− 3)2(2n− XXXXXXXXXX)
(b) 4 points Use pascal’s triangle to prove(
n + 1
+ 1
)
=
n∑
k=
(
k
)
(c) 3 points Use Pascal’s identify to prove that:
22n = 2
[(
2n
0
)
+
(
2n
1
)
+
(
2n
2
)
+
(
2n
3
)
+ . . . +
(
2n
n− 1
)]
+
(
2n
n
)
Question 2: Number Theory
.
(a) 4 points Let p = 4567 and q = 113. Pick a public key e where 86 ≤ e ≤ 94. Encode the message
m = 100 and show how it is successfully decoded.
(b) 3 points Suppose that in mod m we determine that the inverse of x is y. Explain why xk has an
inverse in mod m for any k ≥ 1. What is the inverse of x3?
(c) 5 points Solve the following for x in mod 397. Show your work without using a calculator.
XXXXXXXXXXx ≡ 2402 mod 397
(d) 5 points Use CRT to find a value of 0 ≤ x < XXXXXXXXXXthat satisfies the following congruences:
2x ≡ 15 mod 29
19x ≡ 100 mod 1000
x ≡ 52 mod 117
(e) 5 points Use CRT to solve the following for 0 ≤ x < 899 . You must find all 4 distinct solutions
in that range.
x2 ≡ 33 mod 29
x2 ≡ 66 mod 31
1
(f) 5 points Determine integers s and t such that
5744s = 3260t mod 4
(g) 6 points For each of the following, solve for x or prove that there is no solution:
• 6x + 5 ≡ 20 mod 91
• 13x + 2 ≡ 20 mod 91
• 7x + 2 ≡ 23 mod 91
(h) 6 points
• Update the solution to problem 14 in set 11 so that Power(x,a,n) returns the value of xa mod n,
where 0 ≤ a < n is an integer.
• Write a procedure FastExp(x,a,p) which determines the value of xa mod p where p ≥ 2 is a prime
number. Your procedure can assume that a ≥ 0 and n ≥ 1, which are both integers. Your solution
must use Fermat’s Last theorem, and may call Power(x,a,n) from above.
Question 3: Recu
ence Relations:
. (a) 6 points
• Let F (n), n ≥ 1 be the Fibonacci sequence defined in class. Used the closed-form solution of the
Fibonacci sequence to find F (15). Does this give you the exact same value as if you compute F (15)
using the recu
ence? Explain why or why not.
• Define a sequence g(n) , n ≥ 1 as follows: Let g(1) = 5 and g(2) = 8, and g(n) = g(n− 1) + g(n− 2)
for n ≥ 3. What is the closed-form solution for g(n)? Justify your answer.
.
(b) 6 points A child is building a tower out of a total of n blocks. Let r of those blocks be red, and
the remaining blocks are blue. The child builds a tower using all of the blocks. Suppose that the tower is
uilt with no adjacent red blocks. Let B(n, r) be the number of ways to build such a tower. Write a
ecursive definition for B(n, r), where n ≥ 0, and 0 ≤ r ≤ n. Include your base cases. What is the solution
to this recu
ence? Use your recu
ence to solve for B(6, 2) and B(7, 4), and verify they are co
ect using
your solution to the recu
ence.
(c) 5 points Solve the following recu
ence and prove your result is co
ect using induction:
a0 = 1
a1 = 1
an = 4an−2 + 1 for n ≥ 2
(d) 4 points Solve the following recu
ence:
an = 5an−2 − 4an−4 for n ≥ 4
a0 = 0, a1 = 1, a2 = 1, a3 = 1
(e) 5 points Suppose we are given a rod of length n. We can cut rod into pieces in such a way that
each piece length is a natural number of size at least 1. There are many ways to cut the rod. For example,
if n = 5, we could cut it into pieces of size 1, 2, 2 or 4, 1 etc. Write a recursive definition for P (n, k) which
is the number of ways to cut a rod of length n where the maximum size of the pieces is k. Your definition
2
is for n ≥ 1 and k ≥ 1. You do not need to solve the recu
ence. Use your recu
ence to solve for P (7, 7)
and P (7, 2).
(f) 5 points A child is building a tower out of red, black, and green blocks. The red and black blocks
have size 1 and the green block has size 2. A tower of height n is built using a sequence of the colored
locks, with the condition that no red blocks are adjacent. Write a recursive definition T (n), n ≥ 1, fo
the number of possible towers of height n. You do not need to solve the recu
ence.
Question 4: Recursive Procedures
.
(a) 6 points Recall that in week 6 we considered the problem of distributing n identical items into k
unlabelled groups. In this problem, you must write a recursive procedure called NumberPartitions(n, k)
that returns the number of ways of distributing n identical pennies into k piles, where each pile has at
least 1 penny. The piles are not labelled, so the only thing that matters is the number of coins in each
pile. Your procedure must function properly for n ≥ 1 and 1 ≤ k ≤ n. Use your procedure to verify the
output for n = 8 and k = 4.
(b) 6 points Consider a making a postage of n cents using stamps of size 2, 3 and 4. Suppose we must
use at least one of each stamp denomination. Write a recursive procedure called PrintPostage(n) that
prints out a set of stamps that create a postage of size n. You must determine the co
ect base case and
ensure that your recursive procedure handles that co
ectly. If no postage is possible, your procedure must
print “No postage”. Your procedure must handle all inputs of n ≥ 0.
For example: FindPostage(25) outputs stamps 4, 4, 4, 4, 4, 3, 2. There are other options possible, but just
one co
ect option must be printed.
(c) 6 points Recall problem 4(c) from assignment 2. Consider a new version of this problem where the
ills have denominations 1, 5, 52, 53, XXXXXXXXXXAs in the previous assignment, you owe your friend a debt of n
dollars. You must transfer a set of bills between you and your friend in such a way that the debt is repaid.
In this case, a bill denomination may be used at most two times.
Write a recursive procedure called PrintBills(n) that returns a list of the necessary bills, for n ≥ 0.
The list should include positive numbers for bills you give your friend, and negative numbers for bills you
friend gives you. For example, if n = 21, the output list should be [52,−5, 1]. For n = 32, the output list
should be [25, 5, 1, 1].
*Note: This is not a course on data-structures. So you may assume that you can create an empty list
with the pseudo-code “x = list()” and use the following operations:
-add elements to the list using x.add(25)
-update/access element at index i using x[i]
-determine the length using x.length().
3