CS 361, Introduction to Data Structures Final Exam Fall 2015

You are not to communicate with anyone else in any manner concerning this exam during the exam period. The ODU Honor code is in effect for the duration. You are to solve no more than 3 of the following problems in C++, using the STL library; each code should run stand-alone as a simulation.  You can develop the code in any environment but they should compile using Code blocks. Submit your solutions as a single zipped file via blackboard.

Q1. Imagine that there are processes that are being generated at random intervals, each process has an id (0001 to 9999) and in addition each process has a complexity score that is directly proportional to the product of its required memory and its expected run time. We can treat the complexity score (c >= 0)  as a random value with a mean of 5and a standard deviation of 1. As the processes are generated they are placed into a queue of length q (q is user input).  Processes are removed from the front of the queue after they have been in the front for c time steps. IF a process is generated and the queue if full then the overload is placed in a separate priority queue with the lowest c score given the highest priority. When room is made in the process queue, it is refilled from the priority queue. Generate a simulation of this process handler.

etc

Q2. Imagine a 3-d chess board (8x8x8) with one knight on it. The knight is placed at location level 0, row 0 and column 1, (standard position), implement an algorithm that will allow the knight to move around the board randomly until 90% of possible locations have been visited. Knights usually move a total of three spaces in an "L" shape. This is still true, but they now can go up one (or down) over two and up two (or down) and over one. There are 512 locations in a 3-d chess board.

Q3. This is an experimental question, please implement the following code fragment in a fully functional C++ code. Given ints j, n, and T: where n is user input, the functions b is return type bool, and both p and q each return a time cost. You will use the value T to store the cumulative sum of those costs.

i. For(j=0; j

ii. {If b(j) {T=T+q(j);}

iii Else {

1. If(b(j+1){T=T+q(j-1);}

2. Else {T=T+p(j+3);}

3. }

iv. }

Where  b(i) takes i+3 seconds and (on average) the function b( ) returns true 50% of the time q(i) takes i+1 seconds and p(i) takes i+2 seconds

Create a graph showing best, average, and worst case T scores for your code in number 3 above for n = powers of 2 from 21 to 216. If there are any results you cannot provide be specific as to the reason. You can modify the best/worst by modifying how often b( ) returns true.

Q4. Using your mountain project source code as a starting point, you are to write a code that randomly chooses one of the triangles on the surface of your mountain, this will be the entrance to your cave. A line segment representing that tunnel beginning at the centroid of that surface travels a distance equal to the average of the three sides of that triangle in the direction normal to that surface INTO the mountain. You should store this segment as a vector beginning at the centroid in the form  v = x_mi + y_mj + z_mk . These x_m, y_m, and z_m values will be referenced many times. At this point what happens is determined by the following table.

As the tunnel splits then there is an additional branch that must be explored. If at any time a branch of the tunnel intersects the surface of your mountain that branch should terminate (hint: consider the 2-d projection of your quads as seen from above).

Save your tunnel system as a set of line segments in a separate data file then plot them with your mountain. They should automatically appear as a different color.

5. Create a class gene that contains a sequence of 4 amino acids (represented by chars A, T, C, G) Generate agene linked list of length L (user input) of class, this is a protein. Generate a second linked list of length L/2< L2 < L. Search for a matching sequence of at least 4 genes (16 acids) that can be found in both proteins. If none exist state so. If they do exist display at what index they can be found in each protein.

6. The equation of an ellipse is show below:

If a and b are random integers in the range [1, 10] accept an integer N (2 to 5) from the keyboard, create N random ellipses, create a data file that contains x, y data for them and then plot them using gnuplot. This is a 2-d problem.