CSE 326 Selected Practice Problem Solutions2.6 As discussed in class, the answer to the first part is 22N −1and the answer to the secondpart is O(log log D).2.10(a) O(N)(b) O(N2)(c) The answer depends on how many digits past the decimal point are computed. Eachdigit costs O(N).3.22 Pseudocode:Create stackRead in first tokenwhile (token is not "=")if (token is a number)push the token onto the stackelseif (token is "+")pop apop bpush a + bif (token is "-")pop apop bpush a − bif (token is "*")pop apop bpush a ∗ bif (token is "/")pop apop bpush a/bread next token14.1(a) A.(b) G, H, I, L, M, and K.4.8(a) - * * a b + c d e.(b) ( ( a * b ) * ( c + d ) ) - e.(c) a b * c d + * e -.4.27 See Figures 1-4.Figure 1: 4.27 After accessing 34.28 See Figure 5.2Figure 2: 4.27 After accessing 9Figure 3: 4.27 After accessing 16.2 See Figure 6.6.3 The result of three deleteMins, starting with both of the heaps in Exercise 6.2, is inFigure 7.6.30 Clearly the claim is true for k = 1. Suppose it is true for all values i = 1, 2, . . . , k.A Bk+1tree is formed by attaching a Bktree to the root of a Bktree. Thus by induction, itcontains a B0through Bk−1tree, as well as the newly attached Bktree, proving the claim.3Figure 4: 4.27 After accessing 5Figure 5: 4.28Figure 6: 6.24Figure 7:
View Full Document
Unlocking...