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

Exercise: Parallel computations

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?

Exercise: 2-Optimality of Brent

Prove that the bound given by Brent’s theorem is within a factor two of optimal

Discuss

Exercise: Lossless concatenation

You are given a set of strings \(s_1, \ldots, s_n\) and a target string \(t\).

  1. Use the brute-force 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.

  2. Analyze the work of your algorithm.

  3. Analyze the span of your algorithm.

Discuss

Exercise: Lossy concatenation

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

  1. Use the brute-force 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".

  2. Analyze the work of your algorithm.

  3. Analyze the span of your algorithm.

Discuss

Exercise: Order statistics by reduction to sorting

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:

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

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

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

  4. Give an algorithm that finds the element with any given rank in a given sequence of numbers in the same work and time.

Discuss

Exercise: Multiplication by addition

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:

  1. 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.

Discuss

Exercise: Sorting via Reduction to Convex Hulls

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).

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

  2. State the work and the span of your algorithms in terms of the work and the span of a convex hull algorithm.

Discuss

Exercise: Boring life of professors and how to help them

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.

  1. Design a brute-force algorithm that minimizes the average completion time.

  2. What is the work and span of your brute-force algorithm.

  3. Design a reduction-based algorithm by sorting that minimizes the average completion time.

  4. What is the work and span of your reduction-based algorithm.

  5. Prove that your reduction-based algorithm minimizes the average completion time.

Discuss

Chapter 2: Genome Sequencing

Exercise: Shotgun method, multiple copies

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?

Exercise: Shotgun method, correctness

Is shotgun method guaranteed to reconstruct the original genome sequence?

Exercise: Fragments and snippets

What is the difference between the set of fragments and snippets of a genome sequence.

Exercise: Start positions of snippets

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\).

Exercise: End positions of snippets

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\).

Exercise: Start and end positions of snippets

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.

Exercise: Substring check

Given a string \(s\) of length \(n\), and a string \(t\) of length \(m\):

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

  2. analyze the work and span of your algorithms.

Exercise: Hamiltonian paths on complete graphs

Prove or disprove the following.

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

  2. A permutation of vertices corresponds to a Hamiltonian path.

Exercise: Greedy mountain climbing

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.

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

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

  3. Can you end up in a ditch?

Discuss

Exercise: Generous grandmother

Your rich grandmother enjoys collecting precious items, such as jewelry, gold-plated 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.

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

  2. What is the work and span of your brute-force algorithm?

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

  4. Is your greedy algorithm optimal?

  5. What is the work and span of your greedy algorithm?

Discuss

Exercise: Greedy algorithm for Shortest Superstring Problem [also in the book]

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.

Discuss

Exercise: Superstring’iness of greedy [also in the book]

Prove that algorithm greedyApproxSS indeed returns a string that is a superstring of all original strings.

Discuss

Exercise: When greedy approximation to SS problem fails [also in the book]

Give an example input for which 'greedyApproxSS' does not return the shortest superstring.

Discuss

Exercise: Traveling on a dime [also in the book]

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?

Discuss

Chapter 3: Algorithm Analysis

Exercise: Closing the deal

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?

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

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

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

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

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

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

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

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

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

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

  11. \(W(n,m) = W(n/2,m/4) + \log{nm}\)

Exercise: Closing the real deal

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.

Exercise: Equivalence of reduce and iterate [also in the book]

Prove that reduce and iterate are equivalent when the function being applied is associative.

Exercise: Parentheses matching with scan [also in the book]

Give an algorithm for the parentheses matching problem using scan instead of iterate.

Exercise: Cost of 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.

Exercise: Iterate or reduce, that, my friend, is append 's question

We 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, cost-wise 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]]].

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

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

Exercise: Cost of collect [also in the book]

Describe how to implement collect in a way that is consistent with the specified costs.

Chapter 5: Contraction

Exercise: Ranking Sequences

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.

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

  2. Analyze the worst-case work and span of your algorithm.

  3. Analyze the best-case work and span of your algorithm.

Chapter 6: Divide and Conquer

Exercise: Parallel Merge

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.

Exercise: Binary expression trees

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 *)

  1. Using divide-and-conquer design an algorithm for evaluating a given expression tree to find the value represented by the expression.

  2. What is the worst-case work and span of your algorithm?

  3. What is the best-case work and span of your algoritm?

Index