CS 361
Spring 2017
Final Exam
You have one week to complete this exam. It is open book, open notes, open website and sample codes. You may NOT speak to any other human being about this exam until have semester grades have been posted. Any violation of this will be forwarded to the ODU Honor Council, just like the service academies you are required to report any attempts to violate this rule. Answer all of the first 5 questions, then complete no more than 3 out of questions 6 to 12. If you choose to solve project 10, then please label all files as q10.cpp, q10.h, q10_drivers.cpp, q10_readme.txt etc.
Compare and contrast in terms of computational complexity the following pairs of containers in the C++ STL. Discuss specifically the cost of insertion and searching.
1. Stack vs. Vector (ordered)
2. Map vs. Vector (unordered)
3. List vs. Priority Queue
4. Create and describe a scenario (problem setting) where:
a. A STL List is appropriate
b. A STL List is NOT appropriate
5. After watching HGTV, your significant other has ordered you to remodel your home. Flooring, paint, fixtures (lights and plumbing), and appliances. Being a post-Kennedean coder you have decided to limit yourself to two data structures. You are to propose a composite data structure such as a tree of vectors etc, to store all the information, think room delineation and improvements. Justify your decision and explain how it would work. There is one more requirement. You data structure must have composite lookup of ORDER N.
Programming Problems: Solve no more than three.
6. A certain secret spy agency is gathering information. The information is divided into several broad categories, (M)ilitary, (U)S Civilian, and (C)orporate. There are events in each category, for this exercise they are just described by the following comma delimited string: “category, Event_Id, Priority, abstract” For example:
“U,E101, 2, a diabetic native American was seen waving feathers at the white house”
Or
“M,E302, 9, POTUS has lost his ducky”
Create a data file that contains 10 such events sorts them into a vector of priority queues with the highest priority being first. Display the contents of this structure to the screen.
7. Create a binary tree structure that is populated by nodes that consist of a random integer and a frequency. The key is the integer value, the frequency is an integer that shows how many times that value has been generated. Allow the user to generate N random nodes, with N entered from the keyboard. Display the contents in a depth first manner to the screen. Then load those nodes into a pqueue based not on the value, but on the frequency. The nodes should be displayed as (value, frequency) pairs. Empty the queue and display them according to the priority criteria.
8. Create a class asteroid (or roid for short) and andomly place them in 3d space. Each has an id number, a mass, and an array of size three that contains the %mass for three important natural resources, these percentages MUST sum to less than 100, and usually are far less, the rest of the mass is considered waste. The average sum is 21% for all asteroids. You can consider each then to have a mean of 21/3 or 7% with a standard deviation of 4. No percentage can be negative. These asteroids lay in a ring of radius 50 from a center of rotation (our star). Their radius from the ring has a mean of 8 and a standard deviation of 5. They are uniformly distributed along the ring (0 to 2PI) AND from the ring. No two asteroids can exist in the same location as any other. Allow the user to enter N, the number of asteroids, generate all the values, display the data to the screen, then create a 3d gnuplot of this ring of asteroids.
Radius 8
Radius 50
9. Imagine we are far in the future, we are mining asteroids from problem 8 above, for natural resources. To achieve this we have created a suite of bots. Survey bots (SB), mining bots (MB) and transport bots (TB). Create a class asteroid (or roid for short). You are to create a list of queues of these bots. A queue for each type of bot. Each bot as a unique identifier (int). Allow the user to enter just how many of each kind is to be created. These bots function as follows: Given a list of asteroids The survey bots begin to search through random asteroids, if they find an asteroid whose sum is greater than 15, they send a message to the next available mining bot. The mining bot will travel there (instaneously for this project) and begin operations. When a number of time steps equal to the percent sum is over, the mining bot returns to the queue to wait for its next assignment. A transport bot is dispatched to pick up the resources. This is a time stepping simulation, controlled by the user, you need only print to the screen when bots are doing something, a run time sample follows:
How many asteroids? 100
How many survey? 3
How many mining? 6
How many transport? 2
Ready:
Survey bots 1, 2, 3 dispatched
Time 1:
SB1 searching asteroid 55
SB2 searching asteroid 27
SB3 searching asteroid 60
Time 2:
SB1 searching asteroid 4
SB1 resources found, sum = 18
MB1 dispatched to asteroid 4
SB2 searching asteroid 9
SB3 searching asteroid 100
Time 3:
…..etc…
Time 18:
MB1 finished at asteroid 4
MB1 returns to queue
TB1 dispatched to asteroid 4
SB1 searching asteroid 89
….etc….
10. You are to modify your canyon project in the following way. You are to start with the top of the canyon at 100 as before, the river is still random but narrow (width 1) at y = 99, create the canyon. Save to png. Lower the riverbed by 5 to y=95, widen the river by 1. Rivers can change course +1/-1 with each iteration. RE-Generate the canyon. Repeat for 19 time steps. Create an animated gif of these png files, this is to illustrate erosion over centuries. Redefine the window if necessary.
11. Cell phone data is accumulated through COP, the civilian observation program, 24-7. The government forces all cell communications to be forwarded through communication hubs in Central America so no warrant is required. (If you send me a text message, the request is forwarded through those sites so they can listen in without committing a felony.) Create a simulation that consists of 1) a list of communication nodes that are sender/receivers (These are our cell phones). Randomly choose a number of nodes and mark them with a bool AGENT as true, all others are false. THEN randomly choose source and destination nodes from that list, display that pair, and if at least one of the two nodes is AGENT=true, add that data pair to a multimap of those ids. This is the NSA listening to us. If there are 500 nodes in the initial list, Display how many data pairs must be generated until ALL nodes with the bool AGENT=true is mapped? (Who talks to them is not important, only that they are contacted). Then Display all the communications to the AGENT nodes, who they are to and who they are from. All other communications can be ignored.
12. If you do questions 8 and 9 and make it an animation showing the bot movements this will count as buy 2 get 3 answers.