CSCI466 Assignment 1

This subject has a lot of loves and hates. Some people love it while some people hate it. Some people called this subject as "killing" subject for students. The failure rate is high and most people do not understand the topic. Well, if you are a math lover, you will love this subject. This subject is about "PROBABILITY". Yes.. it's about probability. When you toss a coin, there are 50% of chance that it is head, likewise, 50% for the tail. Question for this subject is "how do you make use of it to apply to data communication? how will you code your program so that it is against the unexpected probable data changes?"

Well, this is the assignment 1 questions. You need a calculator for this subject.

1. (a) There is n people in a room. Compute the probability that at least 2 have the same birth month.
Answer: 12^n - {12! / (12-n)!} / 12^n
1. (b) Evaluate this probability when n=3, 4, 5,6.
Answer: Just replace n with numbers in the above formula.

2. Two different suppliers, A and B, provide manufacturer with the same part. All supplies of this part are kept in a large bin. In the past, 5 percent of parts supplied by A and 9 percent of parts supplied by B have been defective. Supplier A supplies 4 times as many parts as supplier B. Suppose you reach into the bin and select a part and find it defective. What is the probability that it was supplied by A?
Answer: Use Bayes' theorem.

3. You are given two urns each containing two biased coins. The coins in urn I come up heads with probability p1, and the coins in urn II come up heads with probability p2≠p1. You are given a choice of (a) choosing an urn at random and tossing the two coins in this urn or (b) choosing one coin from each urn and tossing these two coins. You win a prize if both coins turn up heads. Show that you are better of selecting choice (a).
Answer: There are two methods.

Method 1 : P(both heads) = 1/2 * p1 * p1 + 1/2 * p2 * p2


Method2: P(both heads) = p1 * p2


Since p2≠p1, there are two possible scenarios.
S1: If p1 is greater than p2, then p1=p2+k. Sub p2=0.4, k=0.1, then p1=0.5. Using
Method1: P(both heads) = 0.205
Method2: P(both heads) = 0.200
S2: If p2 is grater than p1, then p2=p1+k. Sub p1=0.4, k=0.1, then p2=0.4.Using
Method1: P(both heads) = 0.125
Method2: P(both heads) = 0.120
In both scenarios, method 1 has higher probability.

4. A discrete memoryless source with source probabilities {0.23,0.20,0.14,0.16,0.10,0.10,0.02,0.05}. Assume corresponding source symbols are "a, b, c, d, e, f, g, h". We are given the test string & the code that will be generated for the test string "daggechfb".

(a) Determine an efficient fixed length of code for the source.
Answer: log2 (possible sources)

(b) Determine the Huffman code for this source and the average length of the code. Also write out the code for test string "daggechfb".
Answer: Construct the Huffman coding tree.


Average Length of Code = p(a).l(a)+p(b).l(b)+....+p(g).l(g) = 2.81 bits

(c) Determine the arithmetic code for test string given the probability distribution for the source.

Follow the example in your lecture note for the calculation.

Well, this is about assignment 1.