Adhere to the Code of Academic Integrity. You may discuss background issues and general strategies with others and seek help from course staff, but the implementations that you submit must be your own. In particular, you may discuss general ideas with others, but you may not work out the detailed solutions with others. It is never OK for you to see or hear another student’s code and it is never OK to copy code from published/Internet sources. If you feel that you cannot complete the assignment on you own, seek help from the course staff.
In order to give you practice on specific programming constructs, some Matlab functions/features are forbidden in assignments. Do not use the break or continue statement in any assignment in CS 1132. Only the built-in functions that have been discussed in class or in the assigned reading so far may be used.
Many popular events, such as concerts and sports championships, are oversubscribed—more people want to attend than the number of tickets available. One way to decide who gets to attend is to distribute tickets via a lottery: applicants are selected at random to receive tickets until all of the tickets are gone. In this assignment, you will write code to assign tickets in an unbiased way and analyze the likelihood of groups of friends being able to attend together.
Using the help command, learn about the rand(), ceil(), fix(), and floor() functions. After reading their brief description, implement a random integer generator using those functions only. Implement the following function:
function result = myRandInt(startInt, endInt)
% Returns an integer from startInt to endInt, inclusive, with equal probability.
% If startInt > endInt, set startInt as the upper bound and endInt as the
% lower bound.
% startInt, endInt, and result are each an integer.
Remember what it means to implement a function: write code according to the specification. Following specifications is not a choice; it is a requirement. Code that does not follow specifications is incorrect. Your function file must have the exact function header given here, including the name of the function as well as the names and order of the parameters. Correspondingly the file name must be myRandInt.m. Copy the entire function comment given above into your function file—notice that the comment must explain all the parameters.
Suppose every applicant is given an ID number; then all applicant IDs can be stored in a vector. Since ID numbers are arbitrary, it is not practical to directly generate a random ID belonging to one of the applicants in order to decide who gets a ticket. However, it is easy to generate a random vector index, then select the ID stored in that element.
When an applicant is selected, their ID should be removed from the vector (the same applicant should not be selected twice).
One way to effectively remove an element is to copy the ID at the last index (end) of the vector to the just-selected position, then decrease the length of the vector by 1 (which can be done using the statement v(end)=[]). Remember that modifying a vector in a function only affects the copy of the vector in the function’s private workspace; to let the caller see the change, a function must return its copy of the vector via an output parameter.
Implement the following function to select a random ID from a vector and return that ID, as well as a copy of the vector with that ID removed (the order of IDs in the returned vector does not need to be preserved). Make effective use of myRandInt().
function [id, applicants] = selectApplicant(applicants)
% Select and remove a random element from `applicants`.
% `id` is the value of the selected element.
% The order of elements in `applicants` need not be preserved when the
% selected value is removed.
% `applicants` is assumed to initially be non-empty.
Example: one possible set of output from selectApplicant([3,1,4,15,9]) is id = 1 and applicants = [3, 9, 4, 15]. Test your implementation in the Command Window before moving on (remembering that the selected ID is random).
To check that our selection procedure is behaving as intended, it would be helpful to visualize the results. Implement the following function to print out the sequence of applicant IDs prior to selection, putting brackets around the ID that was ultimately selected.
function printSelection(applicants, id)
% Neatly print which applicant in a pool was selected
% Print the elements of non-empty vector `applicants` on a single line,
% separated by spaces. If an element is equal to `id`, surround it with
% brackets.
Example: printSelection([3,1,4,15,9], 1) should print 3 [1] 4 15 9. Test your implementation in the Command Window before moving on.
Hint: You can print a line of text one character at a time with fprintf() by only using the newline character, \n, when you are ready to end the line. Consider the following code fragment:
fprintf('H')
fprintf('e')
fprintf('llo')
fprintf('\n')
The printed text would be the same as the output of fprintf('Hello\n').
Write a function chooseAttendees() to select up to nTickets attendees from a pool of applicants using selectApplicant().
For each applicant selected, call printSelection() to highlight them in the pool. By looking at the sequence of prints, you should be able to double-check that applicants are properly removed from the pool after being selected.
If there are more tickets available than applicants in the pool, then your function should stop after all applicants have been selected. Make effective use of a while-loop to perform the repeated selections. The function should return a vector containing the IDs of the chosen attendees.
Use the following function header, but write your own documentation comments:
function attendees = chooseAttendees(applicants, nTickets)
Below are several lines of example output:
3 1 4 15 9 [2] 6 5 35
3 [1] 4 15 9 35 6 5
3 5 4 15 [9] 35 6
[3] 5 4 15 6 35
The chosen attendees would be [2,1,9,3] in this case. Test your implementation in the Command Window before moving on (remembering that the chosen IDs are random).
In this final problem, you will use simulation to estimate the probability of a complicated event. Alice, Bob, Charlie, and Eve are the first of 20 students to apply for concert tickets at a venue with only 7 seats. Alice, Bob, and Charlie only want to attend if at least two of them can go together. However, Charlie refuses to go if Eve will also be there. (Note that tickets are non-transferrable and non-returnable.)
Write a script, ConcertSim, to estimate the probability that at least two of Alice, Bob, and Charlie will actually attend the concert. Your script should simulate a large number of trials where tickets are randomly distributed to the applicants and determine after each trial whether or not at least two of the friends are selected and choose to attend.
The probability of an event is estimated as the number of occurrences of that event divided by the number of trials. You may use either selectApplicant() (in a loop) or chooseAttendees() to distribute the tickets in each trial.
Hint: you may assign IDs to the applicants however you want, but a convenient scheme would be to use a range expression to make them the numbers 1–20; then the four students involved are easy to identify.
Be sure to parameterize your script so that it is easy to change the number of applicants, the number of tickets, and the number of trials (that is, store those parameters in variables with meaningful names at the top of the script). The final estimate should be printed to the command window. Run your script multiple times to get a sense for the uncertainty in the estimate, and write your estimate of the probability in a comment at the bottom of your script (if the range of estimates spans more than 5%, increase your number of trials).
The following is a list of the minimum necessary criteria that your assignment must meet in order to be considered satisfactory. Failure to satisfy any of these conditions will result in an immediate request to resubmit your assignment. Save yourself and the graders time and effort by going over it before submitting your assignment for the first time. Although all these criteria are necessary, meeting all of them might still not be sufficient to consider your submission satisfactory. We cannot list everything that could be possibly wrong with any particular assignment!
;). At the same time, make sure that all output that your program intentionally produces is formatted in a user-friendly way.myRandInt.m, selectApplicant.m, printSelection.m, chooseAttendees.m, and ConcertSim.m to CMS before the deadline. Late submission is accepted up to 24 hours after the deadline with a 10% penalty. If you upload or re-upload any file during the late submission period, the 10% penalty will apply to the whole assignment.