CSCI 102 – HW 9

HW 9

You will write a program that utilizes arrays.

Writing Your Code

There are 2 parts to this assignment. Each will be submitted through Vocareum. We recommend you use the web-based editor and compiler available through Vocareum.

Program 1 - Counting Occurrences of numbers [-9 to +9]

Description & Requirements

In this program, the user will enter two digit positive and negative integers (i.e. -99 to +99) but your job is to only count the number of occurrences of each integer between [-9 and +9], inclusive. When the user types 100 or -100 the program should exit and print out the statistics of how many times each integer between [-9 and +9] occurred as well as how many numbers outside the range of [-9 to +9] occurred.

You may assume the user will never type in a number that has magnitude (absolute value) of 101 or more.

Hints: Arrays act like tables mapping an index to some desired value. Here we want to map the integer we receive -9 to +9 to the number of times we’ve entered that value. However, array indexing must be 0 to n-1 (indexes cannot be negative). Can you do some math to convert a value in the range [-9 +9] to [0-18].

Other Requirements

You must use an array to store the counts of the numbers between -9 and +9
There is no upper bound on how many values the user may enter before 100 or -100 is input. It may seem like you need array to store the input values, but if you can process an input immediately and do not need it again, you don’t need an array to store the values. Just process them and move on. Consider what the needs are for this program.
Your output should list each number from -9 to +9 on a separate line followed by a colon and a space (:) and then the number of times that number was entered (i.e. number of occurrences). After printing out those 19 lines, you should output a final line that reads Out Of Range: n where n is the actual number of values that were entered but outside the range -9 to +9. You must follow this format or our auto checker will not work and you will lose points.

Example 1

If the user entered:

-10 -1 5 7 99 5 100

Your program should output exactly the lines:

-9: 0
-8: 0
-7: 0
-6: 0
-5: 0
-4: 0
-3: 0
-2: 0
-1: 1
0: 0
1: 0
2: 0
3: 0
4: 0
5: 2
6: 0
7: 1
8: 0
9: 0
Out Of Range: 2

This output results because the number -1 is entered once, 5 is entered twice, 7 is entered once, and the other 2 numbers are outside the range of -9 to +9. 100 causes the program to exit and is NOT counted.

Example 2

If the user entered:

-10 -1 9 -10 2 7 -5 5 -1 -7 -4 -3 -10 -7 -3 -12 -1 3 9 -11 -100

Your program should output exactly the lines:

-9: 0
-8: 0
-7: 2
-6: 0
-5: 1
-4: 1
-3: 2
-2: 0
-1: 3
0: 0
1: 0
2: 1
3: 1
4: 0
5: 1
6: 0
7: 1
8: 0
9: 2
Out Of Range: 5

Example 3

If the user entered:

-3 8 5 -9 9 -3 -6 10 -2 3 -11 -7 11 5 -6 0 8 0 -4 11 100

Your program should output exactly the lines:

-9: 1
-8: 0
-7: 1
-6: 2
-5: 0
-4: 1
-3: 2
-2: 1
-1: 0
0: 2
1: 0
2: 0
3: 1
4: 0
5: 2
6: 0
7: 0
8: 2
9: 1
Out Of Range: 4

Be sure to indent your code correctly and add comments describing major chunks of your code.

Idioms Used

Study and consider how to use some or all of the following idioms:

Submitting your code

*When you believe your program is finished** login to Vocareum, start the HW10 assignment (Count Part), and in the upper-left of the resulting window, click New..File. A textbox will appear where you can type in the filename (leave the work/ portion there and) just type count.cpp. In the left window pane you should now see count.cpp appear (**it must be named count.cpp**) and you can click on it to open it. A blank window should appear on the right. You can write your program in that windows. You can click the Run or Submit buttons to test your program and submit it, respectively.

If you’ve used some other editor, cut/paste your code from your other tab/window to this window. Alternatively, rather than clicking New..File, you can just use the Upload button to upload the file if you have it on your VM (but the file must be named count.cpp)..

When you click Submit it should run a few automated tests to let you know if it compiled and passed some basic sanity checks. Look at the output to ensure things are working. If not, you’ll need to modify your code and resubmit.

Be sure you click submit otherwise your code will just be saved, but not submitted!!

Please post any questions about using Vocareum on EdStem.

Program 2 - Priority Selection

Description & Requirements

This program models a system with n people (1 <= n <= 100) numbered 0 to n-1 and implements a priority mechanism to select one of the n people as they request a single shared resource (e.g. a teaching assistant, a waiter/waitress, a printer, etc.). These n people may request access to the shared resource which can only serve 1 person at a time, but since many people may request the resource at the same time, a priority scheme must be used to select the 1 person who will be granted access to use the resource. The priority scheme should grant access to the requestor who has not used the resource in the longest time (i.e. if you were just granted use of the resource, you should have the lowest priority at the next time step). Since no one has used the resource when the system starts, we will simply use an initial priority order of the people based on their ID such that person 0 has the highest priority initially (i.e. person 0 is deemed to have not used the resource in the longest time), then person 1, 2, 3 and so on.

Your task is to complete the program where each user inputs their desire to use the resource at each time unit (or round) with a Boolean input of 1 = Requesting or 0 = Not Requesting. For example, if n=4 a sample input for one time step (or round) might be:

0 1 0 1

Each entry is a Boolean where the first input (i.e. 0) corresponds to person 0 (not requesting in this case), the second input (i.e. 1) corresponds to person 1 (requesting in this case), etc. By repeatedly using cin to read a bool, you can scan these inputs.

Once the inputs for a given time unit have been received, the program should output which user is granted access to the resource based on all those who are requestingI (person 1 in this case) by outputting the message:

Person 1 selected.

The program should then repeat this process for a new round of inputs (with updated priority based on who just received access to the resource) until an input of all 0 requests is received (i.e. quit when no one requests the resource).

Example Input/Output

To start the user enters how many requesters will enter input each round by entering a single integer (in this case, 4).

Person 1 and 3 request:

0 1 0 1

Expected output (since initially we prioritize 0, then 1, …, then person n-1):

Person 1 selected.

In the next round person 1, 2, and 3 request:

0 1 1 1

Expected output (since person 1 was selected last time, they now have the lowest priority and thus 2 should be chosen):

Person 2 selected.

In the next round person 2 requests:

0 0 1 0

Expected output (since person 2 is the only one that is requesting, it is given access even though it has the lowest priority):

Person 2 selected.

In the next round all persons request:

1 1 1 1

Expected output (Person 0 has not requested and was initially higher in priority than person 3):

Person 0 selected.

Again, all persons request again:

1 1 1 1

Expected output (Person 3 has not been chosen, so it has the highest priority at this time):

Person 3 selected.

Finally, no one requests and thus we QUIT:

0 0 0 0

The entire program run (with input and output) should look like:

4
0 1 0 1
Person 1 selected.
0 1 1 1
Person 2 selected.
0 0 1 0
Person 2 selected.
1 1 1 1
Person 0 selected.
1 1 1 1
Person 3 selected.
0 0 0 0

Approach

The key issue in this program is to track the priority of requesters based on who was granted access to the resource in the past. Two approaches can be used for this.

Option 1: Keep an array where the values are user IDs and they are ordered from highest to lowest so that the ID at location 0 has the highest priority and the ID at location n-1 has the lowest priority (i.e. just received access to the resource on the previous round of requests). Thus, once the resource has been granted to a user, their ID is moved to the last entry of the array and all entries (indices) greater than the old location of the selected user’s are shifted up a spot. (This is a form of the rotation/shift idiom.)

For example, initially the priority array might look like:

Value: |  0  |  1  |  2  |  3  |

When person 1 and person 3 requested it is clear that the value 1 comes first in the array (scanning in order) and so should be granted the resource. After giving the resource to person 1, the priority array could be updated to now give person 1 the lowest priority:

Value: |  0  |  2  |  3  |  1  |

Thus, on the next request when person 1, 2, and 3 all request at the same time, person 2 would be granted the resource.

This approach is further illustrated in the following graphic.

Option 2: Keep an array where the index corresponds to a user ID and the value corresponds to that user’s current priority where the highest priority ID (location) will have the value of 0 (highest priority) and the lowest priority user will have a value of n-1. Thus, once the resource has been granted to a user, the value at the user’s index is set to n-1 and all users with a value greater than the selected user’s old priority are decremented by 1 (or some other alternate scheme you may deduce).

For example, initially the priority array might look like:

Index: |  0  |  1  |  2  |  3  |
--------------------------------
Value: |  0  |  1  |  2  |  3  |

When person 1 and person 3 requested we find the index with the smallest value AND a boolean request of 1 (in this case person 1). We can then update person 1 to have the lowest priority by changing entry 1 to have the highest value while decrementing others.

Index: |  0  |  1  |  2  |  3  |
--------------------------------
Value: |  0  |  3  |  1  |  2  |

Thus, on the next request when person 1, 2, and 3 all request at the same time, person 2 would be granted the resource since they have the lowest priority value of any requestor. At that time the array would be updated to contain:

Index: |  0  |  1  |  2  |  3  |
--------------------------------
Value: |  0  |  2  |  3  |  1  |

Note: Other approaches exist as well and any reasonable approach that works is acceptable.

Requirements

The input n will come first (and is guaranteed to be between 1 and 100) and then rounds of inputs consisting of n 1s or 0s, with whitespace separating all input values.
You do not need to give a message or prompt to receive the n Booleans each round, but you may.
Your output must be in the format Person x selected. where x is the integer ID (0-n-1) of the person chosen.
Your program must quit without any output when the user enters all 0 requests.

Be sure to indent your code correctly and add comments describing major chunks of your code.

Idioms Used

Study and consider how to use some or all of the following idioms:

Submitting your code

When you believe your program is finished login to Vocareum, start the HW10 assignment (Priority Part), and in the upper-left of the resulting window, click New..File. A textbox will appear where you can type in the filename (leave the work/ portion there and) just type pri.cpp. In the left window pane you should now see pri.cpp appear (**it must be named pri.cpp**) and you can click on it to open it. A blank window should appear on the right. You can write your program in that windows. You can click the Run or Submit buttons to test your program and submit it, respectively.

Be sure you click submit otherwise your code will just be saved, but not submitted!!

Please post any questions on EdStem.