Description

CS 417 HOMEWORK 1

Problem 1. Let a, b, d ∈ Z. Suppose that d | a and d | b.
(1) Show that d | a − b.
(2) Let m, n ∈ Z. Show that d | ma + nb.
Problem 2. Let a1, a2, . . . , an be integers. The greatest common divisor of a1, a2, . . . , an,
denoted by gcd(a1, a2, . . . , an), is the largest positive integer d such that d | ai
for each
1 ≤ i ≤ n. It is known that
gcd(a1, a2, . . . , an) = gcd(an, gcd(a1, . . . , an−1)).
Given a list of integers, say alist.
(1) Write a recursive function named recursive gcd(alist) that takes alist as an input
and return the greatest common divisor of all elements in alist.
(2) Write a non-recursive function, named non recursive gcd(alist) to achieve the same
goal.
For this problem, you can use any functions that we wrote to compute gcd(a, b) for two
given integers (this is the base case).
1

HOMEWORK 3 CS 417

Problem 1. Use Gauss’s method to show that
1 + 3 + 5 + . . . + (2n − 1) = n
2
.
For example
1 + 3 = 4 = 22
, 1 + 3 + 5 = 9 = 32
.
Problem 2. (10 points) Do 5 questions in Section 3.10 (Discussion questions).
For the remaining problems, please submit a python file (jupyter notebook is also fine).
For questions that ask for an explanation, please provide your answers as comments.
Problem 3. (10 points) Do Questions 4 and 5 in Section 3.11 (Programming Exercises).
Problem 4. A triangular number is a number that can be arranged in the shape of an
equilateral triangle. Mathematically, n is a triangular number if we can find a positive
integer k such that
n =
k(k + 1)
2
.
The first few triangular numbers are described in the picture below.
Write a function to check whether a given number n is triangualr or not. What is the
big O-performance of your program?
Problem 5. Let am be a sequence given by the following recursive formula
a0 = 2, a1 = 5, am = 5am−1 − 6am−2 for m ≥ 2.
The following questions are considered to be independent from each other (though, if you
want to use one to solve the others, that is fine).
1
(1) Write a function to calculate the kth term of this sequence. You function should
take k as the argument and return ak.
(2) Given a number n. Write a function to check whether n belongs to this sequence
(namely, there exists k such that ak = n). For example, 13 belongs to this sequence
because a2 = 13. On the other hand, 20 is not a member of this sequence. Use
a count variable inside your function to estimate the number of assignments in
your function for n = 102
, 103
, 104
, 105
, 106
, 107
. What do you think is the big Operformance of your algorithm?
(3) What if I tell you that the general formula for am is am = 2m + 3m.
2