数据结构与算法分析c++版答案

Preface ii

1 Data Structures and Algorithms 1 2 Mathematical Preliminaries 5 3 Algorithm Analysis 17

4 Lists, Stacks, and Queues 23 5 Binary Trees 32 6 General Trees 40 7 Internal Sorting 46

8 File Processing and External Sorting 9Searching 58 10 Indexing 11 Graphs 69

12 Lists and Arrays Revisited 76

13 Advanced Tree Structures 82 i

ii Contents

14 Analysis Techniques 88 15 Limits to Computation 94

Preface

Contained herein are the solutions to all exercises from the textbook A Practical

Introduction to Data Structures and Algorithm Analysis, 2nd edition.

For most of the problems requiring an algorithm I have given actual code. In

a few cases I have presented pseudocode. Please be aware that the code presented

in this manual has not actually been compiled and tested. While I believe the algorithms

to be essentially correct, there may be errors in syntax as well as semantics.

Most importantly, these solutions provide a guide to the instructor as to the intended

answer, rather than usable programs.

1

Data Structures and Algorithms

Instructor’s note: Unlike the other chapters, many of the questions in this chapter

are not really suitable for graded work. The questions are mainly intended to get

students thinking about data structures issues.

This question does not have a specific right answer, provided the student

keeps to the spirit of the question. Students may have trouble with the concept of “operations.”

This exercise asks the student to expand on their concept of

an integer representation.

A good answer is described by Project , where a singly-linked list is suggested. The most straightforward implementation stores each digit

in its own list node, with digits stored in reverse order. Addition and multiplication

are implemented by what amounts to grade-school arithmetic. For addition, simply march down in parallel through the two lists representing

the operands, at each digit appending to a new list the appropriate partial

sum and bringing forward a carry bit as necessary. For multiplication, combine

the addition function with a new function that multiplies a single digit

by an integer. Exponentiation can be done either by repeated multiplication

(not really practical) or by the traditional Θ(log n)-time

algorithm based on

the binary representation of the exponent. Discovering this faster algorithm

will be beyond the reach of most students, so should not be required.

A sample ADT for character strings might look as follows (with the normal

interpretation of the function names assumed).

Chap. 1 Data Structures and Algorithms

Some

In C++, this is 1 for s1int strcmp(String s1, String s2)

One’s compliment stores the binary representation of positive numbers, and

stores the binary representation of a negative number with the bits inverted.

Two’s compliment is the same, except that a negative number has its bits

inverted and then one is added (for reasons of efficiency in hardware implementation).

This representation is the physical implementation of an ADT defined by the normal arithmetic operations, declarations, and other support

given by the programming language for integers.

An ADT for two-dimensional arrays might look as follows. Matrix add(Matrix M1, Matrix M2); Matrix multiply(Matrix M1, Matrix M2); Matrix transpose(Matrix M1);

void setvalue(Matrix M1, int row, int col, int val); int getvalue(Matrix M1, int row, int col); List getrow(Matrix M1, int row);

One implementation for the sparse matrix is described in Section Another implementation

is a hash table whose search key is a concatenation of the matrix coordinates.

Every problem certainly does not have an algorithm. As discussed in Chapter 15,

there are a number of reasons why this might be the case. Some problems don’t

have a sufficiently clear definition. Some problems, such as the halting problem,

are non-computable. For some problems, such as one typically studied by artificial

intelligence researchers, we simply don’t know a solution.

We must assume that by “algorithm” we mean something composed of steps are

of a nature that they can be performed by a computer. If so, than any algorithm

can be expressed in C++. In particular, if an algorithm can be expressed in any

other computer programming language, then it can be expressed in C++, since all

(sufficiently general) computer programming languages compute the same set of functions.

The primitive operations are (1) adding new words to the dictionary and (2) searching

the dictionary for a given word. Typically, dictionary access involves some sort

of pre-processing of the word to arrive at the “root” of the word.

A twenty page document (single spaced) is likely to contain about 20,000 words. A

user may be willing to wait a few seconds between individual “hits” of mis-spelled

words, or perhaps up to a minute for the whole document to be processed. This

means that a check for an individual word can take about 10-20 ms. Users will

typically insert individual words into the dictionary interactively, so this process can

take a couple of seconds. Thus, search must be much more efficient than insertion.

The user should be able to find a city based on a variety of attributes (name, location,

perhaps characteristics such as population size). The user should also be able to insert

and delete cities. These are the fundamental operations of any database system:

search, insertion and deletion.

A reasonable database has a time constraint that will satisfy the patience of a typical

user. For an insert, delete, or exact match query, a few seconds is satisfactory. If the

database is meant to support range queries and mass deletions, the entire operation

may be allowed to take longer, perhaps on the order of a minute. However, the time

spent to process individual cities within the range must be appropriately reduced. In

practice, the data representation will need to be such that it accommodates efficient

processing to meet these time constraints. In particular, it may be necessary to support

operations that process range queries efficiently by processing all cities in the

range as a batch, rather than as a series of operations on individual cities.

Students at this level are likely already familiar with binary search. Thus, they

should typically respond with sequential search and binary search. Binary search

should be described as better since it typically needs to make fewer comparisons

(and thus is likely to be much faster).

The answer to this question is discussed in Chapter 8. Typical measures of cost

will be number of comparisons and number of swaps. Tests should include running

timings on sorted, reverse sorted, and random lists of various sizes.

Chap. 1 Data Structures and Algorithms

The first part is easy with the hint, but the second part is rather difficult to do without a stack.

a) bool checkstring(string S) { int count = 0;

for (int i=0; iif (S[i] == ’(’) count++;

if (S[i] == ’)’) {

if (count == 0) return FALSE; count--;

} }

if (count == 0) return TRUE; else return FALSE;

}

b) int checkstring(String Str) { Stack S; int count = 0;

for (int i=0; iif (S[i] == ’(’) (i);

if (S[i] == ’)’) { if ()) return i; ();

} }

if ()) return -1; else return ();

}

Answers to this question are discussed in Section .

This is somewhat different from writing sorting algorithms for a computer, since

person’s “working space” is typically limited, as is their ability to physically manipulate

the pieces of paper. Nonetheless, many of the common sorting algorithms have

their analogs to solutions for this problem. Most typical answers will be insertion

sort, variations on mergesort, and variations on binsort.

Answers to this question are discussed in Chapter 8.

2

Mathematical Preliminaries

(a) Not reflexive if the set has any members. One could argue it is symmetric,

antisymmetric, and transitive, since no element violate any of the rules. (b)

Not reflexive (for any female). Not symmetric (consider a brother and

sister). Not antisymmetric (consider two brothers). Transitive (for any 3 brothers). (c)

Not reflexive. Not symmetric, and is antisymmetric. Not

transitive

(only goes one level). (d)

Not reflexive (for nearly all numbers). Symmetric since a + b = b + a,

so not antisymmetric. Transitive, but vacuously so (there can be no

distinct a, b,and c where aRb and bRc). (e)

Reflexive. Symmetric, so not antisymmetric. Transitive (but sort of vacuous).

(f)

Reflexive – check all the cases. Since it is only true when x = y,it

is technically symmetric and antisymmetric, but rather vacuous. Likewise,

it is technically transitive, but vacuous.

In general, prove that something is an equivalence relation by proving that it

is reflexive, symmetric, and transitive. (a)

This is an equivalence that effectively splits the integers into odd and

even sets. It is reflexive (x + x

is even for any integer x), symmetric

(since x + y = y

+ x) and transitive (since you are always adding two odd or even numbers for any satisfactory a, b,and c). (b)

This is not an equivalence. To begin with, it is not reflexive for any integer. (c)

This is an equivalence that divides the non-zero rational numbers into

positive and negative. It is reflexive since x ˙ x>

0. It is symmetric since

xy˙

= yx˙. It is transitive since any two members of the given class

satisfy the relationship.

5

Chap. 2 Mathematical Preliminaries

(d)

This is not an equivalance relation since it is not symmetric. For example, a =1and b =2. (e)

This is an eqivalance relation that divides the rationals based on their

fractional values. It is reflexive since for all a, =0. It is symmetric since if =x then

=.x. It is transitive since any two rationals

with the same fractional value will yeild an integer. (f)

This is not an equivalance relation since it is not transitive. For example, 4.

2=2and 2. 0=2,but 4. 0=4.

A relation is a partial ordering if it is antisymmetric and transitive. (a)

Not a partial ordering because it is not transitive. (b)

Is a partial ordering bacause it is antisymmetric (if a

is an ancestor of b, then b

cannot be an ancestor of a) and transitive (since the ancestor of an ancestor is an ancestor). (c)

Is a partial ordering bacause it is antisymmetric (if a is older than b, then b

cannot be older than a) and transitive (since if a is older than b and b

is older than c, a is older than c). (d)

Not a partial ordering, since it is not antisymmetric for any pair of sisters.

(e)

Not a partial ordering because it is not antisymmetric. (f)

This is a partial ordering. It is antisymmetric (no violations exist) and

transitive (no violations exist).

A total ordering can be viewed as a permuation of the elements. Since there

are n!permuations of n

elements, there must be n!total orderings.

This proposed ADT is inspired by the list ADT of Chapter 4. void clear(); void insert(int); void remove(int); void sizeof();

bool isEmpty(); bool isInSet(int);

This proposed ADT is inspired by the list ADT of Chapter 4. Note that while

it is similiar to the operations proposed for Question , the behaviour is

somewhat different. void clear(); void insert(int); void remove(int); void sizeof();

7

bool isEmpty();

long ifact(int n) {

The iterative version requires careful examination to understand what

it does, or to have confidence that it works as claimed. (b)

Fibr is so much slower than Fibi because Fibr re-computes the bulk of the series twice to get the two values to add. What is much

worse, the recursive calls to compute the subexpressions also re-compute

the bulk of the series, and do so recursively. The result is an exponential

explosion. In contrast, Fibicomputes each value in the series exactly once, and so its running time is proportional to n.

void GenTOH(int n, POLE goal, POLE t1, POLE t2, POLE* curr) {

if (curr[n] == goal) Put others on t1. GenTOH(n-1, t1, goal, t2, curr); move(t2, goal);

GenTOH(n-1, goal, t1, t2, curr); In theory, this series approaches, but never reaches,

0, so it will go on forever. In practice, the value should become computationally

indistinguishable from zero, and terminate. However, this is terrible

programming practice.

Chap. 2 Mathematical Preliminaries

void allpermute(int array[], int n, int currpos) { if (currpos == (n-1)} { printout(array); return;

}

for (int i=currpos; iallpermute(array, n, currpos+1);

swap(array, currpos, i); The idea is the print out the elements at the indicated bit positions within the set. If we do this for values

in the range 0 to 2n .

1, we will get the entire powerset. void powerset(int n) {

for (int i=0; iif (bitposition(n, j) == 1) cout << j << \" \"; cout << endl; }

Proof: Assume that there is a largest prime number. Call it Pn,the nth

largest prime number, and label all of the primes in order P1 =2, P2 =3,

and so on. Now, consider the number C formed by multiplying all of the n

prime numbers together. The value C +1is not divisible by any of the n prime numbers. C

+1is a prime number larger than Pn, a contradiction. Thus, we conclude that there is no largest prime number. .

Note: This problem is harder than most sophomore level students can handle. √

Proof: The proof is by contradiction. Assume that 2is rational. By definition,

there exist integers p and q such that

√

p

2=,

q

where p and q

have no common factors (that is, the fraction p/q is in lowest

terms). By squaring both sides and doing some simple algebraic manipulation, we get

2

p

2=

2

q

22

2q = p

Since p2 must be even, p must be even. Thus,

9

22

2q =4(p)

2

22

q =2(p)

2

This implies that q2 is also even. Thus, p

and q

are both even, which contra

√

dicts the requirement that p and q

have no common factors. Thus, 2must be irrational. .

The leftmost summation sums the integers from 1 to n. The second summation

merely reverses this order, summing the numbers from n . 1+1=n

down to n . n

+1=1. The third summation has a variable substitution of i, with a corresponding substitution in the summation bounds. Thus,

it is also the summation of n . 0=n to n . (n . 1)=1. Proof:

(a) Base case.

For n

=1, 12 = [2(1)3 +3(1)2 +1]/6=1. Thus, the formula is correct for the base case. (b) Induction Hypothesis.

2(n .

1)3 +3(n . 1)2 +(n . 1)

i2 = .

6

i=1

(c) Induction Step.

i2 i2 +n 2

=

i=1 i=1

2(n .

1)3 +3(n .

1)2 +(n . 1)

2

= +n

6 2n3 . 6n2 +6n . 2+3n2 . 6n +3+n

. 1 2

= +n

6

2n3 +3n2 +n

= .

6

Thus, the theorem is proved by mathematical induction. .

Proof:

(a) Base case. For n =1, 1/2=1.

1/2=1/2. Thus, the formula is correct for the base case. (b) Induction Hypothesis. 11

=1. .

2

i=1

Chap. 2 Mathematical Preliminaries

(c) Induction Step.

1 11

=+

i in

222

i=1 i=1

11

=1. +

n

221

=1. .

n

2

Thus, the theorem is proved by mathematical induction. .

Proof:

(a) Base case. For n =0, 20 =21 .

1=1. Thus, the formula is correct for the base case.

(b) Induction Hypothesis.

2i =2n . 1. i=0

(c) Induction Step.

2i

=2i +2n

i=0 i=0 n

=2n .

1+2n+1 . 1

=2.

Thus, the theorem is proved by mathematical induction. .

The closed form solution is 3n+, which I deduced by noting that

3F (n). 2

n+1 . 3

F (n)=2F

(n)=3. Now, to verify that this is correct, use mathematical induction as follows. For the base case, F (1)=3= .

2

The induction hypothesis is that =(3n . 3)/2.

i=1

So,

3i =3i +3n i=1 i=1 3n .

3

n

= +3

2

n+1 . 3

3

= .

2

Thus, the theorem is proved by mathematical induction.

11

n

Theorem (2i)=n2 +n. i=1

(a) Proof: We know from Example that the sum of the first n odd

numbers is ith even number is simply one greater than the ith odd number. Since we are adding nsuch numbers, the sum must be n

greater, or n2 +n. .

(b) Proof: Base case: n=1yields 2=12 +1, which is true. Induction Hypothesis:

2i=(n. 1)2 +(n. 1).

i=1

Induction Step: The sum of the first neven numbers is simply the sum

of the first n.

1even numbers plus the nth even number.

2i

=( 2i)+2n

i=1 i=1

=(n. 1)2 +(n. 1)+2n

=(n 2 . 2n+1)+(n. 1)+2n

= n 2 . n+2n

= n 2 +n.

n

Thus, by mathematical induction, 2i=n2 +n. .

i=1

Proof: 52

Base case. For n =1,Fib(1) = 1 < n=2,Fib(2) = 1 <(5).

3

Thus, the formula is correct for the base case.

Induction Hypothesis. For all positive integers i5 i

Fib(i)<().

3

Induction Step. Fib(n)=Fib(n. 1)+Fib(n.

2)and, by the Induction Hypothesis, Fib(n. 1)<(5) and Fib(n. 2)<(5)

33

55

Fib(n) < () +()

3355 5

< () +()

333

Chap. 2 Mathematical Preliminaries

85

= ()

3355

< ()2()

33

n

5

= .

3

Thus, the theorem is proved by mathematical induction. .

Proof: 12(1+1)2

3 =

(a) Base case. For n

=1, 1=1. Thus, the formula is correct 4

for the base case.

(b) Induction Hypothesis.

22

(n . 1)n

i3 = .

4

i=0

(c) Induction Step. n

2

(n . 1)n2 i3 3

=+n

4

i=0 2

n4 .

2n3 +n3

= +n

4

n4 +2n3 +n2

=

4

n2(n2 +2n +2)

=

4

2

n2(n +1)

=

4

Thus, the theorem is proved by mathematical induction. .

(a) Proof: By contradiction. Assume that the theorem is false. Then, each

pigeonhole contains at most 1 pigeon. Since there are n holes, there is

room for only n

pigeons. This contradicts the fact that a total of n +1

pigeons are within the n

holes. Thus, the theorem must be correct. . (b) Proof: i. Base case.

For one pigeon hole and two pigeons, there must be two pigeons in the hole. ii. Induction Hypothesis. For n

pigeons in n .

1holes, some hole

must contain at least two pigeons.

13

iii. Induction Step. Consider the case where n +1pigeons are in n

holes. Eliminate one hole at random. If it contains one pigeon, eliminate it as well, and by the induction hypothesis some other hole must contain at least two pigeons. If it contains no pigeons,

then again by the induction hypothesis some other hole must contain

at least two pigeons (with an extra pigeon yet to be placed). If

it contains more than one pigeon, then it fits the requirements of

the theorem directly. .

(a)

When we add the nth line, we create n new regions. But, we start

with one region even when there are no lines. Thus, the recurrence is F (n)=F (n . 1)+n +1.

(b) This is equivalent to the summation F (n)=1+ i=1 ni.

(c) This is close to a summation we already know (equation .

Base case: T(n .

1)=1=1(1+1)/2.

Induction hypothesis: T(n . 1)=(n .

1)(n)/2.

Induction step: T(n)= T(n . 1)+n

=(n .

1)(n)/2+n

= n(n +1)/2.

Thus, the theorem is proved by mathematical induction.

If we expand the recurrence, we get T(n)=2T(n .

1)+1=2(2T(n .

2)+1)+1)=4T(n . 2+2+1.

Expanding again yields

T(n)=8T(n .

3)+4+2+1.

From this, we can deduce a pattern and hypothesize that the recurrence is equivalent to

n

T(n)= .12i =2n . 1.

i=0

To prove this formula is in fact the proper closed form solution, we use mathematical induction. Base case: T(1)=21 . 1=1.

14

Chap. 2 Mathematical Preliminaries

Induction hypothesis: T(n . 1)= . 1.

Induction step:

T(n)=2T(n . 1)+1 = 2 . 1) + 1 =2n

. 1.

Thus, as proved by mathematical induction, this formula is indeed the correct

closed form solution for the recurrence.

(a)

The probability is for each choice. (b)

The average number of “1” bits is n/2, since each position has

probability of being “1.” (c)

The leftmost “1” will be the leftmost bit (call it position 0) with probability

; in position 1 with probability , and so on. The number

of positions we must examine is 1 in the case where the leftmost “1” is

in position 0; 2 when it is in position 1, and so on. Thus, the expected

cost is the value of the summation n

i

.

2i

i=1

The closed form for this summation is 2 . n+2, or just less than two.

2n

Thus, we expect to visit on average just less than two positions. (Students

at this point will probably not be able to solve this summation, and it is not given in the book.)

There are at least two ways to approach this problem. One is to estimate the

volume directly. The second is to generate volume as a function of weight.

This is especially easy if using the metric system, assuming that the human

body is roughly the density of water. So a 50 Kilo person has a volume

slightly less than 50 liters; a 160 pound person has a volume

slightly less than 20 gallons.

(a) Image representations vary considerably, so the answer will vary as a

result. One example answer is: Consider VGA standard size, full-color

(24 bit) images, which is 3 × 0 ×

480, or just less than 1 Mbyte per

image. The full database requires some 30-35 CDs. (b)

Since we needed 30-35 CDs before, compressing by a factor of 10 is

not sufficient to get the database onto one CD.

[Note that if the student picked a smaller format, such as estimating the

size of a “typical” gif image, the result might well fit onto a single CD.]

(I saw this problem in John Bentley’s Programming Pearls.) Approach 1:

The model is Depth X Width X Flow where Depth and Width are in miles

and Flow is in miles/day. The Mississippi river at its mouth is about 1/4 mile

wide and 100 feet (1/50 mile) deep, with a flow of around 15 miles/hour =

360 miles/day. Thus, the flow is about 2 cubic miles/day. Approach 2: What goes out must equal what goes in. The model is Area X

Rainfall where Area is in square miles and Rainfall is in (linear) miles/day.

The Mississipi watershed is about 1000 X 1000 miles, and the average rainfal

is about 40 inches/year ≈

.1 inches/day ≈

.000002 miles/day (2 X .

Thus, the flow is about 2 cubic miles/day.

Note that the student should NOT be providing answers that look like they

were done using a calculator. This is supposed to be an exercise in estimation!

The amount of the mortgage is irrelevant, since this is a question about rates.

However, to give some numbers to help you visualize the problem, pick a

$100,000 mortgage. The up-front charge would be $1,000, and the savings

would be 1/4% each payment over the life of the mortgage. The monthly

charge will be on the remaining principle, being the highest

at first and gradually

reducing over time. But, that has little effect for the first few years.

At the grossest approximation, you paid 1% to start and will save 1/4% each

year, requiring 4 years. To be more precise, 8% of $100,000 is $8,000, while

7 3/4% is $7,750 (for the first year), with a little less interest paid (and therefore

saved) in following years. This will require a payback period of slightly

over 4 years to save $1000. If the money had been invested, then in 5 years

the investment would be worth about $1300 (at 5would be close to 5 1/2 years.

Disk drive seek time is somewhere around 10 milliseconds or a little less

in 2000. RAM memory requires around 50 nanoseconds – much less than

a microsecond. Given that there are about 30 million seconds in a year, a

machine capable of executing at 100 MIPS would execute about 3 billion billion (3 .

1018) instructions in a year.

Typical books have around 500 pages/inch of thickness, so one million pages

requires 2000 inches or 150-200 feet of bookshelf. This would be in excess of

50 typical shelves, or 10-20 bookshelves. It is within the realm of possibility

that an individual home has this many books, but it is rather

unusual.

A typical page has around 400 words (best way to derive this is to estimate

the number of words/line and lines/page), and the book has around 500 pages,

so the total is around 200,000 words.

16

Chap. 2 Mathematical Preliminaries

An hour has 3600 seconds, so one million seconds is a bit less than 300 hours.

A good estimater will notice that 3600 is about 10% greater than 3333, so the

actual number of hours is about 10% less than 300, or close to 270. (The real

value is just under 278). Of course, this is just over 11 days.

Well over 100,000, depending on what you wish to classify as a city or town.

The real question is what technique the student uses.

(a) The time required is 1 minute for the first mile, then 60/59 minutes

for the second mile, and so on until the last mile requires 60/1=60

minutes. The result is the following summation. 60 60

60/i =60 1/i =60H60. i=1 i=1

(b)

This is actually quite easy. The man will never reach his destination,

since his speed approaches zero as he approaches the end of the journey.

3

Algorithm Analysis

Note that nis a positive integer. 5nlog nis most efficient for n=1. 2n

is most efficient when 2 ≤ n≤ 4.

10nis most efficient for all n>5. 20nand 2n are never more

efficient than the other choices.

Both log3 nand log2 nwill have value 0 when n=1.

Otherwise, 2 is the most efficient expression for all n>1. 2/32 3n

2 log3n log2 nn20n 4nn!. (a)

n+6 inputs (an additive amount, independent of n). (b)

8ninputs (a multiplicative factor). (c)

ninputs. 100n. 10n.

√

About (actually, 3 100n). n+6.

(a)

These questions are quite hard. If f(n)=2n = x, then f(2n)=22n = 2

(2n)2 = x.

(b)

The answer is 2(nlog2 3). Extending from part (a), we need some way to

make the growth rate even higher. In particular, we seek some way to log2 3 =

make the exponent go up by a factor of 3. Note that, if f(n)= n)=2log2 3log2 3 =3x

y, then f(2nn. So, we combine this observation with part (a) to get the desired answer.

First, we need to find constants cand no such that 1 ≤ c×

1 for n>n0.

This is true for any positive value c<1 and any positive value of n0 (since

nplays no role in the equation).

Next, we need to find constants cand n0 such that 1 ≤ c×

nfor n>n0.

This is true for, say, c=1 and n0 =1. 17

18

Chap. 3 Algorithm Analysis

Other values for n0 and care possible than what is given here. (a)

The upper bound is O(n) for n0 >0 and c= c1. The lower bound is

Ω(n) for n0 >0 and c= c1. (b)

The upper bound is O(n3) for n0 >c3 and c = c2 +1. The lower

bound is Ω(n3) for n0 >c3 and c= c2. (c)

The upper bound is O(nlog n) for n0 >c5 and c= c4 +1. The lower bound is Ω(nlog n) for n0 >c5 and c= c4.

(d)

The upper bound is O(2n) for n0 >c7100 and c = c6 +

lower bound is Ω(2n) for n0 >c7100 and c = c6. (100 is used for

convenience to insure that 2n >n6)

(a) f(n)=Θ(g(n)) since log n2 = 2 log n. (b)

f(n) is in Ω(g(n)) since nc grows faster than log nc for any c. (c)

f(n) is in Ω(g(n)). Dividing both sides by log n, we see that log n

grows faster than 1.

(d)

f(n) is in Ω(g(n)). If we take both f(n) and g(n) as exponents for 2, 2

we get 2n

on one side and 2log2 n

=(2log n)2 = n2 on the other, and ngrows slower than 2n .

(e)

f(n) is in Ω(g(n)). Dividing both sides by log nand throwing away

the low order terms, we see that ngrows faster than 1. (f)

f(n)=Θ(g(n)) since log 10 and 10 are both constants. 2

(g)

f(n) is in Ω(g(n)) since 2n grows faster than 10n. (h)

f(n) is in O(g(n)). 3n

=, and if we divide both sides by 2n ,

we see that

grows faster than 1.

(a) This fragment is Θ(1). (b)

This fragment is Θ(n) since the outer loop is constant number of times. (c)

executed a This fragment is Θ(n2) since the loop is executed n2 times. (d)

This fragment is Θ(n2 log n) since the outer forloop costs nlog nfor

each execution, and is executed ntimes. The inner loop is dominated

by the call to sort. (e)

For each execution of the outer loop, the inner loop is generated a “random”

number of times. However, since the values in the array are a permutation of the values from 0 to n. 1, we know that the inner loop

will be run itimes for each value of ifrom 1 to n. Thus, the total cost n

is

i=1 i=Θ(n2).

(f)

One branch of the if statement requires Θ(n) time, while the other

requires constant time. By the rule for ifstatements, the bound is the

greater cost, yielding Θ(n) time.

19

(a) n n

n!= n× ×···× ×(.1) ×···×2 ×1

2 2

n n n

≥ × ×···×

×1 ×···×1 ×1

2 2 2

n

)n/2

=(

2

Therefore

n

n 2 1

lg n! ≥lg ≥ (nlg .

22

(b) This part is easy, since clearly 1 ·2 ·3 ···nso n! yielding log n! √

Clearly this recurrence is in O(log nn) since the recurrance can only be √

expanded log ntimes with each time being nor less. However, since this

series drops so quickly, it might be reasonable to guess that the closed form

√

solution is O(n). We can prove this to be correct quite easily with an

√

induction proof. We need to show that T(n) ≤ cnfor a suitable constant

c. Pick c=4.

Base case: T(1) ≤4. √

Induction Hypothesis: T(n) Induction Step:

√

T(2n)= T(n)+ 2n

√√

≤4n.

≤ 4 n+2n

√√ √√

=222n=(2 2+1) 2n

√ ≤ 42n.

Therefore, by mathematical induction we have proven that the closed form

√

solution for T(n) is in O(n).

The best lower bound I know is Ω(log n), since a value cannot be reduced

more quickly than by repeated division by 2. There is no known upper bound,

since it is unknown if this algorithm always terminates.

Yes. Each deterministic algorithm, on a given input, has a specific running

time. Its upper and lower bound are the same – exactly this time. Note that

the question asks for the EXISTENCE of such a thing, not our ability to determine it.

Chap. 3 Algorithm Analysis

Yes. When we specify an upper or lower bound, that merely states our knowledge

of the situation. If they do not meet, that merely means that we don’t

KNOW more about the problem. When we understand the problem completely,

the bounds will meet. But, that does NOT mean that we can actually

determine the optimal algorithm, or the true lower bound, for every problem.

What we do is begin at the left side, and

start searching for K. The secret is to jump twice as far to the right on each

search. Thus, we would initially search array positions 0, 1,

2, 4, 8, 16, 32

and so on. Once we have found a value that is larger than or equal to what

we are searching for, we have bounded the subrange of the array from our

last two searches. The length of this subarray is at most n units wide, and

we have done this initial bracketing in at most log n +1 searches. A normal

binary search of the subarray will find the position n in an additional log n

searches at most, for a total cost in O(log n) searches.

Here is a description for a simple Θ(n2) algorithm. boolean Corner(int n, int m, Piece P1, Piece** array) { for (int i=0; ifor (int j=0; jif (compare(P1, array[i][j], LEFT)) return FALSE; if (compare(P1,array[i][j],BOTTOM)) return FALSE;

}

return TRUE; }

void jigsaw(int n, int m, Piece** array) {

\\\\ First, find the lower left piece by checking each \\\\ piece against the others to reject pieces until one \\\\ is found that has no bottom or left connection. for (i=0; ifor (j=0; jif (Corner(n, m, array[i][j], array)) { for (i=0; ifor (j=0; jif (j==0) { 3 Algorithm Analysis

SWAP(array[i][j], array[tempr][tempc]);

} } }

2

Finding the corner takes O(nm2) time, which is the square of the number of

2

pieces. Filling in the rest of the pieces also takes O(nm2) time, the number

2

of pieces squared. Thus, the entire algorithm takes O(nm2) time.

If an algorithm is Θ(f(n)) in the average case, then by definition it must

be Ω(f(n)) in the average case. Since the average case cost for an instance

of the problem requires at least cf(n) time for some constant c, at least one

instance requires at least as much as the average cost (this is an example of

applying the Pigeonhole Principle). Thus, at least one instance costs at least

cf(n), and so this means at least one instance (the worst case) is Ω(f(n)).

If an algorithm is Θ(f(n)) in the average case, then by definition it must

be O(f(n)) in the average case. Therefore, the average case cost for an

instance of the problem requires at most cf(n) time for some constant

the pigeonhole principle, some instance (the best case) must therefore cost at

most cf(n) time. Therefore, the best case must be O(f(n)).

4

Lists, Stacks, and Queues

Call the list in question L1. (); (); (); val = ();

(a) | 10, 20, 15

. (b) 39 | 12, 10, 20, 15 .

list L1(20); (2); (23); (15); (5); (9);

(); ();

4 Lists, Stacks, and Queues

link* temp1 = head->next; link* temp2 = temp1->next; while (temp2 != NULL) {

link* temp3 = temp2->next; temp2->next = temp1; temp1 = temp2; temp2 = temp3;

}

head->next = temp1;

}

(a) The following members are modified. template

void LList::LList(const int sz) { head = tail = curr = new link;

The space required by the array-based list implementation is fixed. It must be at least n spaces to hold n

elements, for a lower bound of Ω(n).However, the

actual number of elements in the array (n) can be arbitrarily small compared

to the size of the list array.

D

is number of elements; E is in bytes; P is in bytes; and n is number of

elements. Setting number of elements as e and number of bytes as b,the equation has form e > eb/(b + b)= eb/b = e

for a comparison of e>e which is correct.

(a) Since E =8, P =4,and D

=20, the break-even point occurs when 1

n

= (20)(8)/(4+8) = 13.

3

So, the linked list is more efficient when 13 or fewer elements are stored.

(b) Since E =2, P

=4,and D

=30, the break-even point occurs when n

= (30)(2)/(2+4) = 10.

So, the linked list is more efficient when less than 10 elements are stored.

(c) Since E =1, P =4,and D

=30, the break-even point occurs when n

= (30)(1)/(1+4) = 6.

So, the linked list is more efficient when less than 6 elements are stored.

(d) Since E =32, P =4,and D

=40, the break-even point occurs when n

= (40)(32)/(32+4) = .

So, the linked list is more efficient when 35 or fewer elements are stored.

Chap. 4 Lists, Stacks, and Queues

I assume an intrequires 4 bytes, a doublerequires 8 bytes, and a pointer

requires 4 bytes. (a) Since E =4and P

=4, the break-even point occurs when 1

n =4D/8=D.

2

Thus, the linked list is more space efficient when the array

would be

less than half full.

(b) Since E =8and P

=4, the break-even point occurs when 2

n

=8D/12=D.

3

Thus, the linked list is more space efficient when the array would be

less than two thirds full.

We need only modify push and pop, as follows. bool push(const Elem& item) {

Stack2() { delete [] listArray; } // Destructor

void clear(int st) { if (st == 1) top1 = 0; else top2 = size -1;

bool push(int st, const Elem& item) {

if (top1+1 >= top2) return false; // Stack is full if (st == 1) listarray[top1++] = item; else listarraay[top2--] = item; return true;

}

bool pop(int st, Elem& it) { // Pop top element if ((st == 1) && (top1 == 0)) return false;

if ((st == 2) && (top2 == (size-1))) return false; if (st == 1) it = listArray[--top1]; else it = listArray[++top2]; return true;

}

bool topValue(int st, Elem& it) const { // Return top if ((st == 1) && (top1 == 0)) return false;

if ((st == 2) && (top2 == (size-1))) return false; if (st == 1) it = listArray[top1-1]; else it = listArray[top2+1]; return true;

}

int length(int st) const { if (st == 1) return top1; else return size -top2 -1;

} };

// Array-based queue implementation template

class AQueue: public Queue { private:

int size; // Maximum size of queue

int front; // Index of front element int rear; // Index of rear element

Elem *listArray; // Array holding queue elements bool isEmpty;

public:

AQueue(int sz =DefaultListSize) { // Constructor // Make list array one unit larger for empty slot size = sz+1;

rear = 0; front = 1;