Please post your solution to the Apr 14 In-Class Exercise to this thread.

Best,

Chris

<nowiki> a: 000011111 b: 000011110 c: 00001110 d: 1100111 e: 1100110 f: 0000110 g: 111011 h: 111010 i: 110010 j: 001011 k: 001010 l: 000010 m: 11111 n: 11110 o: 11100 p: 11011 q: 11010 r: 11000 s: 00111 t: 00110 u: 00100 v: 00011 w: 00010 x: 00000 y: 10 z: 01 </nowiki>

Tree Part 1

Tree Part 2

• Min trees: (a) -> 1/600, (b) -> 2/600

Total str: (a, b) -> 3/600

• Min trees: (a, b) -> 3/600, (c) -> 3/600

Total str: (a, b, c) -> 6/600

• Min trees: (d) -> 4/600, (e) -> 5/600

Total str: (a, b, c) -> 6/600, (d, e) -> 9/600

• Min trees: (a, b, c) -> 6/600, (f) -> 6/600

Total str: (a, b, c, f) -> 12/600, (d, e) -> 9/600

• Min trees: (g) -> 7/600, (h) -> 8/600

Total str: (d, e) -> 9/600, (a, b, c, f) -> 12/600, (g, h) -> 15/600

• Min trees: (d, e) -> 9/600, (i) -> 9/600,

Total str: (a, b, c, f) -> 12/600, (g, h) - 15/600, (d, e, i) -> 18/600

• Min trees: (j) -> 10/600, (k) -> 11/600

Total str: (a, b, c, f) -> 12/600, (g, h) - 15/600, (d, e, i) -> 18/600, (j, k) -> 21/600

• Min trees: (a, b, c, f) -> 12/600, (l) -> 12/600

Total str: (g, h) - 15/600, (d, e, i) -> 18/600, (j, k) -> 21/600, (a, b, c, f, l) -> 24/600

• Min trees: (m) -> 13/600, (n) -> 14/600

Total str: (g, h) - 15/600, (d, e, i) -> 18/600, (j, k) -> 21/600, (a, b, c, f, l) -> 24/600, (m, n) -> 27/600

• Min trees: (g, h) -> 15/600, (o) -> 15/600

Total str: (d, e, i) -> 18/600, (j, k) -> 21/600, (a, b, c, f, l) -> 24/600, (m, n) -> 27/600, (g, h, o) - 30/600

• Min trees: (p) -> 16/600, (q) -> 17/600

Total str: (d, e, i) -> 18/600, (j, k) -> 21/600, (a, b, c, f, l) -> 24/600, (m, n) -> 27/600, (g, h, o) - 30/600, (p, q) -> 33/600

• Min trees: (d, e, i) -> 18/600, (r) -> 18/600

Total str: (j, k) -> 21/600, (a, b, c, f, l) -> 24/600, (m, n) -> 27/600, (g, h, o) - 30/600, (p, q) -> 33/600, (d, e, i, r) -> 36/600

• Min trees: (s) -> 19/600, (t) -> 20/600

Total str: (j, k) -> 21/600, (a, b, c, f, l) -> 24/600, (m, n) -> 27/600, (g, h, o) - 30/600, (p, q) -> 33/600, (d, e, i, r) -> 36/600, (s, t) -> 39/600

• Min trees: (j, k) -> 21/600, (u) -> 21/600

Total str: (a, b, c, f, l) -> 24/600, (m, n) -> 27/600, (g, h, o) - 30/600, (p, q) -> 33/600, (d, e, i, r) -> 36/600, (s, t) -> 39/600, (j, k, u) -> 42/600

• Min trees: (v) -> 22/600, (w) -> 23/600

Total str: (a, b, c, f, l) -> 24/600, (m, n) -> 27/600, (g, h, o) - 30/600, (p, q) -> 33/600, (d, e, i, r) -> 36/600, (s, t) -> 39/600, (j, k, u) -> 42/600, (v, w) -> 45/600

• Min trees: (a, b, c, f, l) -> 24/600, (x) -> 24/600

Total str: (m, n) -> 27/600, (g, h, o) - 30/600, (p, q) -> 33/600, (d, e, i, r) -> 36/600, (s, t) -> 39/600, (j, k, u) -> 42/600, (v, w) -> 45/600, (a, b, c, f, l, x) -> 48/600

• Min trees: (m, n) -> 27/600, (g, h, o) - 30/600

Total str: (p, q) -> 33/600, (d, e, i, r) -> 36/600, (s, t) -> 39/600, (j, k, u) -> 42/600, (v, w) -> 45/600, (a, b, c, f, l, x) -> 48/600, (m, n, g, h, o) - 57/600

• Min trees: (p, q) -> 33/600, (d, e, i, r) -> 36/600

Total str: (s, t) -> 39/600, (j, k, u) -> 42/600, (v, w) -> 45/600, (a, b, c, f, l, x) -> 48/600, (m, n, g, h, o) - 57/600, (p, q, d, e, i, r) -> 69/600

• Min trees: (s, t) -> 39/600, (j, k, u) -> 42/600

Total str: (v, w) -> 45/600, (a, b, c, f, l, x) -> 48/600, (m, n, g, h, o) - 57/600, (p, q, d, e, i, r) -> 69/600, (s, t, j, k, u) -> 81/600

• Min trees: (v, w) -> 45/600, (a, b, c, f, l, x) -> 48/600

Total str: (m, n, g, h, o) - 57/600, (p, q, d, e, i, r) -> 69/600, (s, t, j, k, u) -> 81/600, (v, w, a, b, c, f, l, x) -> 93/600

• Min trees: (m, n, g, h, o) - 57/600, (p, q, d, e, i, r) -> 69/600

Total str: (s, t, j, k, u) -> 81/600, (v, w, a, b, c, f, l, x) -> 93/600, (m, n, g, h, o, p, q, d, e, i, r) -> 126/600

• Min trees: (s, t, j, k, u) -> 81/600, (v, w, a, b, c, f, l, x) -> 93/600

Total str: (m, n, g, h, o, p, q, d, e, i, r) -> 126/600, (s, t, j, k, u, v, w, a, b, c, f, l, x) -> 174/600

• Min trees: (m, n, g, h, o, p, q, d, e, i, r) -> 126/600, (y) -> 150/600

Total str: (s, t, j, k, u, v, w, a, b, c, f, l, x) -> 174/600, (m, n, g, h, o, p, q, d, e, i, r, y) -> 276/600

• Min trees: (s, t, j, k, u, v, w, a, b, c, f, l, x) -> 174/600, (z) -> 150/600

Total str: (m, n, g, h, o, p, q, d, e, i, r, y) -> 276/600, (s, t, j, k, u, v, w, a, b, c, f, l, x, z) -> 324/600

• Min trees: (m, n, g, h, o, p, q, d, e, i, r, y) -> 276/600, (s, t, j, k, u, v, w, a, b, c, f, l, x, z) -> 324/600

Total str: (m, n, g, h, o, p, q, d, e, i, r, y, s, t, j, k, u, v, w, a, b, c, f, l, x, z) -> 600/600

y z x w v u t s r q p o n m l k j i h g f e d c (b = 2/600) (a = 1/600)<br><br>

y z x w v u t s r q p o n m l k j i h g f e d (c = 3/600) (b a = 3/600)<br><br>

y z x w v u t s r q p o n m l k j i h g f (e = 5/600) (d = 4/600) (c b a = 6/600)<br><br>

y z x w v u t s r q p o n m l k j i h g (f = 6/600) (e d = 9/600) (c b a = 6/600)<br><br>

y z x w v u t s r q p o n m l k j i (h = 8/600) (g = 7/600) (e d = 9/600) (f c b a = 12/600)<br><br>

y z x w v u t s r q p o n m l k j (i = 9/600) (h g = 15/600) (e d = 9/600) (f c b a = 12/600)<br><br>

y z x w v u t s r q p o n m l (k = 11/600) (j = 10/600) (h g = 15/600) (i e d = 18/600) (f c b a = 12/600)<br><br>

y z x w v u t s r q p o n m (l = 12/600) (k j = 21/600) (h g = 15/600) (i e d = 18/600) (f c b a = 12/600)<br><br>

y z x w v u t s r q p o (n = 14/600) (m = 13/600) (k j = 21/600) (h g = 15/600) (i e d = 18/600) (l f c b a = 24/600)<br><br>

y z x w v u t s r q p (o = 15/600) (n m = 27/600) (k j = 21/600) (h g = 15/600) (i e d = 18/600) (l f c b a = 24/600)<br><br>

y z x w v u t s r (q = 17/600) (p = 16/600) (n m = 27/600) (k j = 21/600) (o h g = 30/600) (i e d = 18/600) (l f c b a = 24/600)<br><br>

y z x w v u t s (r = 18/600) (q p = 33/600) (n m = 27/600) (k j = 21/600) (o h g = 30/600) (i e d = 18/600) (l f c b a = 24/600)<br><br>

y z x w v u (t = 20/600) (s = 19/600) (q p = 33/600) (n m = 27/600) (k j = 21/600) (o h g = 30/600) (r i e d = 36/600) (l f c b a = 24/600)<br><br>

y z x w v (u = 21/600) (t s = 29/600) (q p = 33/600) (n m = 27/600) (k j = 21/600) (o h g = 30/600) (r i e d = 36/600) (l f c b a = 24/600)<br><br>

y z x (w = 23/600) (v = 22/600) (t s = 29/600) (q p = 33/600) (n m = 27/600) (u k j = 42/600) (o h g = 30/600) (r i e d = 36/600) (l f c b a = 24/600)<br><br>

y z (x = 24/600) (w v = 55/600) (t s = 29/600) (q p = 33/600) (n m = 27/600) (u k j = 42/600) (o h g = 30/600) (r i e d = 36/600) (l f c b a = 24/600)<br><br>

y z (w v = 55/600) (t s = 29/600) (q p = 33/600) (n m = 27/600) (u k j = 42/600) (o h g = 30/600) (r i e d = 36/600) (x l f c b a = 48/600)<br><br>

y z (w v = 55/600) (q p = 33/600) (t s n m = 56/600) (u k j = 42/600) (o h g = 30/600) (r i e d = 36/600) (x l f c b a = 48/600)<br><br>

y z (w v = 55/600) (t s n m = 56/600) (u k j = 42/600) (q p o h g = 63/600) (r i e d = 36/600) (x l f c b a = 48/600)<br><br>

y z (w v = 55/600) (t s n m = 56/600) (q p o h g = 63/600) (u k j r i e d = 78/600) (x l f c b a = 48/600)<br><br>

y z (t s n m = 56/600) (q p o h g = 63/600) (u k j r i e d = 78/600) (w v x l f c b a = 103/600)<br><br>

y z (t s n m q p o h g = 119/600) (u k j r i e d = 78/600) (w v x l f c b a = 103/600)<br><br>

y (z = 150/600) (t s n m q p o h g = 119/600) (u k j r i e d w v x l f c b a = 181/600)<br><br>

(y = 150/600) (z t s n m q p o h g = 269/600) (u k j r i e d w v x l f c b a = 181/600)<br><br>

(z t s n m q p o h g = 269/600) (y u k j r i e d w v x l f c b a = 331/600)<br><br>

(z t s n m q p o h g y u k j r i e d w v x l f c b a = 600/600)<br><br>

The codes would then be as follows:<br><br>

a: 000111111<br> b: 000111110<br> c: 00011110<br> d: 0001110<br> e: 0011110<br> f: 0001110<br> g: 110111<br> h: 110110<br> i: 001110<br> j: 001011<br> k: 001010<br> l: 00010<br> m: 11111<br> n: 11110<br> o: 11010<br> p: 11001<br> q: 11000<br> r: 00110<br> s: 1111<br> t: 1110<br> u: 00100<br> v: 00001<br> w: 00000<br> x: 00010<br> y: 01 <<<--- y and z really could have been switched; I just went alphabetically<br> z: 00 <<<<br><br>

<nowiki>By considering a common denominator 600, I have only used the numerator for comparison.

(Double click on the image to get a full view).

Following are the codes for the alphabets:

a: 000011111
b: 000011110
c: 00001110
d: 1100111
e: 1100110
f: 0000110
g: 111011
h: 111010
I: 110010
j: 001011
k: 001010
l: 000010
m: 11111
n: 11110
o: 11100
p: 11011
q: 11010
r: 11000
s: 00111
t: 00110
u: 00100
v: 00011
w: 00010
x: 00000
y: 10
z: 01
</nowiki>

First, form a tree for every letter.

[a 0.0017] [b 0.0033] [c 0.005] [d 0.0067] [e 0.0083] [f 0.01] [g 0.0117] [h 0.0133] [i 0.015] [j 0.0167] [k 0.0183] [l 0.02] [m 0.0217] [n 0.0233] [o 0.025] [p 0.0267] [q 0.0283] [r 0.03] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Then, merge trees with the lowest probability.

Iteration 1: [b, a 0.005] [c 0.005] [d 0.0067] [e 0.0083] [f 0.01] [g 0.0117] [h 0.0133] [i 0.015] [j 0.0167] [k 0.0183] [l 0.02] [m 0.0217] [n 0.0233] [o 0.025] [p 0.0267] [q 0.0283] [r 0.03] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 2: [b, a, c 0.01] [d 0.0067] [e 0.0083] [f 0.01] [g 0.0117] [h 0.0133] [i 0.015] [j 0.0167] [k 0.0183] [l 0.02] [m 0.0217] [n 0.0233] [o 0.025] [p 0.0267] [q 0.0283] [r 0.03] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 3: [b, a, c 0.01] [e, d 0.015] [f 0.01] [g 0.0117] [h 0.0133] [i 0.015] [j 0.0167] [k 0.0183] [l 0.02] [m 0.0217] [n 0.0233] [o 0.025] [p 0.0267] [q 0.0283] [r 0.03] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 4: [b, a, c, f 0.02] [e, d 0.015] [g 0.0117] [h 0.0133] [i 0.015] [j 0.0167] [k 0.0183] [l 0.02] [m 0.0217] [n 0.0233] [o 0.025] [p 0.0267] [q 0.0283] [r 0.03] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 5: [b, a, c, f 0.02] [e, d 0.015] [h, g 0.025] [i 0.015] [j 0.0167] [k 0.0183] [l 0.02] [m 0.0217] [n 0.0233] [o 0.025] [p 0.0267] [q 0.0283] [r 0.03] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 6: [b, a, c, f 0.02] [e, d, i 0.03] [h, g 0.025] [j 0.0167] [k 0.0183] [l 0.02] [m 0.0217] [n 0.0233] [o 0.025] [p 0.0267] [q 0.0283] [r 0.03] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 7: [b, a, c, f 0.02] [e, d, i 0.03] [h, g 0.025] [k, j 0.035] [l 0.02] [m 0.0217] [n 0.0233] [o 0.025] [p 0.0267] [q 0.0283] [r 0.03] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 8: [b, a, c, f, l 0.04] [e, d, i 0.03] [h, g 0.025] [k, j 0.035] [m 0.0217] [n 0.0233] [o 0.025] [p 0.0267] [q 0.0283] [r 0.03] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 9: [b, a, c, f, l 0.04] [e, d, i 0.03] [h, g 0.025] [k, j 0.035] [n, m 0.045] [o 0.025] [p 0.0267] [q 0.0283] [r 0.03] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 10: [b, a, c, f, l 0.04] [e, d, i 0.03] [h, g, o 0.05] [k, j 0.035] [n, m 0.045] [p 0.0267] [q 0.0283] [r 0.03] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 11: [b, a, c, f, l 0.04] [e, d, i 0.03] [h, g, o 0.05] [k, j 0.035] [n, m 0.045] [q, p 0.055] [r 0.03] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 12: [b, a, c, f, l 0.04] [e, d, i, r 0.06] [h, g, o 0.05] [k, j 0.035] [n, m 0.045] [q, p 0.055] [s 0.0317] [t 0.0333] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 13: [b, a, c, f, l 0.04] [e, d, i, r 0.06] [h, g, o 0.05] [k, j 0.035] [n, m 0.045] [q, p 0.055] [t, s 0.065] [u 0.035] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 14: [b, a, c, f, l 0.04] [e, d, i, r 0.06] [h, g, o 0.05] [k, j, u 0.07] [n, m 0.045] [q, p 0.055] [t, s 0.065] [v 0.0367] [w 0.0383] [x 0.04] [y 0.25] [z 0.25]

Iteration 15: [b, a, c, f, l 0.04] [e, d, i, r 0.06] [h, g, o 0.05] [k, j, u 0.07] [n, m 0.045] [q, p 0.055] [t, s 0.065] [w, v 0.075] [x 0.04] [y 0.25] [z 0.25]

Iteration 16: [b, a, c, f, l, x 0.08] [e, d, i, r 0.06] [h, g, o 0.05] [k, j, u 0.07] [n, m 0.045] [q, p 0.055] [t, s 0.065] [w, v 0.075] [y 0.25] [z 0.25]

Iteration 17: [b, a, c, f, l, x 0.08] [e, d, i, r 0.06] [h, g, o, n, m 0.095] [k, j, u 0.07] [q, p 0.055] [t, s 0.065] [w, v 0.075] [y 0.25] [z 0.25]

Iteration 18: [b, a, c, f, l, x 0.08] [e, d, i, r, q, p 0.115] [h, g, o, n, m 0.095] [k, j, u 0.07] [t, s 0.065] [w, v 0.075] [y 0.25] [z 0.25]

Iteration 19: [b, a, c, f, l, x 0.08] [e, d, i, r, q, p 0.115] [h, g, o, n, m 0.095] [k, j, u, t, s 0.135] [w, v 0.075] [y 0.25] [z 0.25]

Iteration 20: [b, a, c, f, l, x, w, v 0.155] [e, d, i, r, q, p 0.115] [h, g, o, n, m 0.095] [k, j, u, t, s 0.135] [y 0.25] [z 0.25]

Iteration 21: [b, a, c, f, l, x, w, v 0.155] [e, d, i, r, q, p, h, g, o, n, m 0.21] [k, j, u, t, s 0.135] [y 0.25] [z 0.25]

Iteration 22: [b, a, c, f, l, x, w, v, k, j, u, t, s 0.29] [e, d, i, r, q, p, h, g, o, n, m 0.21] [y 0.25] [z 0.25]

Iteration 23: [b, a, c, f, l, x, w, v, k, j, u, t, s 0.29] [y, e, d, i, r, q, p, h, g, o, n, m 0.46] [z 0.25]

Iteration 24: [b, a, c, f, l, x, w, v, k, j, u, t, s, z 0.54] [y, e, d, i, r, q, p, h, g, o, n, m 0.46]

Iteration 25: [b, a, c, f, l, x, w, v, k, j, u, t, s, z, y, e, d, i, r, q, p, h, g, o, n, m 1.00]