Description
Learning Goals:
• Review of the Sequential, Associated, and Unordered data structures
• Review and practice using the STL’s Vector, List, Forward List, Map, and Unordered Map container
interfaces
• Reinforce the similarities and differences between containers
• Review and practice efficiency class identification for the fundamental operations of all the data
structures covered
o O(1), O(log2 n), O(n), and O(n2)
• Reinforce modern C++ object-oriented programming techniques
Description:
In this homework assignment you are to perform 3 tasks:
1. Complete the starter code given, then compile and execute your program
saving the output to a text file. The output will be a table containing the
amount of actual elasped time consumed while performing an operation
(columns) on a container filled with N elements (rows). This is not the
main objective of this assignment, but rather just a required step.
2. Graph the table produced by the program. This too is just a required
step towards the main objective.
3. Analyze and summarize the performance of the same operation across all data structures. This is
the most important objective of the assignment. Explain the information on the graph in terms of
the operation’s efficiency class. Compare and contrast the operations performed on the different
data structures. Be sure to include Big Oh in your explanations. For each operation, provide a
concrete, real-world situation that operation is used and then make a selection of the container
best suited. Explain why you selected the one you did, and why you did not select the others. Your
response should be at least 1 full page (½-inch margins, 10-point Times New Roman font, single
spaced, well-formed grammatically correct sentences, etc.). You may include pictures, tables, and
graphs, but those are in addition to (doesn’t count towards) your 1 full page target. Include your
graph in your analysis report.
You are given main.cpp with sections that need to be completed. This program is unusual in that it does
not solve a particular problem like previous homework assignments, but enables you to demonstrate you
know how to use the STL containers, their interfces, and related iterators. Most of the sections require
only a single line of code. For example, insert a grocery item into a container at verious positions (front,
back, etc). Other sections require a few more lines of code (about 5 or 6). For example, search for a
grocery item with a particular UPC. You’ve done all of this before, so it should be review. Okay, hash
tables (std::unordered_map) may be new but they have an uncanning similarity to binary search trees
(std::map).
Container Review and Analysis Homework Last updated: Tuesday, April 28, 2020
CPSC 131, Data Structures – Spring 2020 Page 2 of 4
Bettens
For example, given the following code fragement that measures the amount of elasped time consumed
inserting an element at the back of an unbounded vector data structure:
{ // 1a: Insert at the back of a vector
std::vector dataStructureUnderTest;
measure( “Vector”, “Insert at the back”, noop, [&]( const GroceryItem & item ) {
///////////////////////// TO-DO (1) //////////////////////////////
/// Write the line of code to push “item” at the back of the data structure under test
/////////////////////// END-TO-DO (1) ////////////////////////////
} );
}
you would write dataStructureUnderTest.push_back( item ); in the space provided.
The main.cpp starter code (your point of departure) compiles and executes out of the box. The table
produced will contain a bunch of zeros because you haven’t added your code yet, and that’s okay. As you
complete a section or two, it’s a good idea to make sure it still compiles and executes. If you are having
difficulties getting a section to work, remove (or comment out) your “bad” code and move on to the next
section. When you have the first round of “easy stuff” finished, cycle back and finish the others. Be sure
to submit a program that both compiles and executes with no errors.
Run time tips:
As discussed all semester, when the container holds just a few elements, the efficiency class difference
between the data struture operations is not very interesting. It’s only when you have large amounts of
data in the container that the differences become very interesting.
In summary, this program measures in microseconds the amount of elapsed (wall-clock) time required to
perform a data strucure’s operation hunderds of thousdands of times, each time slightly changing the
container. For example, it measures the amount of time it takes to insert an element into an empty list,
then the amount of time to insert an element into a list with only one element, and so on until it measures
the amount of time to insert an element into a list with roughly 100,000 elements. Then it repeats for
other operations and other data structures. (1,000 microseconds = 1 millisecond, and 1,000,000
microseconds = 1 second)
This all take a considerable amount of time. Expect your program to take up to 45 to 60 minutes to finish
execution when using the full sample data set (Grocery_UPC_Database_Sample.dat), depending on the
capabilities of your machine. To help you during development, a smaller sample data set
(small_sample_input.dat) is also provided, but may still take a minute or two to complete.
The amount of time it takes your program to run is also influenced by how your program is built. A Debug
build may run 10 times slower than a Release (optimized) build. You may change Build.sh to produce
Release builds by editing Build.sh and changing:
CommonOptions=”-g3 -O0 -pthread -std=c++17 …
to
CommonOptions=”-g0 -O3 -DNDEBUG -pthread -std=c++17 …
Container Review and Analysis Homework Last updated: Tuesday, April 28, 2020
CPSC 131, Data Structures – Spring 2020 Page 3 of 4
Bettens
Size BST/InsertBST/RemoBST/Searc DLL/Insert
0 27 0 0 135
250 21 0 0 0
500 3 0 0 0
750 17 0 0 1
1000 4 8 0 0
1250 7 0 0 1
1500 17 0 0 0
1750 5 0 0 1
Graphing tips:
The program outputs tab seperated values (tsv) text that you redirect to a
text file at the command line. Open this text file in a spreedsheet
program, like Excel. Verify the data is placed in columns with headers and
rows. Next, create a line graph within Excel1 by selecting all the data,
including the header row, and then inserting a new line chart. For
example, if your data looks like the picture shown to the upper right, select
all the cells in the 5 columns and 9 rows.
Then from the Insert Tab on the ribbon, open the Insert Chart dialog and
pick the line chart option as shown to the lower right.
Of course you may generate the graph however you wish, but it should
resemble the graph in the Description above. It’s very likely Google Sheets
and LibeOffice Calc have similar cpabilities. You may also do it by hand and
scan it.
Rules and Constraints:
1. You are to modify only designated TO-DO sections. Do not modify anything outside such designated
areas. Designated TO-DO sections are identified with the following comments:
///////////////////////// TO-DO //////////////////////////////
…
/////////////////////// END-TO-DO ////////////////////////////
Keep these comments and insert your code between them. In this assignment, there are 21 such
sections of code you are being asked to complete. You were given the solution to one of them above.
All of them are in main.cpp.
2. This assignment requires you redirect standard input from a text file and redirect standard output to a
text file. See How to build and execute your programs. To run your program, enter something like one
of the commands below (pick one) at the console:
./project_\(clang++\).exe < Grocery_UPC_Database_Sample.dat | tee output.txt
or
./project_\(g++\).exe < Grocery_UPC_Database_Sample.dat | tee output.txt
or
“./project_(clang++).exe” < Grocery_UPC_Database_Sample.dat | tee output.txt
or
“./project_(g++).exe” < Grocery_UPC_Database_Sample.dat | tee output.txt
or
cat Grocery_UPC_Database_Sample.dat | “./project_(clang++).exe” | tee output.txt
or
cat Grocery_UPC_Database_Sample.dat | “./project_(g++).exe” | tee output.txt
3. Use Build.sh (potentially modified as described above) to compile and link your program – it employs
the correct compile options.
1 Search Google for “Create a line chart in Excel” for more information, how-tos, and videos.
Container Review and Analysis Homework Last updated: Tuesday, April 28, 2020
CPSC 131, Data Structures – Spring 2020 Page 4 of 4
Bettens
Deliverable Artifacts:
Provided files Files to deliver Comments
main.cpp 1. main.cpp Modify the file as described above.
GroceryItem.hpp
Timer.hpp
2. GroceryItem.hpp
3. Timer.hpp
You should not modify these files. The grading
process will overwrite whatever you deliver with
the one provided with this assignment. It is
important that you deliver complete solutions, so
don’t omit these files in your delivery.
GroceryItem.cpp 4. GroceryItem.cpp
You should replace the provided file stubs with
your (potentially) updated files from the previous
assignment.
5. AnalysisReport.pdf Your analysis report document including your
results graph.
6. output.txt
Capture your program’s output to this text file
and include it in your delivery. Failure to deliver
this file indicates you could not get your program
to execute.
small_sample_input.dat
medium_sample_input.dat
Grocery_UPC_Database_Sample.dat
Text files to be used as program input. Do not
modify these files. They’re big and unchanged, so
don’t include it in your delivery. Start with
small_sample_input.dat then
medium_sample_input.dat. Once you have a
working program, use
Grocery_UPC_Database_Sample.dat to generate
your final output from which to graph your
results
sample_output.txt
Sample output of a working program. Use for
reference, your output format may be different.
But the contents should match. Do not include
this file with your delivery.
sample_graph.xlsx Sample Excel file with data loaded and graph
drawn. Do not include this file with your delivery.
