Due Thursday, 02 April 2009


CPSC 223b   Homework #N2   Lists, Stacks, Queues, and Such
 
Algorithms may be stated in any language understood by a reasonably intelligent
being with common sense but no problem-specific knowledge (code must be very
well commented).  Solutions are due IN CLASS, not in my mailbox, ... .

REMINDER (The Gilligan's Island Rule):  When discussing an assignment (either
programming or nonprogramming) with other students, you may write on a board or
a piece of paper, but you may not take any written or electronic record away
from the discussion.  Moreover, you must engage in a full hour of mind-numbing
activity (such as watching back-to-back episodes of Gilligan's Island) before
you work on the assignment again.  This will ensure that you can reconstruct
what you learned from the discussion, by yourself, using your own brain.


P1. (10 points) The ordered, singly-linked list with one element per node is
    a classic data structure.  But when there are N elements in the list, the
    worst-case time for search, insertion, or deletion is N + O(1) comparisons.

    To improve this performance, we could use an ordered, singly-linked list of
    arrays with the following properties:

    A) Each node of the linked list is a structure of the form

	 struct node {
	     int nitems;
	     KEY key[M];
	     VALUE value[M];
	     struct node *next;
	 }

       where M is some integer constant.

    B) (KEY,VALUE) pairs are stored in strictly increasing KEY order within each
       node, and every KEY stored in a node is less than every KEY stored in
       the following node.

    C) The number nitems of KEYs stored in a node satisfies M/2 <= nitems <= M,
       unless there are fewer than M/2 entries in the entire table, in which
       case all KEYs are stored in the same node.

    Sketch algorithms for

    * searching for a (KEY,VALUE) pair given the KEY

    * inserting a (KEY,VALUE) pair

    * deleting a (KEY,VALUE) pair given the KEY

    in this data structure.  Your algorithms should take advantage of both the
    speed of binary search in an ordered array and the ease of insertion and
    deletion in a linked list.  For simplicity you may ignore the case where
    there are fewer than M/2 entries in the table either before or after the
    operation, and may assume that the keys are unique.

    Bound the worst-case performance of your algorithms (as a function of M
    and the total number N of items in the list) for search, insertion, and
    deletion.  You may assume that N is much larger than M and may ignore O(1)
    terms.  What role does Property C play in these bounds?


P2. (5 points) You are given a set S with N list nodes.  Each node contains a
    link that points either to the node itself or to some other node in the
    set (i.e., none of the links are NULL).  Thus if you start at any given
    node and follow these links, you will ultimately return to SOME node that
    you have already visited and you will cycle thereafter.

    Describe an algorithm that, given pointers X and Y to nodes in the set,
    determines whether or not following links beginning with X and with Y will
    lead to the SAME ultimate cycle.  Your algorithm may not modify any nodes
    in the set or use more than O(1) extra storage (which limits the depth of
    recursion as well).  Explain why your algorithm works as well as how, and
    give its complexity in terms of N (a recurrence relation will suffice).

    Note:  Efficiency is not important; and the complexity can be a worst-case
     bound (or a recurrence for such a bound).  Two-point deduction for using
     the number of nodes in S in your algorithm.


P3. (5 points) Consider a queue ADT that supports the operations addQ(),
    removeQ(), and isEmptyQ().  Describe an implementation of this ADT that
    stores its data using two instances of a stack ADT whose operations are
    pushS(), popS(), and isEmptyS().  Your implementation must be efficient
    in the sense that it uses at most O(N) stack operations for any set of
    N queue operations that starts with an empty queue.  Explain why it has
    this property.


P4. (5 points) Describe a data structure that supports the basic stack
    operations (pop(), push(), isEmpty()) and an additional operation
    findMin(), which returns the value of the smallest element stored in the
    stack WITHOUT deleting that element.  All operations should run in O(1)
    time.

    Note:  The problem describes the interface (i.e., what each operation
    does).  You need to describe how to implement this data structure so that
    each operation runs in O(1) time, assuming that malloc() and free() take
    time O(1), but that realloc() takes time O(MIN), where MIN is the smaller
    of the two block sizes.

    Hint:  What extra information can you keep to achieve this purpose?


P5. (1 point) How much time did you spend doing the first four problems?

								CS-223-03/23/09