Preparation for the Final Exam.
If you print this out, set your font to constant width (e.g. Courier).
Sorry for lousy formatting.
You may not see the possible pitfalls unless you
actually try to implement your solution. It is therefore
advised that you spend some extra time in the lab, even
if you are sure you can write the code when needed.
The code I refer to will be uploaded on Ambassador. Guess what --
I make no claim that it is
a) in really good style
b) bug free
While I cannot do much about the style right now, anyone who spots a bug
(and sends a timely e-mail to report it) gets EXTRA CREDIT :-).
If you haven't implemented the solutions to the practice midterm
problems, consider doing it now.
Quiz 1 and Quiz 4 are also useful for preparation (both now
have solutions on Ambassador in the Solutions folder).
0. Basics of C++: Constructors, Destructors, Overloading,
References, Templates.
I expect you to understand the purpose and the basic properties of
* references ( mostly for passing objects 'by reference' in and
out of functions, see copy contr. )
* copy constructors ( called whenever an object is passed into
or out of a function 'by value'
used in declarations that declare and
initialize an object from another object
of the same type:
X a( 1, 2, 3); // X::X(int,int,int) called
X b = a; // X::X(const X&), the c.c.
X c(a); // and c.c. again
used to manipulate temporaries )
* operator= ( used to copy contents, but not to create objects,
unlike the c.c.
usually guards agains self-assignment:
X& operator= ( const X& other ){
if( this != &other ){
// do stuff ... }
return *this;
}
returns *this to allow multiple assignments )
* this ( available only inside member functions of a class --
it's the pointer to the specific objects who calls
the member, e.g. the overloaded operator= :
X a(1,2,3);
X b(3,4,5);
a = b; //see code above
calls a.operator= (b), b is now 'other' , and
'this' is a pointer (type X*) to a . So smth like
a = a;
makes this == &a true, stuff will not be done )
* default ( needed for smth like X a; or X arr[100];
constuctor will be created automatically unless other
constructors are declared )
* destructors ( called when you use delete explicitly or when a
local variable goes out of scope )
* new and delete ( call constructors and destructors
if you say
X* some_ptr = new X[100]; //array of 100 X's
you must say
delete[] some_ptr; //*not* delete some_ptr;
a) Implement the class Series which reads in a series of numbers from a file
(the length of the series is the first number in the file, hence *not*
known at compile time), stores them and finds sums, averages etc.
A series object must be able to re-read from another file, replacing the
old data with the new (which may be of different length!).
Since the size is not known at compile time, you will have to allocate
memory on free store using new [] (i.e. dynamically) and free it up
with delete[], and keep a pointer to that memory in your class.
Here's a series of doubles:
class Series {
private:
// your stuff
public:
Series( char* filename ); // read a file of the following format:
// length num1 num2 num3 ...
~Series();
void read_file( char* filename ); // read file and replace data
int size(); // get the length of the series
double sum();
double average();
//..
};
The following must work (correctly):
Series A( "data-1.dat" );
Series B( "data-2.dat" );
Series C( A ); //C get a copy of A's data
cout << A.size() << " " << A.sum() << "\n"; //for data-1.dat
cout << B.size() << " " << B.sum() << "\n"; //for data-2.dat
B = A; //B gets a copy of A's data, loses its
//own, which gets removed from memory
A.read_file( "data-3.dat" ); //A's old data replaced and discarded
cout << B.size() << " " << B.sum() << "\n"; //they print the same
cout << C.size() << " " << C.sum() << "\n"; //numbers as the 1st cout,
//i.e. for data-1.dat
cout << A.size() << " " << A.sum() << "\n"; //prints new stuff for
// data-3.dat
A = A; //should not move any data -- self-assignment
B = C = A; //everyone gets data-3 now
Clearly, this code requires non-default copy constructor and operator= .
What happens if these are not specified (i.e. the automatically generated
defaults are used?)
Put some messages in your constructors and operators, or step through
your code in the debugger so that you know what gets called and when.
b) Write an overloaded operator[] so that cout << A[2]; prints the third
number in the series and A[2] = 100; resets it to 100 .
c) Write an overloaded operator< which compares series lexicographically
(that is,
{ 20 30 10 40 } < { 21 90 }
{ 21 30 10 40 } < { 21 30 10 90 }
{ 10 11 12 13 } < { 11 }
{ 10 11 12 13 } < { 10 11 12 14 }
{ 10 11 12 13 } < { 10 11 12 13 14 } etc,
i.e. compare the first entries, if they are equal compare the next pair
and so on. Whoever has a smaller number on the first step when the
entries are different loses.)
d) Now make your class a template class, so that you can declare
Series, Series and Series (the latter
is the most interesting -- what is the sum of two strings? You
can add play around with this, if you have time. See Sec. 7.3
pp. 130-137 of the text.)
e) Discuss the following "code":
class Musor{ ... };
void foo() { new Musor(0); }
f) Sort an STL list by any method (bubble-sort will do).
Sort an STL list of any for which T::operator< is defined.
1. Binary Search Trees -- see the BST dictionary on Ambassador
This is an implementation of a binary tree of strings (the string
type in C++ has operator< defined). It is used to implement
a dictionary. I count and print out the list of all different
words in "Alice in Wonderland". In the following exercises
you can use the dictionary tree constructed by that code.
Write recursive functions to
a) count the number of leaves in the tree (about 5
lines o'code for the function body)
b) find the "deepest" word in the tree (i.e the word(s)
with the longest path leading to them from the root)
c*) write a function to delete a word from the tree. The resulting
tree must remain a proper BST, that is, the order should be
preserved at all nodes. When you delete a non-leaf node,
you have to re-attach its left and right subtrees. Let's say
the node you deleted was a right child, then its right subtree
can be re-attached at the place of the deleted node (why?).
As for the left subtree, you have to find a proper place for it.
Design and code the algorithm (see also Sec. 12.6, pp. 287-288 of the text)
d) On paper: draw a random binary tree and perform pre-order,
post-order, in-order and level-order traversals. Which one
will give you a completely ordered sequence of values in case
of a BST?
2. Priority Queues
Under a priority queue we understand a data structure (a collection of elements
of some type for which operator< is defined) that supports the following
operations:
* push // add an element to the collection
* top // return the _largest_ element in the collection
* pop // remove the _largest_ element from the collection
This definition can be changed to returning and popping the _smallest_ element
instead. A priority queue is an _abstract data type_, i.e. we don't
want to care how it's implemented. Usually a heap is used.
a) Implement a priority queue of ints on top of a list or vector.
This is going to be an inefficient but simple implementation. You will
have to do some sorting on every push and/or pop.
Test your code by pushing random integers into your priority queue and
then poping them off. They should come out in decreasing order.
b) Recall the extra-credit problem:
Print, in increasing order, all natural numbers <= N
such that their only prime divisors are 2, 3, and 5 (i.e. all
numbers one can get by multiplying together a certain number
of 2s, 3s, and 5s). Here's the beginning of this sequence:
2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, ...
Read the buggy solution in pqueue-example and fix it. Here's the text:
const int N = 100; //Buggy solution. Fix it.
main(){
priority_queue, greater > PQ;
int x = 1;
while( x <= N ){
PQ.push( x*2 );
PQ.push( x*3 );
PQ.push( x*5 );
x = PQ.top();
cout << x << " ";
PQ.pop();
}
cout << " finished.\n";
}
3. Heaps and HeapSort -- see Heap on ambassador and
read Sec. 15.2 pp. 362-369.
a) Make my heapsort in Heap into a template, so that it can
heap-sort a vector of any type for which operator< is defined.
Specifically, make it work for an array of strings (for
strings operator< is defined as lexicographic, the same
order you see in a dictionary).
b) On paper: Take an array of random ints and
-- make a heap out of it, as per heapsort algorithm
-- apply adjust_heap repeatedly as per heapsort algorithm
to make the heap you've got into an ordered array
4. Hash functions -- Read Sec. 17 (you may skip 17.4, but read 17.6)
a) Do Ex. 1, 4, 5, 6
b) Look at the hash-test code. If we were doing a full-scale implementation
of a hash table for strings (in this case, all different words found in
"Alice in Wonderland" plus some fake words as a result of my lousy parsing),
our hash_array would contain a word or a list of words whose indexes into
hash_array (calculated by hash_function) collide. In this example, we
simply count the number of collisions and print a histogram.
The file word_list contains approx 2,600 words. Experiment with different
sizes of HASH_BASE to see how it affects the number of collisions.
Take HASH_BASE = 1009 or 997 and then take HASH_BASE = 1024. Can you
explain the difference? Look at the number of 0's in the hash_array - these
entries were not hit by any word.
Write your own hash_functions as described in 17.6 ( pp. 423-424 ).
Compare them with mine. Then look in hash_function.h in STL sources to
see their hash function for strings. Their code for hashing a 'string s'
looks like
long h = 0;
for(int i=0; i > list_of_vertex;
typedef vector< list_of_vertex,
allocator > vector_of_list_of_vertex;
That way if you declare vector_of_list_of_vertex edge_list; and fill
it in properly, then edge_list[2] will be a list_of_vertex, the list of
vertices you can get to by going along one edge from vertex 2 .
Read in an adjacency matrix and print nicelythe resulting edge list.
Note: the type vertex is simply aliased to int. If you want your vertex to
be a more complicated struct, don't forget to add the macro
__MSL_FIX_ITERATORS__ (vertex);
after your defnition of struct vertex { ... };
b) Using either the existing matrix representation of a graph or your edge list
represenattion, implement the depth-first and breadth-first traversals
(see Sec. 19.3.1, pp. 453-455) If you decide to use the adjacency matrix
representation, you will have to find all the neighbors of a a vertex v
by something like this:
graph gr( "your_data_file.dat" );
vertex v = 2; //vertex is just an int
// find all neighbors of v
for( int i=0; i < gr.size() ; i++){
if ( gr.are_connected( v, i ) ) // edge v --> i exists, process it
cout << "edge " << v << " --> " << i << " found\n"; //etc.
}
c) Construct the minimal spanning tree for the weighted graph on p. 456 using
Kruskal's algortihm (you can wait for my handout on Thursday to do this).
d) Dijkstra's algorithm finds the costs (distances, total weights) of the
minimal paths from the source to any vertex, BUT, what are these paths?
Modify the code for Dijkstra's algorithm to keep track of the actual
shortest paths so that a shortest path to a given target vertex can
be recovered after the algorithm has finished.
Hint: Keep track of the predecessors along shortest paths, as in Floyd's.