Lcs311 Spring 2008 Homework

lCS311 Spring 2008 Homework

Chs.1,3

1. For a nearly complete k-ary tree of n nodes total, derive:

a)Height, as the actual expression as well as the asymptotic bound

b)Number of leaves

c)Number of internal nodes.

2. Indicate whether B is Θ, O, o, Ω or ω bound for A. Assume that k and c are constants greater than 0. Check each appropriate column in the table below and justify your answer.

A / B / O / o / Ω / ω / Θ
n^(k/3) / (k/3)^n
n^(16 log48) / n^(8log44)
log4(n) / lg(n)
10n3 / 500n3
30n2 / 30*n2+ 30*n + 30

Ch.2

Solve problem 2-3 a. b. Do make sure you understand it, because it will be used in Ch.32.”Naïve algorithm” is any brute-force algorithm that has not been optimized in any way. In this particular case, “naïve” means implementing the original “plain’” polynomial formula.

Write code that implements Horner’s rule. Make it general, so that your code can be reused.

Solve problem 2.3-2. Why would be bother to modify the algorithm to avoid the sentinels?

Trace MergeSort in the style similar to Fig.2.4, but include the splits. Notice that Fig.2.4 shows only Merges, not splits. When you draw the trace showing the splits, it will look like Fig.2.4. but it will go down, not up. At the end, draw the merges. Trace MERGE-SORT(A) for

A = <1 12 3 80 8 11 80 80 >.

Then draw the corresponding tree in style of Fig.2.5. Make conclusions as to the relationship between the two figures.

The web has a detailed handout on MergeSort tracing. Make sure you become very proficient at it, we will be working with many similar recursive formulas.

Ch.4

1.Draw the recursive trees for the recursive functions from the review homework, and calculate the final answer for f(n) by either counting the nodes from the tree, Master theorem, or plain mathematical expansion. Show the method you used.

f(n) = f(n-2) + n/2

f(n) = 2f(n/4) + n

f(n) = f(n/2) + n/2

Ch.10

1.Trace the following pseudocodes and conclude what they return. If necessary, fix them to produce the correct results:

//L is is singly linked list, x is a value, code is in C

Code1(L, x) {

x = first(L)

while (x != NIL || key(x) != x)

x = next(x)

//L is is singly linked list, k is a value, code is in C

Code2(L, k) {

x = first(L)

while (x != NIL & key(x) != k)

x = next(x)

//L is is singly linked list, k is a value, code is in C

Code3(L, k) {

x = first(L)

while (x != NIL & key(x) = k)

x = next(x)

//L is is singly linked list, k is a value, code is in C

Code4(L, k) {

x = first(L)

while (key(x) < k)

x = next(x)

//L is is singly linked list, k is a value, code is in C

Code5(L, k) {

x = first(L)

while (x!= NIL || key(x) < k)

x = next(x)

f. High-level pseudocode from a student project: (ps – the student wrote code that did not run properly. I found the bug in less than 2 minutes by extracting this pseudocode from the code.)

//extracts tokens from a line:

while (not end of file)

read a line

token = extract a token

while (there is next token)

for i = 1, M //assuming we want M tokens on one line

A[i] = token

token = extract next token

Ch.6

1. Trace MAX-HEAPIFY(A, 1) on array A = <1 12 3 80 8 11 80 80 >.

The easiest, quickest way to trace heap codes is to draw the heap as a tree, and then just cross out values and write in new values as nodes get swapped.

(FYI: In my experience, redrawing the tree after a while is necessary, when the crosses make the tree look too messy to read.)

2. Trace MAX-HEAPIFY(A, 2) on array A = <1 12 3 80 8 11 80 80 >.

3. Trace BUILD-MAX-HEAP(A) on array A = <1 12 3 80 8 11 80 80 >.

4. Check the correctness of your answers and discuss the differences and similarities between problems 1, 2 and 3.

5. Rewrite HEAP-INCREASE-KEY to use MAX-HEAPIFY-UP, which heapifies bottom-up. (Notice that MAX-HEAPIFY heapifies top-down.) Write the new version of HEAP-INCREASE-KEY as well as MAX-HEAPIFY-UP.

In other words: rewrite what is already there in HEAP-INCREASE-KEY, but write it so that the heapifiying part is in a separate function.

Ch.7

1. Write out the formulas and the solutions for the running time of QuickSort in case that:

all elements have different values
all elements have the same value
the array is sorted in increasing order
the array is sorted in decreasing order
the array has 2,000,000 elements
the array has one element
the array has 200 elements
the array has 0 elements

2.Write the formula for running time, draw the recursion tree, and solve the running time for Quicksort() in case that each partition splits the array into 2/5 and 3/5. A comparable tree is on p.151.

3.Trace QuickSort in the style similar to Fig.2.4, but include the splits. Notice that Fig.2.4 shows only Merges, not splits. When you draw the trace showing the splits, it will look like Fig.2.4. but it will go down, not up. At the end, draw the merges. Trace QUICK-SORT(A) for A = <1 12 3 80 8 11 80 80 >.

Then draw the corresponding tree in style of Fig.2.5. Make conclusions as to the relationship between the two figures.

Compare this trace and results with MERGE-SORT trace and results that we had for homework for Ch.2.

Make conclusions: how are MERGE-SORT and QUICK-SORT similar and different?

4.Is it possible to convert QuickSort into iterative code? Explain your answer, and provide some ideas as to how to accomplish the conversion if you think it is possible.

Ch. 8

Trace COUNTING-SORT on A = <1 12 3 80 8 11 80 80 >.

Ch. 9

Trace RANDOMIZED-SELECT(A, 1, 10, 6) on array A given below. Assume that RANDOMIZED-PARTITION() always selects the last element as the pivot.

A=< 1 12 3 80 8 11 80 80 11 12 4 5 6 1 33>.

What is the purpose of variable k? Explain why RandomizedSelect introduces variable k, instead of working only with input parameter i.

2. Discuss similarities, differences, and running times of MergeSort, QuickSort, RandomizedQuickSort, RandomizedSelect, and BinarySearch.
Ch. 11

1. Assume that the hash table has 4 slots (i.e. m= 4) and h’(k) = k mod m. Show the hash tables for the following keys, using:

open addressing with linear probing h(k, i) = (h’(k) + i)) mod m
open addressing with quadratic probing, c1 = 1, c2 = 3

h(k, i) = (h’(k) + c1*i + c2*i2) mod m

open addressing with double probing. h(k, i) = (h’ (k) + i * h2(k)) mod m,

h2(k) = 1 + (k mod (m-1)).

chaining, using doubly linked list and h(k) = k mod m.

Key / 6 / 24 / 18 / 12 / 36 / 42 / 10 / 3 / 5
Slot
Key

Ch.12

1. Suppose we have numbers between 1 and 100 in a BST and want to search for number 36, starting from the root. Which of the following sequences could not be the sequence of nodes examined?

a. 6 42 12 36

b. 6 11 42 36

c. 33 33 23 36

d. 33 33 33 36

2. Trace TREE-INSERT(B, z) on the BST given in figure 12.3 (including the node with key 13), where z is node with key 19.Show only the most important steps of the trace.

How would you summarize the “high level pseudocode” of this algorithm?

FYI: This skill is important because it allows you to skip tracing every line of the code, and instead focus on tracing bigger chunks, which is more efficient. For example: “this chunk swaps parent with its smallest child”.

3. Trace TREE-DELETE(B, z) on the BST in figure 12.4a (including the node with key 13), where z is the node with key 12. Show only the most important steps of the trace.

How would you summarize the “high level pseudocode” of this algorithm?

Ch. 13

1. “Draw” (it is OK to just say where the new node will be) the red-and-black tree that results when RB-INSERT is called in the tree given in Fig. 13.1, and discuss if the resulting tree is a red-black tree when the node inserted is colored red, or black (i.e. do everything up and including line 16). Then trace RB-INSERT-FIXUP (i.e. line 17) only for case c.

a. the new node has value 13

b. the new node has value 21.

c. the new node has value 35.

Ch.15, part 1: Assembly Line

1. Using the formulas for the Assembly line problem, point to and describe the overlapping of subproblems.

Is AssemblyLine problem a good candidate for dynamic programming? Justify your answer.

How about QUICK-SORT? Justify your answer.

In your opinion, when is it desirable to use dynamic programming? Justify your answer.

Ch.15, part 2: Matrix Chain

1. Using the dynamic programming approach using bottom-up algorithm, find the optimal position of parenthesis of a matrix-chain product whose sequence of dimensions is {30, 10, 20, 10, 40}. Prove your result by drawing it in the style of Fig. 15.3, and also label the order in which the cells are filled in.

What is the savings achieved using dynamic programming versus using the parenthesis in the order ((M1M2)M3)M4 ?

Is it worth it running the dynamic programming algorithm on this problem?

2. For problem 1, write recursive and memoized algorithms based on the dynamic programming solution. Prove your result by drawing it in the style of Fig. 15.3, and also label the order in which the cells are filled in.

Discuss the differences between solutions in problems 1 and 2.

Warning: this problem is a good candidate for the next exam, where you would be given a recursive formula like this one and asked to write recursive, memorized, and iterative solutions. (We don’t need to know the application of the formula, we are practicing coding a formula.)

Ch. 16

1. Construct a variable length optimal prefix code using the Huffman’s code _from our textbook_. Trace the code by hand and show the priority queue. Notice that the textbook skips showing the queue.

Encode the word and show the resulting encoded message. Start with the array in the order below.

LILIAN

Character / L / I / A / N
Frequency
Fixed length code
Prefix code

How much savings does Huffman code provide compared to a fixed-length code?

What can you conclude regarding the efficiency of a variable-length prefix code?

Ch. 18

1. Write all legal B-trees of minimum degree 2 that have keys {1 4 5 6 10}.

2. Write higher level pseudocode for B-TREE-INSERT-NONFUL.

FYI: Notice how B-TREE-SPLIT-CHILD can be traced more efficiently when we use only pseudocode, and notice the usefulness of the English description in the paragraph below the code.

3. Show the results of inserting the keys: D1 D2 D3 D4 L Q W M A N E R P B into an empty B-tree with minimum degree 2. Only draw the configuration of the tree just before some node must split, and also draw the final configuration.

4. Show results of deleting C, N, R in order, from the tree in Fig. 18.8f.

t=3, 2 <= num. keys <=5.

Ch. 23

1. For the graph given below, find the minimum spanning tree using Prim’s algorithm. Trace the code from our textbook by hand, but show only the most important steps, as graphs, and show the priority queue. Notice that the textbook skips showing the queue. Use alphabetical ordering. The source vertex is a.

Hint: what do you have to do with the edge from c to c?

Ch. 24

1. Find the feasible solution to the following system of linear inequalities, utilizing Bellman-Ford algorithm. Use alphabetical ordering.

x1 – x3<= -1

x3– x2 <= 5

x3 – x4 <= -2

x4 – x1 <= -4

x2 – x1 <= 1

x1 – x4 <= -5

Ch. 25

Find the shortest paths for the graph given by the adjacency matrix below, using SLOW-ALL-PAIRS-SHORTEST-PATHS, FASTER-ALL-PAIRS-SHORTEST-PATHS, and Floyd Warshall algorithms.

Show each L(k). and D(k). matrix, as well as each parent matrix π(k), for each algorithm (so there will be a π(k), matrix for each L(k). matrix, and a π(k), matrix for each D(k). matrix).

What is the final solution?

How will you check if your results are correct? Do so.

abcd

a∞53∞

b∞∞2∞

c∞∞∞4

d∞1∞∞

Hint: what kind of matrix is required as input to the algorithm?

Ch.26

Show execution of Edmonds-Karp algorithm on the graph given in Fig. 26.5. Show the most important steps of BFS.

Ch.29

1. Solve the following linear program using SIMPLEX algorithm:

Minimize z = a - b

Subject to:1. a – 2b  0

2. a + 3b ≥ 4

3. 5a + b = 2

4. a,b  0

How will you check if your solution is correct? Do so.

Ch. 32

1. Trace searching for pattern P = 77 using Rabin-Karp algorithm on the text T = 05337752266533377755. Use q=11 and d=10. How many spurious hits does the algorithm encounter?

2. Construct the string-matching automaton and draw its state transition diagram for pattern P = abaaba. Illustrate its operation on the text string T = aaabaababaabaaba.

To do this question, the best method that I found so far is to have the pattern and the string written on two pieces of paper, and then slide the papers over each other.