# 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...

Assignment 3
CS-GY 6003 INET Spring 2022
Due date:
11:55pm on April 15th 2022 on Gradescope.
Instructions:
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 to solve for B(6, 2) and B(7, 4), and verify they are co
ect using
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 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:
-update/access element at index i using x[i]
-determine the length using x.length().
3
Answered 2 days AfterApr 07, 2022

## Solution

Rajeswari answered on Apr 10 2022
Assignment 3 CS-GY 6003 INET Spring 2022
The above is equivalent to proving
=*
Right side first factor is selecting 2n from 4n objects.
Left side denominator is (by using one 2 to multiply with one number)
= (1.2.3.4….(2n))^2 (because all odd numbers upto to 2n are on right side and all even numbers in first term of right side
=
Hence right side is nothing but
Thus proved
Q no2
Here p and q are prime
We write n =pq =516071
The element e belongs to {86,87….94}
E=89 since this is prime we have gcd of (89, 4566, 112) =1
So public message is e =89 and n = 516071
The private key will be the inverse of 89 in Z_515958
There decoding they factorise 516071 into 113 and 4567 (i.e. two big primes)
The receiver determines the inverse of e modulo (p-1)(q-1)
(p-1) (q-1) = 4566*112 =511392
Set up a division problem where a is larger than b.
a ÷ b = c with remainder R. Do the division. Then replace a with b, replace b with R and repeat the division. Continue the process until R = 0.
511392 ÷ 89 = 5745 R 87    (511392 = 5745 × 89 + 87)
89 ÷ 87 = 1 R 2    (89 = 1 × 87 + 2)
87 ÷ 2 = 43 R 1    (87 = 43 × 2 + 1)
2 ÷ 1 = 2 R 0    (2 = 2 × 1 + 0)
When remainder R = 0, the GCF is the divisor, b, in the last equation. GCF = 1
Taking reverse
89(-252823)+ 44*511392 =1
Inverse is coefficient of 89 i.e. -252923
Hence private key is d = -252923
S= 100^89 = 100^89 mod 516071 =(483929)^33*100mod 516071 = 123673
The receiver would do s^d and decode it.
Given that inverse of x is y. i.e. x*y = 1 mod m
Or m-1 is divisible by xy. This is possible only if gcd (x,m)=1
For any k>1, x^k will never have any common factor with m. Since (x^k, m) have gcd 1, we get x^k also definitely has an inverse
For x^3, gcd (x^3,m) =1
There exists integers s and t such that s*x^3+t*m=1
Subtracting s1(x^3-x) +m(t-t1) =0
Or s1(x^3-x) = 0 mod m.
Or x is the inverse of x^3
We have 2^9 = 512 and 2^9 mod 397 = 115 mod 297
Hence
X=285-20^3963
2x = 15 mod 29
i.e 2x = {….-14, 15, 44, 73, 102,….}
For x to be an integer we have to select only even numbers on right
i.e. x ={…-7, 22, 51,…}
Or x = 22 mod 29 = (22,51,80, …3392993)
19x = 100 mod 1000 = {-900, 100, 1100, 2100,…….17100, …36100,…,55100,…}
Only 17100 is the least integer divisible by 19
Hence x = {…,900, 1000, 1100,1200,…}
X=0 mod 100
Since x square cannot be...
SOLUTION.PDF