CSC 248/448  Assignment #1

Due: at the beginning of class, Tuesday Sept. 16, 2003

For questions on this assignment, you may contact me (james@cs) or Myrosia Dzikovska (myros@cs).

 

Part A: Written Questions

 

1. For each answer, explicitly identify the random variables you use, their sample spaces, and summarize the information specified in the question in terms of probabilities.

a.       What's the probability that your friend will be late for a movie when it's raining, if the probability of rain is 30%, the probability of your friend being late for a movie is 50%, and the probability of rain given that your friend is late, is 20%?

b.      If whether Harry wins a race is independent of how I got to the racetrack, what is the probability that he wins when I drive, if the probability of him winning is .3 and the probability of me driving is .5.

c.       An urn contains b blue balls and c cyan balls. A ball is drawn at random, its color recorded and the ball is returned to the urn, and then a ball is drawn again. What is the probability that (i) the first ball drawn is cyan, (ii) the second ball drawn is cyan, (iii) the first two balls drawn are cyan, (iv) that the first ball drawn is cyan given that the second ball drawn is cyan.

 

2. Answer the same questions as in part (1c), except that whenever a ball is drawn from the urn, when it is replaced, we also add d additional balls of the same color.

3.  For two probability distributions P1 and P2, both modeling a random variable X with two values a and b, show that the function defined by

                              l1 * P1(X) + l2 * P2(X)

is guaranteed to be a probability distribution if both l1 and l2 and greater or equal to 0 and less than or equal to 1, and l1 + l2= 1. If you canąt produce a formal proof, you can get partial credit for laying out how you would prove it, and proving the parts you can.

 

Part B: Programming

For this assignment, you will be given two corpora: part of the Brown Corpus, which is a corpus of written English including news and fiction texts, and part of the Switchboard corpus, which is a corpus of transcribed informal conversations. Please answer the questions posed for each of these.

 

1.       Clean up the Copora

The corpus data in Brown corpus are tagged with parts of speech, in the format "word/tag", for example, "company/N". Write a Perl program that strips away the tags, leaving only the words in the corpus. Count the number of words in the corpus.

 

The data in Switchboard corpus have annotations about non-verbal noises in square brackets, such as [laughter] etc. Write a program that removes them from the corpus. Count the number of words in the corpus, and the number of annotations you removed.

 

2.      Collect Data from Corpora:

Given an untagged corpus, write a Perl program that reads in a corpus and calculates the frequencies of all words. Answer the following questions

 

- What are the 10 most frequent words in the corpus?

- How many words occurred just once? 2 times? 3 times?

 

3. Given the word frequency counts in the corpus, verify how well Zipf's law holds for this corpus. Zipf's law states that "In the English language, the probability of encountering the rąth most common word is given roughly by K/r for r up to 1000, for some constant K". It has been suggested previously that K=0.1. Answer the following questions:

·        identify the constant K that best "fits" the data you collect from the two corpora, using some measure of "fit" of your own design. Justify in the documentation why your measure of fit is reasonable.

·        For the 50 most frequent terms in the corpus and your constant K, for how many the frequency is predicted correctly by Zipf's law within a 5% error margin? Within a 10% error margin?

·         Is Zipf's law still correct for low frequency terms in the corpus? Specifically, if a term occurred once, two or three times in the corpus, is it's frequency correctly predicted within a 5 or 10% error margin with your constant K?

 

 

Please submit the following for this assignment

·   Your source code files in Perl. The code should be easy to read and commented appropriately. Please make sure that the code can be run on the CS network (i.e. it does not use any Perl modules not globally installed there).

·   The README file that explains how to run your code, and what to expect in the output. It should include

o       The names of all program files you submitted, and their command line arguments

o       Examples which show how to run them

o       The printouts from your test run

o       The list of known bugs, if there are and

·   A writeup that answers more general questions asked in this assignment (you can include it as part of the README file). As part of the general writeup, describe any problems you encountered with the data, and how you solved them.

 

Your grade on the programming part will be based on the following: 50% for a written analysis of your approach, discussion of what testing and evaluation you did to verify the use of your approach, and documentation on how to use your program, 25% for well-written code, and 25% for the results of running on the test corpora.