SOME QUESTIONS TO EXERCISE CPSC 413 WITH. I tried to make the questions Goldilock Questions. That is, Not too easy, not too hard, just right 1: Prove (an example is sufficient) that the order in which the matrix multi- plications are performed may dramatically affect the total number of scalar multiplications—despite the fact that, since matrix multiplication is associative, the final matrix stays the same. 2: Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key k in a binary search tree ends up in a leaf. Consider three sets: A, the keys to the left of the search path; B, the keys on the search path; and C, the keys to the right of the search path. Professor Bunyan claims that any three keys a∈A, b∈B and c∈C must satisfy

a≤b≤c. Give a smallest possible counterexample to the professor’s claim.

3: Draw an example of each of the following: 1. A DAG with 8 vertices and 10 edges. 2. An undirected tree with 8 vertices and 10 edges. 3. A tree that is not “an undirected graph without cycles”. 4. A graph without cycles that is not a tree.

Are all four possible? If not, why not

4:

During the summer you get a job as DJ at a small radio station that only plays

teenagers’ music. To make your program more attractive, you run a contest:

you will receive ten phone calls from the public, and afterwards, you will award

a thoughtful prize to the oldest member of your audience. Note the following:

(i) you receive one call at a time, (ii) you do not know when the next call will

occur, (iii) you are not allowed to disclose the age at any moment.

Think of a strategy to solve this situation, that’s it, finding the largest

number without having all the data beforehand.

ASYMPTOTIC NOTATION SUMMARY.

See: https://www2.cs.arizona.edu/classes/cs345/summer14/files/bigO.pdf

for a reasonable list.

Following are the properties of asymptotic notations:-

1. Transitive

• If f(n) = Θ(g(n)) and g(n) = Θ(h(n)), then f(n) = Θ(h(n))

• If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n))

• If f(n) = o(g(n)) and g(n) = o(h(n)), then f(n) = o(h(n))

• If f(n) = Ω(g(n)) and g(n) = Ω(h(n)), then f(n) = Ω(h(n))

• If f(n) = ω(g(n)) and g(n) = ω(h(n)), then f(n) = ω(h(n))

2. Reflexivity

• f(n) = Θ(f(n))

• f(n) = O(f(n))

• f(n) = Ω(f(n))

3. Symmetry

• f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n))

4. Transpose Symmetry

• f(n) = O(g(n)) if and only if g(n) = Ω(f(n))

• f(n) = o(g(n)) if and only if g(n) = ω(f(n))

5. Some other properties of asymptotic notations are as follows:

• If f (n) is O(h(n)) and g(n) is O(h(n)), then f (n) + g(n) is O(h(n)).

• The function loga n is O(logb n) for any positive numbers a and b ≠ 1.

• loga n is O(lg n) for any positive a ≠ 1, where lg n = log2 n.

END SUMMARY 5: For each one of the following statements, write two functions f and g that satisfy the given condition.

a) f(n)=O(g2(n))

b) f(n)=ω(g(n))

c) f(n)=ω(log(g(n)))

d) f(n)=Ω(f(n)g(n))

e) f(n)=Θ(g(n))+Ω(g2(n))

6:

For each of the following pairs of functions f(n) and g(n), either f(n) = O(g(n))

or g(n) = O(f(n)), but not both. Determine which is the case.

1. f(n) = (n − n)/2, g(n) = 6n.

2. f(n) = n + 2 n, g(n) = n.

3. (n) = n + log n, g(n) = n n.

4. f(n) = n + 3n + 4, g(n) = n3.

5. f(n) = n log n, g(n) = n n/2.

6. f(n) = n + log n, g(n) = n.

7. (n) = 2(logn) , g(n) = logn + 1.

8. f(n) = 4n log n + n, g(n) = (n − n)/2

2

2

r

2 h3

r

n

2

a

7:

8: Software packages A and B have processing time exactly TEP = 3n1.5 and TWP = 0.03n1.75, respectively. If you are interested in faster processing of up to n = 108 data items, then which package should be chosen?

9:

a: Show that any integer postage greater than 7 cents can be formed

by using only 3-cent and 5-cent stamps.

b: Show that any integer postage greater than 34 cents can be formed

by using only 5-cent and 9-cent stamps.

c: Show that any integer postage greater than 5 cents can be formed

by using only 2-cent and 7-cent stamps.

d: Show that any integer postage greater than 59 cents can be formed

by using only 7-cent and 11-cent stamps.

e: What is the smallest value of k such that any integer postage greater

than k cents can be formed by using only 4-cent and 9-cent stamps?

Prove your answer is correct.

10:

What, if anything is wrong with the following reasoning? All horses are the

same color. The proof is by induction on the number of horses. The base of

the induction is easy: If there is one horse, then it is trivially the same color

as itself. Now suppose that there are n horses, numbered 1 through n. By the

induction hypothesis, horses 1 through n−1 have the same color (let’s say

black). In particular, horse 2 is black. Also, by the induction hypothesis,

horses 2 through n have the same color. Since horse 2 is black, this means

that horses 2 through n must be black. Therefore, all of the horses have the

same color.

11:

An Eulerian cycle in a connected graph is a cycle in which every edge

appears exactly once. Prove by induction that every graph in which each

vertex has even degree (that is, each vertex has an even number of edges

incident with it) has an Eulerian cycle.

12:

TRUE OR FALSE?

a) n = O(n ).

b) N = O(n ).

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

d) n log n = O(n n).

e) n = O(log n).

f) log n = O( n).

g) n = O(n 1 + n )).

h) n (1 + n) = O(n ).

i) n (1 + n) = O(n log n).

j) 3n + 1n = O(n ).

k) 3n + 1n = O(n + n n + n).

l) log n + n = O(n).

m) n log n = O(n).

n) 1/n = O(log n).

o) log n = O(1/n).

p) log n = O(n−1/2).

q) n + 1n = O(1n log

2 3

noon n

r a

r

r

r

z af

2 pm a

2 pm 2

2 pm a

r r r n

r

r

mm Olrik

r m 4

欢迎咨询51作业君