Time Stamp
Last updated on February 1.
Chapter 0: How to use
These exercises are provided purely as additional material to check your understanding. There may be omissions, inconsistencies, and even perhaps errors. They can be discussed publicly. A preferred way of discussion would be to use the provided links below to the relevant piazza discussion board to discuss each question. Feel free to ask crarifications, correct errors that you may have found, but of course do not share your solutions.
Chapter 1: Introduction
When designing a parallel algorithm, we have to be careful in identifying the computations that can be performed in parallel. What is the key property of such computations?
Prove that the bound given by Brent’s theorem is within a factor two of optimal
You are given a set of strings \(s_1, \ldots, s_n\) and a target string \(t\).

Use the bruteforce technique to come up with an algorithm that gives you a subset of the strings and the specific order in which they can be concatenated to obtain the target string.

Analyze the work of your algorithm.

Analyze the span of your algorithm.
You are given a set of strings \(s_1, \ldots, s_n\) and another target string \(t\).

Use the bruteforce technique to come up with an algorithm that gives you a subset of the strings and the specific order in which they can be concatenated while removing overlaps to obtain the target string. For example if you concatenate "parallel" and "elision", you will get "parallelision".

Analyze the work of your algorithm.

Analyze the span of your algorithm.
Suppose that you have an algorithm that can, for given a comparison function, comparison sort a sequence of numbers in \(\Theta(n\log{n})\) work and \(\Theta(\log^2{n})\) span. Using the problem reduction technique:

Give an algorithm that finds the minimum element in a given sequence of numbers in the same work and time.

Give an algorithm that finds the maximum element in a given sequence of numbers in the same work and time.

Give an algorithm that finds the median element in a given sequence of numbers in the same work and time.

Give an algorithm that finds the element with any given rank in a given sequence of numbers in the same work and time.
Suppose that you have an algorithm that can sum up the floating points numbers in a given sequence in \(\Theta(n)\) work and \(\Theta(\log{n})\) span. Using the problem reduction technique:

Give an algorithm that finds the product of the numbers in a given sequence of numbers in the same work and time. Explain the assumptions that you need to make sure that the result is correct.
Given a sequence of points in two dimensions \(P\), the planar convex hull problem requires finding the convex hull of the points, which is the smallest polygon containing \(P\). The polygon is defined by the sequence \(Q\), consisting of a subset of the points in \(P\) ordered clockwise, such that no three points are collinear (on the same line).

Design a sorting algorithm by reduction to the convex hull problem.

State the work and the span of your algorithms in terms of the work and the span of a convex hull algorithm.
Every morning, a professor wakes up to perform a collection of \(n\) tasks \(t_1 \ldots t_n\), where each task has a known length \(l_i\). Each day, the professor completes the tasks in some order, performing one task at a time, and thus assigning a finish time \(f_i\) to each. Over time, the professor has developed a strategy of minimizing the average completion time of these tasks, that is \(\frac{\sum_{i=1}^{n}{f_i}}{n}\). Exactly why this strategy works continues to be an (unfunded) research project.

Design a bruteforce algorithm that minimizes the average completion time.

What is the work and span of your bruteforce algorithm.

Design a reductionbased algorithm by sorting that minimizes the average completion time.

What is the work and span of your reductionbased algorithm.

Prove that your reductionbased algorithm minimizes the average completion time.
Chapter 2: Genome Sequencing
In shotgun method, we make multiple copies of the genome and divide each copy into fragments each of which is small enough to be sequenced. What is the reason for starting with multiple copies? Why do we need them?
Is shotgun method guaranteed to reconstruct the original genome sequence?
What is the difference between the set of fragments and snippets of a genome sequence.
Consider the set of snippets for a genome sequence, and let \(s\) be a superstring of the snippets, such that each snippet is contained in the superstring as substring. Prove than no two snippets can start at the same position in \(s\).
Consider the set of snippets for a genome sequence, and let \(s\) be a superstring of the snippets, such that each snippet is contained in the superstring as substring. Prove than no two snippets can end at the same position in \(s\).
Consider the set of snippets for a genome sequence, and let \(s\) be a superstring of the snippets, such that each snippet is contained in the superstring as substring. Based on the exercises above, order the snippets according to their start and end positions in $s$. Prove that this ordering is the same.
Given a string \(s\) of length \(n\), and a string \(t\) of length \(m\):

give an algorithm that checks whether \(s\) is a substring of \(t\), and

analyze the work and span of your algorithms.
Prove or disprove the following.

A Hamiltonian path on a complete graph corresponds to a permutation of vertices.

A permutation of vertices corresponds to a Hamiltonian path.
As an exotic spring break gift, you receive a plane ticket to Nepal in your name. Since you have only about 9 days of travel and it takes at least a day to get to Nepal from here, when you get there you decide the highest peak that you can climb by greedily walking in the steepest direction under your feet.

Describe a situation where you would climb the highest peak in Nepal.

Describe a situation where you would climb lowest peak in Nepal.

Can you end up in a ditch?
Your rich grandmother enjoys collecting precious items, such as jewelry, goldplated household goods. When you visit her for Spring break (instead of going to Cancun), she is very pleased and decides to reward you. She gives you a bag and a scale and instructs you to take anything you want as long as the bag does not hold any more than 10 pounds. Delighted by the surprising (based on your parents' stories of their childhood) generosity of your grandmother, you also realize that your grandmother forgot to take the price tags off the items, which gives you an idea about the value of these items, which otherwise look rather esoteric to you.

Give a brute force algorithm for selecting the items to take away with you. Is your algorithm optimal?

What is the work and span of your bruteforce algorithm?

Give a greedy algorithm for selecting the items to take away with you. Why is your algorithm greedy?

Is your greedy algorithm optimal?

What is the work and span of your greedy algorithm?
In the greedy approximation algorithm for SSSP, we remove \({s_i,s_j}\) from the set of strings but do not remove any strings from \(S\) that are contained within \(s_k\) = \(join(s_i,s_j)\). Argue why there cannot be any such strings.
Prove that algorithm greedyApproxSS
indeed returns a string that
is a superstring of all original strings.
Give an example input for which 'greedyApproxSS' does not return the shortest superstring.
Consider the following greedy algorithm for TSP. Start at the source and always go to the nearest unvisited neighbor. When applied to the graph described above, is this the same as the algorithm above? If not what would be the corresponding algorithm for solving the TSP?
Chapter 3: Algorithm Analysis
Find the closed from for the following recursions. First use the tree method by writing out the sum and solving it. Then apply the brick method and compare your answers. Do you see how the brick method follows from the tree method?

\(W(n) = 3W(n/2) + n\)

\(S(n) = 2S(n/4) + n\)

\(W(n) = 2W(n/4) + n^2\)

\(W(n) = 2W(n/2) + n\log{n}\)

\(W(n) = 2W(n/2) + n\log{n}\)

\(S(n) = 2S(\sqrt{n}) + \log{n}\)

\(W(n) = W(n/3) + W(n/4) + n\)

\(S(n) = \max{(S(n/3),S(n/4))} + \log{n}\)

\(W(n,m) = 2W(n/2,m/4) + nm\)

\(W(n,m) = W(n/2,m/4) + n^2m\)

\(W(n,m) = W(n/2,m/4) + \log{nm}\)
Show that \(W(n) = 2W(n/2) + \log{n} \in O(n)\) by using tree of substitution method.
Chapter 4: Sequences
Exercise: Matching parantheses correctly [also in the book]
Prove that the iterate
based algorithm indeed solves the
parentheses matching problem.
reduce
and iterate
[also in the book]Prove that reduce
and iterate
are equivalent when the
function being applied is associative.
scan
[also in the book]Give an algorithm for the parentheses matching problem using
scan
instead of iterate
.
map
via tabulate
[also in the book]Earlier we showed how to implement map
using tabulate
. Decide
whether this implementation preserves asymptotic costs for an
ArraySequence, and then for TreeSequence.
Iterate
or reduce
, that, my friend, is append
's questionWe have seen that iterate
and reduce
have the same extrinsic
semantics when they are given an associative operation and an identity
value: that is they return the same result with the same sequence.
Intrinsically, however, costwise that is, they may differ.
Suppose that you are given a sequence \(S_n\) parameterized by \(n\), whose \(i^{th}\) element is the sequence of natural numbers. For example, \(S_3 = [[0\), [0,1], [0,1,2]]].

What is the work and span of \(\prod^{`append` [\)} S_3], that is the work and span of appending the sequences using iterate?

What is the work and span of \(\sum^{`append` [\)} S_3], that is the work and span of appending the sequences using
reduce
?
collect
[also in the book]Describe how to implement collect
in a way that is consistent with the
specified costs.
Chapter 5: Contraction
Given a sequence of \(n\) numbers and and a rank \(r < n\), the you want to find the element of the sequence with the given rank. For example if the input is \([1,3,2,4\)] and we are asked to find the element with rank \(0\)$ then the answer is \(1\) because \(1\) is the element with rank \(0\) smallest element.

Give a contraction algorithm for finding the element of the sequence with a given rank.

Analyze the worstcase work and span of your algorithm.

Analyze the bestcase work and span of your algorithm.
Chapter 6: Divide and Conquer
Give a parallel algorithm for merging two sorted sequences. If the sequences have length \(m\) and \(n\), then your algorithm should perform \(O(n+m)\) in \(O(\log{(n+m)})\) span.
A binary expression tree is a tree where each internal node is a binary operation such as multiply or add and each leaf is a natural number.
datatype binop = Plus  Minus  Multiply  Divide datatype exp_tree = Leaf of int  Node of (exp_tree * binop * exp_tree) function evaluate (t: exp_tree) = ... (* your code here *)

Using divideandconquer design an algorithm for evaluating a given expression tree to find the value represented by the expression.

What is the worstcase work and span of your algorithm?

What is the bestcase work and span of your algoritm?