Problem Set 5—Lower Bounds for Problems

Purpose

This problem set develops your ability to reason about lower bounds on the solution time of whole problems.

Background

This problem set is based on material covered in lectures between October 15 and October 27. Part of this material, about a decision-tree analysis of the lower bound for sorting, is also covered in section 8.1 of our textbook.

Activity

Solve each of the following problems.

Problem 1

Prove that the lower bound for computing the dot product of two n-element vectors is Θ(n). Assume that any constant-time arithmetic operations used by algorithms for this problem operate on a constant number of operands.

Problem 2

Imagine lists of numbers that begin with some number (possibly 0) of occurences of 0, followed by any number (again, possibly 0) of non-zero values. The key thing about these lists is that all occurrences of 0 come before any occurrence of a non-zero value.

Now consider the problem of finding the first non-zero value in such a list (with the case where there are no non-zero values detected and reported as valid but unusual). Find and prove a lower bound for comparison-based algorithms for solving this problem. Express your bound as an asymptotic function of list length.

Problem 3

Consider lists containing exactly three numbers.

Part A

How many leaves do decision trees for sorting such lists have?

Part B

What is the minimum height for these decision trees? Assume all decisions are based on comparisons between pairs of elements of the list.

Part C

Give an example of a minimum-height decision tree for sorting such lists. Indicate what comparison is represented by each internal node in the tree, and what each leaf represents.

Part D

Show the path that sorting the list ( 7, 5, 12 ) would take through your decision tree.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.