15-110 PS7 Sample Solutions - Spring 2018

1. 

(a)            42
            /      \
          39        79
         /         /  \
       10        65    91
         \            /
          23        88

(b) You can have a root with each of the 5 three-node trees to its left: 5
    You can have a root with each of the 5 three-node trees to its right: 5
    You can have a root with two nodes to its left (2 ways to do this) and 
    one node to its right: 2
    You can have a root with two nodes to its right (2 ways to do this) and
    one node to its left: 2
    Total: 14 

2.

(a) h = [88, 60, 51, 18, 50, 28, 8]

(b) Insert it to the left of 18 (first available slot in the next level)
    and swap it upward until there is a node above it that is greater.
               88
            /      \
          65        51
         /  \      /  \
       60    50  28    8
      /
     18

(c) Replace 88 with 8 (move last node in last level to root) and then
    swap it down with its greater child until it has children below it
    that are less.
                60
             /      \
           50        51
          /  \      / 
         18   8   28

(d) Since the heap is balanced, the heap has 10 full levels (2**10-1 = 1023)
    and one node on the last level. The insert will happen on the last
    level with 10 levels above it, so there are at most 10 swaps.

3.

(a) graph = [ [  0,  9,  f, 12, 16, 29 ],
              [  9,  0, 17, 24,  f,  f ],
              [  f, 17,  0, 10,  f,  f ],
              [ 12, 24, 10,  0,  8,  f ],
              [ 16,  f,  f,  8,  0, 26 ]
              [ 29,  f,  f,  f, 26,  0 ] ]

(b) Charleston to Beckley       8
    Parkersburg to Morgantown   9
    Huntington to Charleston   10
    Charleston to Morgantown   12
    Beckley to Martinsburg     26
    Total: 65

4. 

(a) 128 + 64 + 16 + 4 + 2 + 1 = 215

(b) The leftmost bit is 1 so it's negative.
    Flip the bits and add 1 to get the positive version:
    11010111 --flip--> 00101000 --+1--> 00101001 = 32 + 8 + 1 = +41
    So the original bit pattern is -41.

(c) 11010111 = D7

5.

(a) A occurs most frequently since it has the shortest Huffman code (0).

(b) 10000 1111 101 1001 10001 1110 0
    C     O    R   T    I     N    A

(c) This is a lossless technique because you do not lose any
    information when you encode and then decode.

6. 

(a) 

Red:   FF = 11111111 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255
Green: D9 = 11011001 = 128 + 64      + 16 + 8         + 1 = 217
Blue:  0F = 00001111 =                      8 + 4 + 2 + 1 =  15

(b)

The sampling theorem says that we need to sample at twice the highest
frequency of the sound. Since the sound has only one frequency (1760Hz)
after it settles, we would sample at 3520 samples/sec.

2 bytes/sample * 3520 samples/second * 20 seconds * 2 (stereo)
= 281,600 bytes = 275KB (assuming 1KB = 1024 bytes).
Also acceptable: 281.6KB (if you assumed 1KB = 1000 bytes)

7.

(a)  x = 1 + 3 + 4 + 8 + 9 + 0 = 25
     y = 6 + 8 + 5 + 1 + 3     = 23
     z = (3*25 + 23) % 10 = 98 % 10 = 8   Return: 10 - 8 = 2

(b)  B  (the checkdigit should be 2, so something was wrong, but there
         is not way to tell which of the 12 digits was wrong)

8.

(a)  X  Y  Z  F
     0  0  0  1 
     0  0  1  1
     0  1  0  0
     0  1  1  0
     1  0  0  1
     1  0  1  0
     1  1  0  0
     1  1  1  1

(b)  F = -X^-Y^-Z v -X^-Y^Z v X^-Y^-Z v X^Y^Z
("-" is used for "not", "^" for "and", "v" for "or")

(c) if (number < 1) or (number >= 28):