Program that allows operator to manage print queue

Assignment Help Programming Languages

Reference no: EM13906596

1. Compare the growth rates of the following pairs of functions:

a. f(n) = n and g(n) = (n + 1) / 2.

b. f(n) = n² and g(n) = n² + 6n.

c. f(n) = log n and g(n) = log n².

d. f(n) = 2ⁿ and g(n) = 2²ⁿ.

e. f(n) = 5n and g(n) = 4n^3/2.

2. Show that:

a. (n + 1)³ is Ο(n³).

b. 2^{n + 1} is Ο(2ⁿ).

c. n is o(n log n).

d. n² is ω(n).

e. n³ log n is ?(n³).

3. Give a big-Oh characterization of the running time of the following loops in terms of n.

a. Algorithm 1:

s = 0

for i = 1 to n

s = s + i

b. Algorithm 2:

p = 1

for i = 1 to 2 * n

p = p * i

c. Algorithm 3:

p = 1

for i = 1 to n ** 2

p = p * i

d. Algorithm 4:

s = 0

for i = 1 to 2 * n

for j = 1 to i

s = s + i

e. Algorithm 5:

s = 0

for i = 1 to n ** 2

for j = 1 to i

s = s + i

4. In this problem, you are required to write a program that allows an operator to manage a (simulated) print queue. Your program must include facilities to support the following print queue operations:

a. List all the jobs.

b. Add a new job.

c. Remove a job.

d. Release the next job.

e. Increase the priority of a job.

f. Decrease the priority of a job.

The print queue should be implemented as a priority queue based upon the binary heap with hashing algorithms pseudocode provided on the CS340 Algorithms web page. The data structures used to implement your program might look something like this:

struct Job

{

int priority;

int jobNo;

string filename;

int fileSize;

};

struct HashPointer

{

int jobNo;

int location;

};

struct PrintQueue

{

int elementCount;

Job a [HEAP_SIZE];

HashPointer h [HEAP_SIZE];

};

The print queue should provide storage for up to 15 jobs (i.e., HEAP_SIZE=16). A job in the print queue (found in the Job array a in PrintQueue) is completely described by the priority, jobNo, fileName, and fileSize members of Job. The jobNo for each job is a unique value that is incremented after each new job is added to the print queue. The jobNo should be initialized to 1. For each new job added to the print queue, the values for priority, fileName, and fileSize are entered by the operator. Valid values for the priority member must be in the range from 1 to 3, inclusive, where 1 is the highest priority and 3 is the lowest. Whenever there is more than one job with the same priority, the job with the smaller file size will be considered to have higher priority. Jobs in the print queue are ordered by priority. The HashPointer array h in PrintQueue is used for finding and directly accessing a job in the Job array a.

Once your program is implemented and tested, you can demonstrate that it works by following the sequence of events given below:

- Create print queue

- List all

- Insert a153 // a = file name, 15 = file size, 3 = priority (a will be assigned jobNo=1)

- Insert b103 (b will be assigned jobNo=2)

- Insert c53 (c will be assigned jobNo=3)

- List all // 3: c 5 3\n 2: b 10 3\n 1: a 15 3\n (3, 2, and 1 are job numbers and \n is meant to indicate that each job should be printed on a new line)

- Insert d202 (d will be assigned jobNo=4)

- Insert e252 (e will be assigned jobNo=5)

- Insert f152 (f will be assigned jobNo=6)

- List all

- Release next

- List all

- Insert g154

- Insert g152 (g will be assigned jobNo=7)

- Change priority 12 // 1 = job number of a, 2 = new priority

- List all

- Change priority 73

- Change priority 82

- Change priority 21

- Change priority 54

- List all

- Remove 3 // 3 = job number of c

- Remove 5

- List all

- Release next

- List all

If you are working alone, submit to UR Courses: (1) any .cpp and .h files you might have created (and only the .cpp and .h files) zipped into one file and (2) a single script file showing the execution of your program as you follow the sequence of events given above.

If you are working in a partnership, one of the partners should submit to UR Courses: (1) a file named partners that provides the name and student numbers of the partners, (2) any .cpp and .h files you might have created (and only the .cpp and .h files) zipped into one file and (3) a single script file showing the execution of your program as you follow the sequence of events given above. The other partner/s should submit to UR Courses: (1) a file named partners that provides the name and student numbers of the partners. Note that all partners need to submit the partners file.

5. The dynamic linked list topological sorting algorithm pseudocode provided on the CS340 Algorithms web page generates only one possible ordering of the items. In some situations, it may be that one or more items can be interchanged and the output generated will be another possible ordering of the items. And in other situations, if the items were tasks in constructing a house, for example, or courses offered at a university, it may be that one or more tasks could be done concurrently, or one or more courses could be taken concurrently.

In this problem, you are required to implement the dynamic linked list topological sorting algorithm pseudocode provided on the CS340 Algorithms web page. However, you are required to modify the algorithm so that it identifies items that can occur concurrently.

After the data structure has been built in the input phase, print it out in the following format (the data shown below is based on the example shown in class):

Leader 1

element = 1

inDegree = 0

nextLeader = 2

Follower 1 = 2

Follower 2 = 3

Leader 2

element = 2

inDegree = 1

nextLeader = 4

Follower 1 = 4

Follower 2 = 10

Leader 10

element = 9

inDegree = 1

nextLeader = N/A

Follower 1 = 10

Follower 2 = 4

In the output phase, create a list of items, one per line, except for concurrent items. Concurrent items should be listed on the same line. For example, if the problem consists of items A, B, C, and D, and the output is

B C

this implies that B and C are concurrent items.

Once your program is implemented and tested, you can demonstrate that it works by using the CS_Prerequisites.txt file in the /home/venus/hilder/cs340/assignment2/datafiles directory as input.

If you are working in a partnership, one of the partners should submit to UR Courses: (1) a file named partners that provides the name and student numbers of the partners, (2) any .cpp and .h files you might have created (and only the .cpp and .h files) zipped into one file and (3) a single script file showing the execution of your program using the CS_Prerequisites.txt file as input. The other partner/s should submit to UR Courses: (1) a file named partners that provides the name and student numbers of the partners. Note that all partners need to submit the partners file.

Reference no: EM13906596

Questions Cloud

Determine the activation energy for steady-state creep : Three samples of aluminium are subjected to a constant stress and the times required to produce a constant strain of 0.1% during steady state creep at different temperatures are shown in table 1 below.-The temperature at which a strain of 0.1% is p..

Find the probability of the second type error : Let x1,..., x16 be an independent sample from a normal distribution N(μ, 5). For the following test problem: Ho: μ = 6.5 ↔Ha: μ ≠6.5, let the rejection region be W = {|x-6.5| ≥ c}, If μ = 7.5 is correct, find the probability of the second type erro..

Programming languages for example pascal : Some programming languages for example Pascal have used the semi colon to seperate statements while java uses it to terminate the statements. which of them in your opinion is most natural and least likely to result in syntax errors? support your a..

Determine the heat transfer experienced by the calorimeter : Determine the heat transfer (q) experienced by the calorimeter for this reaction. b. Determine the ?Hrxn per mole of HI. c. Identify whether this reaction is endothermic or exothermic and explain your reasoning.

Program that allows operator to manage print queue : You are required to write a program that allows an operator to manage a (simulated) print queue. Your program must include facilities

Downward flow of information : Using the "downward flow of information" concept, discuss the HazCom responsibilities of chemical producers, companies whose employees use chemicals, and the employees themselves. Response must be 200 words in length.

Describe the steps of the systems development life cycle : Your assignment should describe the steps of the Systems Development Life Cycle (SDLC) discussed in Topic 4 of the subject.

How would you distinguish quality management from qi : How would you distinguish quality management from QI in healthcare? Please provide some examples.

Elements in a two-dimensional array : Write a value-returning method that returns the number of columns with n elements in a two-dimensional array of chars, where n is a parameter of the method. Include code to test your method.

User Account

All Pages