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

- 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

- Release next

- 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

A

B C

D

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 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 using the CS_Prerequisites.txt file 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.