Midterm 1 Solution

CS23

1. Short Answer Problems. Each of the problems is worth 35 points. Please provide a complete, concise answer to each of the following questions.
   1. Write pre-conditions, post-conditions, and a loop invariant for the following function. Before you can do these things, you must determine what the function does.

      int f(int a[], int l)
      {
         int i;
         int m;
      
         for (m = 0, i = 0; i < l; i++)
            if (a[i] < a[m])
               m = i;
      
         return a[m];
      }
      

      Pre-condition: a is an int array with l elements.

      Post-condition: f() returns the smallest value in a.

      Invariant: a[m] is the smallest value in a[0] through a[i - 1].

   2. Compare and contrast modular programming and object-oriented programming. Be sure to discuss the notion of an abstract data type in your answer.

      Sketch: Modular programming uses a control abstraction and is a top-down style. Very difficult to achieve meaningful data hiding.

      Object-oriented programming is a bottom-up approach that uses data abstraction: data has strictly defined operations which can be performed and data can only be modified through this narrow interface. The implementation is completely hidden.

   3. Discuss and relate the ideas of ``The efficiency/inefficiency of recursion'' and ``A good solution is one which minimizes the cost over all applicable phases of the life cycle.''

      Sketch: recursion certainly uses more memory than an iterative solution (for the stack frames). It is time efficient for some things (raising an integer to a power, binary search) and very time inefficient for other things (Fibonacci sequence, Towers of Hanoi).

2. Programming Problems. Each of the problems is worth 35 points. You are more likely to receive partial credit if you write your code so that I can understand what you've done.
   1. Here are some elements for a pointer-based, singly-linked list:

      struct listItem
      {
         listItem* next;
         int value;
      };
      
      typedef listItem* list;
      

      Write a function which takes as arguments two ascending sorted linked lists and merges them to create a single ascending sorted linked list. The two original lists should no longer exist after this operation. Here is the function prototype:

      list* SortedMerge(list& a, list& b);
      

      Note that the return type is a small typo.

      // a and b are reference parameters so that we can empty them out.
      
      list SortedMerge(list& a, list&b)
      {
         list merged;   // Points to beginning of merged list.
         list temp;     // Points to end of merged list.
      
         // Get the merged list started.
         if (a == NULL && b == NULL)   // Nothing to do.
            return NULL;
         // b has smallest value.
         else if (a != NULL && b != NULL && b->value < a->value
                  || a == NULL)
         {
            merged = b;
            b = b->next;
         }
         else   // a has smallest value.
         {
            merged = a;
            a = a->next;
         }
         temp = merged;
         temp->next = NULL;
      
         while (a != NULL && b!= NULL)   // Compare first item of each list.
         {
            if (a->value < b->value)
            {
               temp->next = a;
               a = a->next;
            }
            else
            {
               temp->next = b;
               b = b->next;
            }
            temp = temp->next;
            temp->next = NULL;
         }
      
         if (a != NULL)   // Append remainder of a to merged list.
         {
            temp->next = a;
            a = NULL;   // a is now empty.
         }
         else   // Append remainder of b and empty.
         {
            temp->next = b;
            b = NULL;
         }
      
         return merged;
      }
      

   2. Design a stack class using an array implementation. The twist is that the array size is determined at run time. The stack will hold integers. Here are the public functions you should implement:
      1. The constructor --- will take the maximum size of the stack as an argument, and dynamically create the stack array. The stack is initially empty.
      2. The destructor --- will destroy the stack array.
      3. Push --- will take an integer argument and push that value onto the top of the stack, if there is room. If there is no room, terminate.
      4. Pop --- will remove the top of stack item from the stack and return its value. If the stack is empty, terminate
      5. Empty --- return 1 if the stack is empty, otherwise return 0.
      6. Full -- return 1 if the stack is full, otherwise return 0.
      If you don't understand what a stack is, a push is an insertion onto the end of a list and a pop is a deletion from the end of a list. A stack is merely a special type of a list.

      class Stack
      {
         int *s;
         int len;
         int top;
      
       public:
         Stack(int length);
         ~Stack();
         void Push(int val);
         int Pop(void);
         inline int Empty(void) { return top == 0; }
         inline int Full(void)  { return top == len; }
      };
      
      Stack::Stack(int length)
      {
         assert (length > 0);
         s = new int[length];
         assert (s != NULL);
         len = length;
         top = 0;
      }
      
      Stack::~Stack()
      {
         delete [] s;
         s = NULL;
      }
      
      void Stack::Push(int val)
      {
         assert (!Full());
         s[top++] = val;
      }
      
      int Stack::Pop(void)
      {
         assert (!Empty());
         return s[--top];
      }