HW#1 --- last modified February 09 2022 23:21:33.

Solution set.

Due date: Feb 14

Files to be submitted:
  Hw1.zip

Purpose: To gain experience with probabilistic analysis and our first randomized algorithms.

Related Course Outcomes:

LO1 -- Analyze or code a randomized algorithm.

Specification:

This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw1.zip file. The written part should be in a file Hw1.pdf. For this part of the homework you should write solutions for the following questions. In what you turn in, first copy and paste the question, then write your solution to it beneath it.

1. Consider the sample space `S` consisting of `n > 1` rolls of a unbiased, six-side die. Consider the event `A_j subseteq S` consisting of `n` rolls where the `j`th roll is `1`. Show `A_j` and `A_i` are pairwise independent assuming `i ne j`. Consider the event `E` that the sum of the `n` rolls is 0 mod 6. Show for each `j`, `A_j` and `E` are pairwise independent. Show that the events `E, A_1, ..., A_n` are not mutually independent.
2. Our analysis the hiring problem shows that it can be useful to be able to pick a function uniformly at random from some space of functions. For the Hiring Problem, the space of functions were permutations of `1, ..., n`. Call a function of `n` inputs `f` symmetric if for any permutation `pi` of `1,..., n`, `f(x_1, ..., x_n) = f(\pi(x_1), ... \pi(x_n)).` For example, the threshold function `T_k^n(x_1,...x_n)` which is equal 1 if `sum_i x_i \geq k` and 0 otherwise is a symmetric function. Let `\mathcal(F_k^n)` be the space of all symmetric functions from `(ZZ_k)^n -> ZZ_k`. Give pseudo-code for an algorithm to generate an element of `\mathcal(F_k^n)` uniformly at random.
3. Consider the Hiring Problem from class. Candidate `i` had a rank(i) which was a number from 1 to n. Each candidate had a distinct rank. Rather than using a rank suppose the candidates had a fitness number fit(i) saying how good the candidate was. Suppose fit(i) is equally likely to be any integer number in the range 1 to `|~f(n)~|`. We only hire a candidate if their fitness number than is better than the current best candidate. Calculate how this would effect the analysis of the expected number of candidates we hire for `f(n) = n/2` and for `f(n) = log_2 n`.

For the coding part of the assignment, I want you to write a program CollectAllPermutations.java (if you use a language different than Java, check with me first that I know that language, and then modify the names of your programs appropriately and have a readme.txt explaining compilation and usage). This program will be compiled using Java 15 with the syntax:

javac CollectAllPermutations.java

Your program will then be run from the command using a command like:

javac CollectAllPermutations n mode

Here `n` is an integer and mode is either the word quiet or the word verbose. If mode is verbose It will use one of the two algorithms from class to generate a random permutation (your choice) on `n` values, and then print that the permutation as a space separated list of numbers, and then continue generating permutations until all the permutations of `n` values have been printed at least once. At which point it should output: "All permutations of `n` collected in `x` iterations" where `x` equal to the number of times it printed out a permutation. In quiet mode, the program operates in the same way, but does not write the permutations, instead only output the last line with the number of iterations required to generate all of them. For example, we might see (depending on the random number generator) an output like:

java CollectAllPermutations 3 verbose
2 1 3
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
1 2 3
3 2 1
All permutations of 3 collected in 8 iterations

If the mode had been quiet only the last line would be output.

Include your code as part of the Hw1.zip file you submit. Then conduct 10 experiments for each positive integer between 2 and 11. I.e., Ten experiments for 2, ten for 3, etc (seed your random number generators differently each time). You can do this programmatically if you want. Determine the average number of iterations for each integer and its standard deviation. Plot the integers and the number of trials with the standard deviations on a clearly labeled graph where you fit the curve that you would expect based on the coupon collector problem to the data using `chi^2` minimization. How well does the curve fit? Write up your experiments and put the graphs in your Hw1.pdf file that you include in the Hw1.zip file you submit.

Point Breakdown