CSE 326 -- FALL 2000 
HOMEWORK ASSIGNMENT #2

DUE:  Friday, Oct 13th

For this homework you will be describing algorithms using pseudocode.
It is not necessary to actually compile and execute the program.
However, your algorithms must still be correct!  Keep in mind these:

-----------------------------------------------------------------
PSEUDOCODE GUIDELINES

(1) Begin with an English description of how the algorithm works.  You
    may want to include examples and diagrams of the data structures
    that help make the operation of the algorithm more clear.  About
    one or two paragraphs of text is usually enough.  Include a
    general overview of the approach and goals.  For recursive
    algorithms it is often useful to clearly describe the base and
    inductive cases that make the algorithm correct.

(2) Follow basic C and/or C++ syntax.  Dynamically created structures
    should be allocated using "new" and deallocated using "delete".
    Avoid the use of advanced C++ features like iterators, templates,
    class inheritance, etc.  Do not rely on pre-defined classes from
    the Weiss book unless that is part of the assignment.

(3) You may simplify your pseudocode by using the name of a structure
    type as an ordinary datatype.  E.g., instead of writing
	struct node { int data ; struct node * next; };
	struct node * MyNodePtr;
    you may write	
	struct node { int data ; node * next; }
	node * MyNodePtr;

(4) You can introduce definitions for the relational operators applied
    to non-numeric types.  For example, you might write
	Define (F < G) for nodes F and G to hold iff (F.data < G.data)
    This should be done only to clarify, never to obscure, the
    presentation.  If you have any questions about whether a definition or
    abbreviation is okay to include check with the TA.

(5) Include meaningful comments in the body of the pseudocode.  

(6) Try to make the program as succinct and elegant as you can.  This
    is not only good style but usually makes the algorithm easier for
    others to understand.

(7) Pseudocode should be typed (preferred) or VERY neatly handprinted.
    If we have difficulty reading your homework you will lose points!

---------------------------------------------------------------------

The following problems will involve linked lists.  Lists are
represented by linked lists of nodes without the use of headers.  In
all problems an empty list is a pointer to NULL.  The general type for
elements of the list is called "object".

The definition of a node is:

	struct node { object data ; node * next; };

(Note that this syntax is okay in pseudocode - see pseudocode
guidelines above.)

#1.  Write an algorithm that splits a list into two lists, each of
     which contains half the elements of the original list.  
     (Or, if the original list is of odd length, one of the new
     lists will be one node longer than the other.)

     Your algorithm should not allocate any new nodes.  Furthermore,
     it should visit each node at most once.

     The items in the new lists need not be contiguous in the old
     list: e.g., the first list need not contain only elements from
     the first half of the old list.

     The declaration for this function is

	void split(node * in, node * & out1, node * & out2)

     Note that the results are returned using the reference parameters
     out1 and out2.

#2.  Write an algorithm that destructively merges two sorted lists
     into one sorted list.  It should not allocate any new nodes.  The
     declaration of the function is

	node * merge(node * in1, node * in2)

     The function returns a pointer to the first element of the new
     list.  It should run in O(n+m) time, where n and m are the
     lengths of the two sorted arrays.

     You may assume that the comparison operators such as "<" are
     defined on things of type object.

#3.  Write a recursive algorithm for sorting lists, using the "mergesort"
     method:

	split the input in two pieces;
	recursively call sort on the first piece;
	recursively call sort on the seond piece;
	merge the two sorted pieces

     The declaration for the algorithm is:

	node * mergesort(node * in)

     and it returns a pointer to the first node of the sorted result.

     Write the T(n) recurrence equation for your algorithm.
     What is the best O() bound?

#4.  Polynomials can be efficiently represented using linked lists
     (see notes from class and Weiss 3.2.7).  The key property of the
     polynomial adt is that each exponent should appear at most once
     in the list, and in order.  (The class notes used an increasing
     order, while Weiss uses a decreasing order).

     Let us call a polynomial with repeated and out of order
     terms a "messy" polynomial, e.g.

	2x^3 + 19x - 17x^3

     Describe an efficient "cleanup" algorithm for converting messy
     polynomials into true polynomials.

     What is the O() running time of your algorithm?  A good solution
     for this problem will run in O(n log n), where n is the number of
     terms in the messy polynomial.  A not-so-good solution will run
     in O(n^2).

     In Weiss 3.2.7 the problem of implementing multiplication of
     polynomials using linked list is described.  How could your
     "cleanup" algorithm be used by such a multiplication algorithm?