CS206 Sample Problems for Midterm Examination
Pfs. Dougherty & Wonnacott				Spring 2005


1) Given the following axioms about lists, use "equational reasoning"
   (i.e., substitution) to show statements a) and b) are true for any
   items X and Y and list L.  For each substitution you perform,
   write down the number of the axiom you used:

class list {
public:
        // A list can be one of two things
        //   * an empty list, created with   list()
        //   * a head element and a sublist, list(h, l)
        list();
        list(const item & head, const list & rest);

        // Given a list, we can ask if it is empty,
        // or retrieve its head or the sublist part:
        friend bool empty(const list & l);
        // axioms:
        // 1.   empty(list())     === true
        // 2.   empty(list(h, r)) === false

        friend item head(const list & l);
        // precondition: list is not empty
        // axioms:
        // 3.   head(list(h, r)) === h

        friend list rest(const list & l);
        // precondition: list is not empty
        // axioms:
        // 4.   rest(list(h, r)) === r

 a) empty(rest(list(X, list())))  ==  true

 b) empty(rest(list(X, list(Y, L)))) == false

 c) Provide axioms for the method concat(l1, l2) - 
	a single list containing l1 then l2.

 d) Provide axioms for the method reverse(l) - 
	a backwards copy of l.

 e) Provide axioms for the method palindrome(l) - 
	true iff l is the same forwards or backwards.

 f) Provide axioms for the method tail(l) - 
	which returns the last item in list l.

 g) Provide alternative axioms for the method palindrome(l) 
	using tail(l)


2) Write axioms for a "swap_pairs" function that swaps adjacent pairs
   of elements in a list -- for example, the list 1 2 3 4 5 6 7 8
   should become 2 1 4 3 6 5 8 7 (the last element in a list of odd
   length can be left alone).

   Prove that swap_pairs(swap_pairs(L)) == L	for any list L.


3) Analyze the complexity of the following program, in terms of N,
   assuming that compute(i,j) always takes 1 time step.

   void test(int N)
   {
     for (int i=0; i<N; i++)		// loop 1
     {
       for (int j=i; j<N; j++)		// loop 2
         compute(i,j);

       for (int j=i; j<N+i; j++)	// loop 3
         compute(i,j);
     }
   }

 a) Give a simple function that is about and "proportional to" the
    number of calls to "compute" (using Sedgewick's definition of
    about and "proportional to").

 b) What is the O() bound on this function?


4) Consider the problem of representing "graphs" (sets of numbered
   nodes, some of which are connected), as in the union-find,
   or partitioning problem found in chapter 1 of Sedgewick's text.
   Suppose that we wish to produce a representation that lets us
   efficiently compute the number of edges involving a given node
   (that is, we need an efficient "neighbors" operation below).  For
   example, if G is a graph with 4 nodes (numbered 0 to 3), and three
   edges, between 0 and 2, between 2 and 3, and between 1 and 0, then
   neigbors(G, 0) == neigbors(G, 2) == 2 and neigbors(G, 1) ==
   neigbors(G, 3) == 1.

class graph {   			// a graph with N nodes
public:
        graph(int N);
        // Create a graph for a set of N items
        // precondition:  N>=0

        graph(const graph &p, int i, int j);
        // Produce a graph that is identical to p, 
	// 	but i and j are connected
        // precondition: 0 <= i, j < set_size(p)

        friend int neighbors(const graph &p, int x);
        // return the number of neighbors of x
        // precondition:  true
        // axioms:
        //      neighbors(graph(N), x)
        //          === 0
        //      neighbors(graph(P, i, j), x)
        //          === neighbors(P, x) + 1, if x==i or x==j,
	//	    === neighbors(P, x), otherwise

a) First, suppose we represent a graph with a list of all edges.
   For example, the graph G above would be represented by the
   list ( (0,2), (2,3), (1,0) ).

   What are the complexities of each of the three operations (assuming
   that all list operations take O(1) time?

b) A better representation for this problem is to keep N vectors, so
   that the ith vector shows the "other end" of each edge involving i.
   For example, G above would have 1 and 2 in vector #0, 0 in vector
   #1, 0 and 3 in vector #2, and 2 in vector #3.  For this
   representation, give:

     i) The private section

    ii) An abstraction function

   iii) A representation invariant

    iv) The complexities of each operation

You are not required to actually write the functions to implement this
class, but you may do so if it will help you produce your answers.


5) Consider the following class definition:

class my_string
{
 public:
	my_string();		// primitive constructor

	// extend a string with a new initial character
	my_string(char c, my_string s);

	// return the number of characters in the string
	friend int size(my_string s);
	// axioms:

	// get the first character in a string
	friend char initial(my_string s);
	// precondition: size(s) > 0
	// axioms:
	//  initial(my_string(c, s)) === c

	// get the remainder of the string
	friend my_string others(my_string s)
	// precondition: size(s) > 0
	// axioms:
	//  others(my_string(c, s)) === s

	// predicate if a character is in a given string
	friend bool contains(my_string s, char x);
	// axioms:

 private:
};

 a) Complete the axioms for the functions "size()" and "contains()"
    above -- include any needed preconditions.

 b) Evaluate the following expressions using equational reasoning (be
    careful, some may only be conditionally true):

 c) Onto the initial class representation ...

	 private:
		vector<char> characters;	// vector of characters
		int charcount;			// count of characters
	};

Provide the representation invariant and an abstraction function for
this initial representation of the abstract class my_string -- use comments if
your notation is not clear, but endeavor to be clear from the start.

d) an alternative representation ...

	 private:
		list<char> characters;
	};

Provide the representation invariant and an abstraction function for
this second representation of the abstract class my_string -- use comments if
your notation is not clear, but endeavor to be clear from the start.


6) Consider the list operations below:

	list l = list("manny", list("moe", list("jack", list())));
	list r = rest(l);
	list m = remove_head(r);	// delete initial item in list r
	cout << l << endl;	// assume operator<< is defined for lists

 a.)	what list is displayed using value semantics (i.e., deep copy)?

 b.)	what list is displayed using reference semantics (i.e., shallow copy)?