EEN511 Test, 11th March 2004

E-mail solutions to me (stephen@rabbit.eng.miami.edu), in HTML format. That way you can add pictures if you want, and make things stand out with colours and font sizes. Do not use pale colours in your answers; I will print paper copies for grading on a black and white printer. Of course, I will look at it on a normal monitor first, but everything must be visible when printed.

Include your NAME and STUDENT NUMBER at the beginning.

1
With reference to a working implementation of Heap-Sort, show clearly and unarguably that its running time really is O(n莛og₂n) and that its additional memory requirement is O(n).

"With reference to a working implementation" means that you should have a working implementation, include it in your answer, and refer to it in the explanation.

Showing something "unarguably" does not require a formal mathematical proof. It requires a well-reasoned argument that would leave an intelligent person with no doubt of the truth of the assertion. You should not leave this intelligent person to realise or discover anything for him/her/itself, but you do not need to demonstrate that 2+2 is 4.

2
Write a function that sorts a linked list. It should not "cheat" by transferring the linked list to an array and sorting that! It should not use any extra memory unnecessarily. It should be reasonably efficient, but I will be happy with O(n²) solutions.

3
Carefully examine the following program. It is testing the implementation of a strange type of string object. This special kind of string is stored both forwards and backwards. Who knows why? Don't worry about the reasons.

Something very odd happens when it is run on some computers. Work out what happens, why it happens, and how to prevent it.

It is NOT cheating to try out experiments on a computer, but the effects are machine-dependent. The compiler on rabbit tries very hard to hide the problem. The Microsoft compiler exhibits the problem very clearly. This is not a fault with the Microsoft compiler; it is behaving correctly; there really is something wrong, a logical flaw, in this program.

Extra credit: The last assignment "a=a;" may seem rather unnatural. Who would ever waste time assigning a variable to itself. However, there is a situation in which that sort of thing can happen quite naturally (an assignment of a variable to itself can occur without the programmer ever writing a=a;). Can you work out what that situation is?

#include <stdio.h>
#include <string.h>

class MyString
 { protected:
     char * data;
     char * rev;
     int length;
   public:
     MyString(void);
     MyString(char * s);
     ~MyString(void);
     MyString & operator = (const MyString & x);
     void print(void); };

MyString::MyString(void)
 { data = NULL;
   rev = NULL;
   length = 0; }

MyString::MyString(char * s)
 { length = strlen(s);
   data = new char [length+1];
   rev = new char [length+1];
   for (int i=0; i<length; i+=1)
    { data[i] = s[i];
      rev[i] = s[length-i-1]; }
   data[length] = 0;
   rev[length] = 0; }

MyString::~MyString(void)
 { delete[] data;
   delete[] rev; }

MyString & MyString::operator = (const MyString & x)
 { delete[] rev;
   delete[] data;
   length = x.length;
   rev = new char [length+1];
   data = new char [length+1];
   for (int i=0; i<=length; i+=1)
    { data[i] = x.data[i];
      rev[i] = x.rev[i]; }
   return *this; }

void MyString::print(void)
 { if (data==NULL || rev==NULL)
    { printf("[empty]");
      return; }
   printf("[%s~%s]\n", data, rev); }

void main(void)
{ MyString a = "Dog";
  MyString b = "Hello";
  MyString c = "Cat";
  a.print();
  b.print();
  c.print();
  printf("\na = c;\n");
  a = c;
  a.print();
  b.print();
  c.print();
  printf("\na = b;\n");
  a = b;
  a.print();
  b.print();
  c.print();
  printf("\na = a;\n");
  a = a;
  a.print();
  b.print();
  c.print();
  printf("\n"); }

When I compile and run it, this happens:

[Dog~goD]
[Hello~olleH]
[Cat~taC]

a = c;
[Cat~taC]
[Hello~olleH]
[Cat~taC]

a = b;
[Hello~olleH]
[Hello~olleH]
[Cat~taC]

a = a;
[------眷眷~------眷眷戌戌戌戌戌戌戌A]
[Hello~olleH]
[Cat~taC]