Description
1 Study Group
List the names and SIDs of the members in your study group. If you have no collaborators,
you must explicitly write “none”.
2 Course Policies
(a) What dates and times are the exams for CS170 this semester? Are there planned alternate
exams?
Note: We will make accommodations for students in faraway timezones.
(b) Homework is due Mondays at 10:00pm, with a late deadline at 11:59pm. At what time
do we recommend you have your homework finished?
(c) We provide 2 homework drops for cases of emergency or technical issues that may arise
due to homework submission. If you miss the Gradescope late deadline (even by a few
minutes) and need to submit the homework, what should you do?
(d) What is the primary source of communication for CS170 to reach students? We will send
out all important deadlines through this medium, and you are responsible for checking
your emails and reading each announcement fully.
(e) Please read all of the following:
(i) Syllabus and Policies: https://cs170.org/syllabus/
(ii) Homework Guidelines: https://cs170.org/resources/homework-guidelines/
(iii) Regrade Etiquette: https://cs170.org/resources/regrade-etiquette/
(iv) Forum Etiquette: https://cs170.org/resources/forum-etiquette/
Once you have read them, copy and sign the following sentence on your homework submission.
“I have read and understood the course syllabus and policies.”
3 Understanding Academic Dishonesty
Before you answer any of the following questions, make sure you have read over the syllabus
and course policies (https://cs170.org/syllabus/) carefully. For each statement below,
write OK if it is allowed by the course policies and Not OK otherwise.
(a) You ask a friend who took CS 170 previously for their homework solutions, some of which
overlap with this semester’s problem sets. You look at their solutions, then later write
them down in your own words.
1
CS 170, Homework 1
(b) You had 5 midterms on the same day and are behind on your homework. You decide to
ask your classmate, who’s already done the homework, for help. They tell you how to do
the first three problems.
(c) You look up a homework problem online and find the exact solution. You then write it
in your words and cite the source.
(d) You were looking up Dijkstra’s on the internet, and inadvertently run into a website with
a problem very similar to one on your homework. You read it, including the solution,
and then you close the website, write up your solution, and cite the website URL in your
homework writeup.
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,Homework 1
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
