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
CS 170 Homework 2
2 Werewolves
You are playing a party game with n other friends, who play either as werewolves or villagers.
You do not know who is a villager and who is a werewolf, but all your friends do. There are
always more villagers than there are werewolves.
Your goal is to identify one player who is certain to be a villager.
Your allowed ‘query’ operation is as follows: you pick two people as partners. You ask
each person if their partner is a villager or a werewolf. When you do this, a villager must
tell the truth about the identity of their partner, but a werewolf doesn’t have to (they may
lie or tell the truth about their partner).
Your algorithm should work regardless of the behavior of the werewolves.
(a) Given a single person, devise an algorithm that returns whether or not that person
is a villager using O(n) queries. Just an informal description of your test and a brief
explanation of why it works is needed.
(b) Show how to find a villager in O(n log n) queries (where one query is taking two people
x and y and asking x to identify y and y to identify x).
There is a linear-time algorithm for this problem, but you cannot use it here, as we would
like you to get practice with divide and conquer.
Hint: Split the group into two groups, and use part (a). What invariant must hold for
at least one of the two groups?
Give a 3-part solution.
(c) (Extra Credit) Can you give a linear-time algorithm?
Give a 3-part solution.
Hint: Don’t be afraid to sometimes ‘throw away’ a pair of people once you’ve asked them
to identify their partners.
1
CS 170, Fall 2022 Homework 2 J. Nelson and J. W. Demmel
3 The Resistance
We are playing a variant of The Resistance, a board game where there are n players, k of
which are spies. In this variant, in every round, we choose a subset of players to go on a
mission. A mission succeeds if no spies are chosen to go on the mission, but fails if at least
one spy goes on the mission, and when a mission fails we are not told who the spies are that
went on the mission.
Come up with a strategy that identifies all the spies in O(k log(n/k)) missions. Only a
main idea and runtime analysis are needed.
4 Modular Fourier Transform
Fourier transforms (FT) have to deal with computations involving irrational numbers which
can be tricky to implement in practice. Motivated by this, in this problem you will demonstrate how to do a Fourier transform in modular arithmetic, using modulo 5 as an example.
(a) There exists ω ∈ {0, 1, 2, 3, 4} such that ω are 4th roots of unity (modulo 5), i.e., solutions
to z
4 = 1. When doing the FT in modulo 5, this ω will serve a similar role to the primitive
root of unity in our standard FT. Show that {1, 2, 3, 4} are the 4th roots of unity (modulo
5). Also show that 1 + ω + ω
2 + ω
3 = 0 (mod 5) for ω = 2.
(b) Using the FFT, produce the transform of the sequence (0, 2, 3, 0) modulo 5; that is,
evaluate the polynomial 2x+ 3x
2 at {1, 2, 4, 3} using the recursive FFT algorithm defined
in class, but with ω = 2 and in modulo 5 instead of with ω = i in the complex numbers.
All calculations should be performed modulo 5. Hint: You can verify your calculation by
evaluating the polynomial at the roots of unity using the slow method, if you like.
(c) Now perform the inverse FFT on the sequence (0, 1, 4, 0), also using the recursive algorithm. Recall that the inverse FFT is the same as the forward FFT, but using ω
−1
instead of ω, and with an extra multiplication by 4−1
for normalization.
(d) Now show how to multiply the polynomials 3x + 2x
2 and 3 − x using the FFT modulo
5. You may use the fact that the FT of (3, 4, 0, 0) modulo 5 is (2, 1, 4, 0) without doing
your own calculation.
5 Pattern Matching
Consider the following string matching problem:
Input:
• A string g of length n made of 0s and 1s. Let us call g, the “pattern”.
• A string s of length m made of 0s and 1s. Let us call s the “sequence”.
• Integer k
2
CS 170, Fall 2022 Homework 2 J. Nelson and J. W. Demmel
Goal: Find the (starting) locations of all length n-substrings of s which match g in at least
n − k positions.
Example: Using 0-indexing, if g = 0111, s = 01010110111, and k = 1 your algorithm should
output 0,2,4 and 7.
(a) Give a O(nm) time algorithm for this problem.
We will now design an O(m log m) time algorithm for the problem using FFT. Pause a
moment here to contemplate how strange this is. What does matching strings have to do
with roots of unity and complex numbers?
(b) Devise an FFT based algorithm for the problem that runs in time O(m log m). Write
down the algorithm, prove its correctness and show a runtime bound.
Hint: On the example strings g and s, the first step of the algorithm is to construct the
following polynomials
0111 → 1 + x + x
2 − x
3
01010110111 → −1 + x − x
2 + x
3 − x
4 + x
5 + x
6 − x
7 + x
8 + x
9 + x
10
To start, try to think about the case when k = 0 (i.e. g matches perfectly), and then work
from there.
(c) (Extra Credit) Often times in biology, we would like to locate the existence of a gene in
a species’ DNA. Of course, due to genetic mutations, there can be many similar but not
identical genes that serve the same function, and genes often appear multiple times in
one DNA sequence. So a more practical problem is to find all genes in a DNA sequence
that are similar to a known gene.
This problem is very similar to the one we solved earlier, the string s is complete sequence
and the pattern g is a specific gene. We would like to find all locations in the complete
sequence s, where the gene g appears, but for k modifications.
Except in genetics, the strings g and s consist of one of four alphabets {A, C, T, G} (not
0s and 1s). Can you devise an O(m log m) time algorithm for this modified problem?
6 Coding Question
As a new initiative this semester, we’re going to have short coding exercises so that you can
get a feel of what it’s like to implement these amazing algorithms that you learn about in
lecture in real code. While the notebook may seem large, the actual code you have to write
will usually be very short and direct.
There are two ways you can access the hw2.ipynb notebook and complete the problems:
1. Click here if you prefer to complete this question on Berkeley DataHub.
2. Run
git clone https://github.com/Berkeley-CS170/cs170-coding-notebooks-fa22.git
in your computer’s terminal if you prefer to complete it locally.
3
CS 170, Fall 2022 Homework 2 J. Nelson and J. W. Demmel
Notes:
• Submission Instructions: Please merge your completed Jupyter Notebook with your
written solutions for other questions and submit one merged pdf file to Gradescope.
• OH/HWP Instructions: While we will be providing conceptual help on the coding
portion of homeworks, OH staff will not look at your code and/or help you debug.
• Academic Honesty Guideline: We realize that code for some of the algorithms we ask
you to implement may be readily available online, but we strongly encourage you to not
directly copy code from these sources. Instead, try to refer to the resources mentioned
in the notebook and come up with code yourself. That being said, we do acknowledge
that there may not be many different ways to code up particular algorithms and that
your solution may be similar to other solutions available online.
4
CS 170 Homework 3
2 Updating Labels
You are given a tree T = (V, E) with a designated root node r, and a non-negative integer
label l(v) for each node v. We wish to relabel each vertex v, such that lnew(v) is equal to l(w),
where w is the k-th ancestor of v in the tree for k = l(v). In other words, v “inherits” the
label from its k-th ancestor. Follow the convention that the root node, r, is its own parent.
Design a linear time algorithm to compute the new label, lnew(v), for each v in V . Just
describe the algorithm and give a runtime analysis in terms of n = |V | and m = |E|; no proof
of correctness is necessary.
3 Where’s the Graph?
Each of the following problems can be solved with techniques taught in lecture. Construct a
simple directed graph and write an algorithm for each problem by black-boxing algorithms
taught in lecture and in the textbook.
(a) Sarah wants to do an extra credit problem for her math class. She is given three numbers:
1, x, and y. Starting from x, she needs to find the shortest sequence of additions,
subtractions, and divisions (only possible when the number is divisble by y) using 1 and
y to get to 2022. If there are multiple sequences with the shortest length, return any one
of them. She can use 1 and y multiple times. Give an algorithm that Sarah can query
to get this sequence of arithmetic operations.
(b) There are n different species of Pokemon, all descended from the original Mew. For any
species of Pokemon, Professor Juniper knows all of the species directly descended from it.
She wants to write a program that answers queries about these Pokemon. The program
would have two inputs: a and b, which represent two different species of Pokemon. Her
program would then output one of three options in constant time (the time complexity
cannot rely on n):
(1) a is descended from b.
(2) b is descended from a.
(3) a and b share a common ancestor, but neither are descended from each other.
Unfortunately, Professor Juniper’s laptop is very old and its SSD drive only has enough
space to store up to O(n) pieces of data for the program. Give an algorithm that Professor
Juniper’s program could use to solve the problem above given the constraints.
1
CS 170, Fall 2022 Homework 3 J. Nelson and J. W. Demmel
Hint: Professor Juniper can run some algorithm on her data before all of her queries and
store the outputs of the algorithm for her program; time taken for this precomputation is
not considered in the query run time.
(c) Bob has n different boxes. He wants to send the famous ”Blue Roses’ Unicorn” figurine
from his glass menagerie to his crush. To protect it, he will put it in a sequence of
boxes. Each box has a weight w and size s; with advances in technology, some boxes
have negative weight. A box a inside a box b cannot be more than 15% smaller than the
size of box b; otherwise, the box will move, and the precious figurine will shatter. The
figurine needs to be placed in the smallest box x of Bob’s box collection.
Bob (and Bob’s computer) can ask his digital home assistant Falexa to give him a list of
all boxes less than 15% smaller (but not necessarily lighter) than a given box c. Bob will
need to pay postage for each unit of weight. Find an algorithm that will find the lightest
sequence of boxes that can fit in each other in linear time (in terms of the graph).
Hint: how can we create a graph knowing that no larger box can fit into a smaller box,
and what property does this graph have?
4 The Greatest Roads in America
Arguably, one of the best things to do in America is to take a great American road trip. And
in America there are some amazing roads to drive on (think Pacific Coast Highway, Route 66
etc). An intrepid traveler has chosen to set course across America in search of some amazing
driving. What is the length of the shortest path that hits at least k of these amazing roads?
Assume that the roads in America can be expressed as a directed weighted graph G =
(V, E, d), and that our traveler wishes to drive across at least k roads from the subset R ⊆ E
of “amazing” roads. Furthermore, assume that the traveler starts and ends at her home
a ∈ V . You may also assume that the traveler is fine with repeating roads from R, i.e. the k
roads chosen from R need not be unique.
Design an efficient algorithm to solve this problem. Provide a 3-part solution with runtime in terms of n = |V |, m = |E|, k.
Hint: Create a new graph G′
based on G such that for some s
′
, t′
in G′
, each path from s
′
to t
′
in G′
corresponds to a path of the same length from a to itself in G containing at least
k roads in R. It may be easier to start by trying to solve the problem for k = 1.
5 Detecting Cyclic Vertices
Design an efficient algorithm that given a directed graph G = (V, E), outputs the set of all
vertices v such that there is a cycle containing v. In other words, your algorithm should
output a set containing all vertices v such that there exists a path from v to itself in G that
traverses at least one other unique vertex u ̸= v ∈ V .
Provide a 3-part solution with run-time in terms of n = |V | and m = |E|.
2
CS 170, Fall 2022 Homework 3 J. Nelson and J. W. Demmel
6 Coding Questions
For this week’s coding questions, we’ll be implementing FFT, DFS, and BFS, and applying
them to common problems. The Jupyter Notebooks are located under the hw3 folder here.
You can also download these files to your personal computer and complete the exercises
locally. Please complete both jupyter notebooks and make sure to submit them to the right
subparts on gradescope.
(a) fft.ipynb
(b) dfs bfs.ipynb
Notes:
• Submission Instructions: Please merge your completed Jupyter Notebooks with your
written solutions for other questions and submit one merged pdf file to Gradescope.
• OH/HWP Instructions: While we will be providing conceptual help on the coding
portion of homeworks, OH staff will not look at your code and/or help you debug.
• Academic Honesty Guideline: We realize that code for some of the algorithms we ask
you to implement may be readily available online, but we strongly encourage you to not
directly copy code from these sources. Instead, try to refer to the resources mentioned
in the notebook and come up with code yourself. That being said, we do acknowledge
that there may not be many different ways to code up particular algorithms and that
your solution may be similar to other solutions available online.
3