Description
4 Recurrence Relations
For each part, find the asymptotic order of growth of T; that is, find a function g such that
T(n) = Θ(g(n)). In all subparts, you may ignore any issues arising from whether a number
is an integer.
(a) T(n) = 4T(n/4) + 32n
(b) T(n) = 4T(n/3) + n
2
(c) T(n) = T(3n/5) + T(4n/5) (We have T(1) = 1)
5 In Between Functions
Find a function f(n) ≥ 0 such that:
• For all c > 0, f = Ω(n
c
)
• For all α > 1, f = O(α
n
)
Give a proof for why it satisfies both these properties.
2
CS 170, Fall 2022 Homework 1 J. Nelson and J. W. Demmel
6 Sequences
Suppose we have a sequence of integers An, where A0, . . . , Ak−1 < 50 are given, and each
subsequent term in the sequence is given by some integer linear combination of the k previous
terms: Ai = Ai−1b1 + Ai−2b2 + · · · + Ai−kbk. You are given as inputs A0 through Ak−1 and
the coefficients b1 through bk.
(a) Devise an algorithm which computes An mod 50 in O(log n) time (Hint: use the matrix
multiplication technique from class). You should treat k as a constant, and you may
assume that all arithmetic operations involving numbers of O(log n) bits take constant
time. 1
Give a 3-part solution as described in the homework guidelines.
(b) Devise an even faster algorithm which doesn’t use matrix multiplication at all. Once
again, you should still treat k as a constant.
Hint: Exploit the fact that we only want the answer mod a constant (here 50).
Give a 3-part solution as described in the homework guidelines.
7 Decimal to Binary
Given the n-digit decimal representation of a number, converting it into binary in the natural
way takes O(n
2
) steps. Give a divide and conquer algorithm to do the conversion and show
that it does not take much more time than Karatsuba’s algorithm for integer multiplication.
Just state the main idea behind your algorithm and its runtime analysis; no proof of
correctness is needed as long as your main idea is clear.
1A similar assumption – that arithmetic operations involving numbers of O(log N) bits take constant time,
where N is the number of bits needed to describe the entire input – is known as the transdichotomous word
RAM model and it is typically at least implicitly assumed in the study of algorithms. Indeed, in an input of
size N it is standard to assume that we can index into the input in constant time (do we not typically assume
that indexing into an input array takes constant time?!). Implicitly this is assuming that the register size on
our computer is at least log N bits, which means it is natural to assume that we can do all standard machine
operations on log N bits in constant time.
3