Project 2
This project is an introduction to basic algorithms in R. It should demonstrate the fact that writing algorithms in C and R are very different tasks.
1. Read about the quicksort algorithm (in your favorite algorithms
book, on Wikipedia, etc.). Write a quicksort() function.
For inputs of integer vectors such as
x
<- c(14.5,97.9,34.3,71.7,29.1,60.2,29.8,67.5,94.5,17.9,76.8,17.6,6.2,0.0,29.1,50.8,49.3,94.5,45.5,8.9)
or for inputs of character vectors such as
y
<- c("Y","U","Z","K","M","R","S","F","R","Z","D","I","N","I","K","T","S","D","R","F")
the code quicksort(x) should return an integer vector in
sorted order, and the code quicksort(y) should return a
character vector in sorted order.
Do not use a built-in sorting function such as sort()
or order() in your code.
2. Read about the Euclidean algorithm (in your favorite algorithms
book, on Wikipedia, etc.). Write a gcd() function.
For pairs of integer inputs such as 884, 9384, the
code gcd(884,9384) should return the greatest common divisor,
in this case, 68.
3. Read about the faro shuffle, also called the perfect faro shuffle
(in your favorite algorithms book, on Wikipedia, etc.). Write
a faro() shuffle function. If a vector x with even
length 2*n is passed as a parameter to the faro() function, the
result is a vector of the same length as x, with the entries
of x reshuffled as follows: x[1], x[n+1], x[2], x[n+2], ...
In particular, if we write x <- 1:52, then faro(x)
should return the vector c(1,27,2,28,3,29,.........,24,50,25,51,26,52).
[As an interesting
side note, by the way, eight consecutive faro shuffles of this vector
of length 52 will return x to its original state.]
4. Read about the Luhn algorithm, also called the Luhn formula
(in your favorite algorithms book, on Wikipedia, etc.). Write
a luhn() function. If a vector x is passed
as a parameter to the luhn() function, with (for
instance) length(x) equal to n, then the last digit
(namely, x[n]) is a "check digit". The
function luhn() should return TRUE if the parameter is a
mathematically valid account number, or FALSE otherwise. For instance,
if we define
x <- c(4,9,9,2,7,3,9,8,7,1,6)
then luhn(x) yields TRUE.
5. Read about n-bit reflected binary Gray codes
(in your favorite algorithms book, on Wikipedia, etc.). Write
a gray() function, such that gray(n) will generate
the n-bit Gray code. For instance, gray(3) will generate the
8-by-3 matrix:
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0
6. Write a powerof2() function that finds the largest integral power of 2 that divides the both of the inputs. For instance, if 32 divides both of the inputs, but 64 fails to divide at least one of the inputs, then the function should output 32. For examples, powerof2(24,196) should output 4, since 4 is a divisor of both of the inputs, but 8 fails to divide at least one of the inputs.
7. Consider the following leader selection algorithm. A collection of n people are present. Each has a coin that, when flipped, will show heads with probability p, or tails with probability q=1-p. At each stage of the game, the people remaining will all flip their coins simultaneously. There are two possibilities during a round of the game:
a. At least one person in the current round gets heads. In this case, all of the people with heads will remain in the game; any people with tails are completed removed from the game (and are not allowed to return).
b. Everyone currently in the current round gets tails. In this case, all of the people in the current round are selected by the algorithm as the winners, and the game is over.
Write a function LeaderSelection(n,p) that determines the number of winners in the previous algorithm.
8. Explore the properties of the LeaderSelection algorithm. For instance, if p=1/3 and n=1000, what is the expected number of people selected by the algorithm? To understand the performance characteristics of the algorithm on average, you will need to run the algorithm several times.
9. A total of n people begin at the start of the algorithm. Each person has a piece of a paper, a pencil, and a coin that, when flipped, will show heads with probability p, or tails with probability q=1-p. The people each will write a list of H's and T's on their papers, as follows: At the each stage of the algorithm, each person will write one new letter at the end of her piece of paper, which will be H if the person flips heads at that stage, or T if the person flips tails at that stage. The algorithm will stop when each piece of paper contains a unique sequence of H's and T's.
Write a function HTpapers(n,p) that determines the number of rounds necessary so that each piece of paper contains a unique sequence of H's and T's.
10. Explore the properties of the HTpapers algorithm. For instance, if p=3/5 and n=1000, what is the expected number of rounds needed by the algorithm so that all n pieces of papers are unique? To understand the performance characteristics of the algorithm on average, you will need to run the algorithm several times.