Last Modified: Fri Dec 10 16:53:52 EST 2004
|
C M S C 2 1 4 C o m p u t e r S c i e n c e II F a l l 2 0 0 4 |
Probably - in particular if you store this Lab (or whatever) in a map then it might be NECESSARY to write the < operator and/or other comparison operators (like == or != or <=).
Yes - you should write a .h (header) file for prim.cpp and it should contain at least the prototype for "computeMST". Also if you have any "local" helping functions in the prim.cpp file then you may encounter some compiler errors (multiply defined things) - if this is the case you should remove those helping functions (the only time this is a problem is if they are non-template functions) and/or more those helping functions into another file (this is a little bit messy but necessary due to some cxx "magic" template issues).
MORE THAN LIKELY - the problem is that you have a CONST object and are calling a NON-const member function - you have TWO main options:
The extra credit details are posted via the main projects webpage at the following link:
http://www.cs.umd.edu/class/fall2004/cmsc214/Projects/P5/p5.extra.htmlNOTE: there is no "description" of Dijkstra's algorithm and you must refer to your course notes for how to implement it. Do NOT try to do a "brute force" search for the cheapest path - algorithms that do so will recieve NO EXTRA CREDIT AND MAY RECIEVE A DEDUCTION.
It was originally a mistake (off by 2), but will stand - MEANING project #5 is now due on FRIDAY, December 10th by 11pm for ontime and then can be submitted as late as 11pm on SUNDAY, December 12th (by 11pm) for up to 2 days late penalty. Project #4 final deadline will also be SUNDAY, December 12th by 11pm.
There won't be a "bonus" for turning in project #5 "early" (but you can use the extra time to complete the recently posted extra credit).
In general no. In particular this is a more "open ended" project and not everything is explicitly specified (although most is to some degree). SO, re-read the project description to see if an answer is available there and then if there is not enough information or potentially conflicting information make the best possible decision you can with the information given and hope for the best.
Is this an acceptable policy? Most definitely - many times you are going to be provided with little to no information let alone step by step detailed instructions - and thus it will be your responsibility to make educated choices as to how to proceed - sometimes you'll make good ones, sometimes not - for a project that may mean you do well (recieve a good grade) and sometimes do not so well (lose some points for a bad decision or an omission or ...). Chances are you won't lose much credit (if any) for "bad decisions" (related to unspecified items) on this project.
Chances are that you're trying to use the [ ] operator on the map - the problem is that the map class doesn't appear to have written a CONST version of the [ ] operator - this is a shortcoming of the map class (generally the [ ] operator can be overloaded with a const version and a non-const version - this allows the most flexible use of it).
So what alternatives are there? This is another good exercise in looking for ALTERNATE ways to solve a problem. Unfortunately without changing the map class (which is not possible) or abandoning the map class all together most solutions are not "efficient" - however this is what we'll have to work with.
ONE possible solution is to make a NON-CONST COPY of the map in question and then do your work on that non-const version. This is inefficient because you're making an unnecessary copy of a potentially very large object - BUT you only have to do this ONCE (or very rarely) and thus it is an acceptable solution for our purposes. NOTE: this probably will not solve the problem completely but it should help lead to an acceptable solution.
No. You do have to USE each of those STL classes at some point in time with your Graph class - however the data member adjacency_list MUST be a vector of lists (thus you have used those two) and the function(s) that return a map qualify as having "used" the map class - thus that completes this requirement.
To re-clarify - you do NOT have to have a DATA MEMBER of type vector, list and map - you just have to USE those three STL classes at some point in time.
See the section of the project titled "HINTS" (down near the bottom). In particular the 6th hint discusses how to "fix" this problem.
Note that there are usually (almost ALWAYS) several ways to do something and if one way doesn't work try another. In particular when overloading an operator it can generally be done as a member function or as a friend function or as a non-member non-friend function and in this case the first two options do not work "easily" however the third way works fine - DON'T FORGET that this function should be a TEMPLATE.
This is a good exercise in thinking about ALTERNATE ways to solve a problem - the more a person is able to do this the better they will be at solving problems in general.
The official extra credit information isn't ready to post yet, but for the most part it is just to implement Dijkstra's algorithm to find the cheapest path from vertex A to vertex B in the graph. More specific details will be posted, but if you do the following function:
vector dijkstra(graph,vertex a,vertex b,bool = false);in a file called "dijkstra.cpp" (with a corresponding dijkstra.h file) then that will be the majority of the extra credit. Note that the return type is a vector which will be the actual path found from a to b (with a in position 0 and b in the last position of the vector). The graph passed in is the graph to run dijkstra's on (it should be passed by const reference) the two vertex's are the verticies to start and end at and the boolean is generally set to false but when set to true means the function should output "DEBUGGING" information (to be clarified soon). If no path from a to b is found then an empty vector is returned.
Ah, this is not because it won't let you use it, you just need to specify that it is part of the std:: namespace so if you do the following in your header file:
#ifndef WHATEVER_H
#define WHATEVER_H
#include <vector>
template <class DataType>
class FOO {
...
private:
vector<DataType> v1; // compiler error here
};
#endif
This will not compile (if it does you have some problems with one or
more of your header files having a "using" statement in them or in your
.cpp file you have a "using" statement before your #include statements
- WHICH YOU GENERALLY SHOULD NOT HAVE - see the tutorial on the class
webpage about
namespaces
and how they generally work and when you should use "using" statements
and when you should not.
To fix the problem above in the header file, just add "std::" in front of the vector as follows:
std::vector<DataType> v1;
and you will have to do this for most any STL class and items you use
(in your header files) from the "system libraries".
This is an "odd error" and occurs when you try to do something like the following:
template <class Data>
int function( const vector<Data> v1, const Data &x ) {
int count = 0;
vector<Data>::const_iterator it; // this line does not compile
for ( it = v1.begin(); it != v1.end(); it++ )
if ( *it == x ) ++count;
return count;
}
The function above is written almost 100% correctly - unfortunately,
iterators are handled a bit differently and the one line:
vector<Data>::const_iterator it;
needs to be modified as follows:
typename vector<Data>::const_iterator it;
in particular the keyword "typename" must be placed in front of
the vector<Data>::iterator (or const_iterator or reverse_iterator
or most any type of iterator) BUT THIS IS ONLY NEEDED when you are
trying to create an iterator of an STL class with a generic template
type like above (with "Data") - if you use a "real type" (like int)
then the keyword "typename" is optional.
It turns out that many textbooks do not discuss this part of the STL class or do so incorrectly or avoid the whole problem by avoiding the use of iterators - for example:
int size = v1.size();
for ( int i = 0; i < size; i++ )
if ( v1[i] == x ) ++count;
So this is another example of how one little loop (to sum up how many
times item x appears in the vector) can be done in many different ways.
It is recommended you try to use iterators when processing vectors and
other STL classes (as it is good practice and you are expected in general
to know how they work - aka how to use them).
SIDE NOTE: The textbook "The C++ Programming Language" written by Bjarne Stroustrup is perhaps the best textbook as an "official" reference for the C++ language (since Bjarne Stroustrup created the C++ language) - note however that it is not a "user-friendly" textbook (meaning it is harder to follow/read than most other textbooks - but where the solution to the problem above was found).
Yes. More details about the extra credit will be posted here by next week (at least one full week before this project is due).
Project #5 is due by 11PM on Wednesday, December 8th, 2004. Note: any project may be turned in late up to 2 days as specified on the class syllabus. For details regarding the late policy and any penalties associated with submitting late projects please see the class syllabus.
|
See the class syllabus for policies concerning email Last Modified: Fri Dec 10 16:53:52 EST 2004 |
|
|
|
|
|