CS 32, Fall 2017
Programming Assignment 1
Due: Monday October 30, 11:59pm
Worth: 100 points
PA1 can be done either in two-people teams or individually.
If you are working with a partner, don't just split up the work! Pair programming means working
together to solve each of the problems: trust us that it will work more smoothly for you if you do
it like that anyway. Also be sure that both partners' names are in a comment
at the top of each source code file, and that you properly form a group for this project
in the submit.cs system.
- Download and edit graph.h and its implementation file,
graph.cpp, to solve the problem described in
Chapter 15 Programming Project 1 (pp. 778-779) of the Data Structures textbook by
Main and Savitch. Read the discussion provided by the textbook authors, and you may
use their suggestions in your solution, but be sure to follow the specific instructions on this
web page.
- Type your name(s) and the date in a comment at the top of both files.
[Like always, whether or not we remind you!]
- Study the parts that are already done in both graph.h and graph.cpp. Also read
sections 15.1 and 15.2 of that textbook to fully understand the existing graph definition
and implementation.
- Change the private member variables of class graph as suggested on page 779 of the text,
and eliminate the MAXIMUM constant from the class definition.
- Some other changes you'll need to make to graph.h:
- Implement all of the new functions in graph.cpp. Also verify that the other
functions still work properly with your new class definition. Here are some things to
consider:
- Compile and test your program at CSIL (by connecting remotely is okay). We strongly suggest you
create your own test program, so that you can individually test each of your functions. When you
are ready for more comprehensive tests, you may try out the non-interactive test program that we will
use to grade your project, graphexam.cpp. Compile it as follows (and
heed any warning messages):
g++ -o graphexam -Wall graphexam.cpp
Give a test number, 1 to 5, as a command line argument when you run it. For example,
the following command will execute test number 3:
./graphexam 3
We prefer that you do not proceed to the next step to submit your work until you are sure that all of your
functions are working properly.
- You will turn in both graph.h and graph.cpp.
From our class page at https://submit.cs.ucsb.edu/,
click the "Make Submission" button next to PA1, or use the following command from a CS terminal:
~submit/submit -p 861 graph.cpp graph.h
Be sure to wait for the results of all tests. If you score 100/100, and you've
followed all of the other rules, then you'll earn full credit.
Prepared 10/11/2017 by Michael Costanzo
Special thanks to Michael Main, University of Colorado, creator of many parts of this project.