Stanford University
Computer Science 349: Winter 2006 - 2007

CS349 2007 Final Exam: Take Home Exam

Due: March 22nd at 11:59 pm. Please submit by email to your instructor.

You are free to use any material, including books, course material, etc. However, you should complete the exam yourself without assistance from others. It is a violation of the house code to receive assistance from others or to copy material without proper attribution.

Feel free to use point from. Each question can be answered satisfactorily in a page of writing or less. I am primarily interested in the most key points responsive to each question.

  1. (8 pts) Collections
    Your instructor proposes the "method-invasive" extension to the invasive collection model of the world, as follows:
        class AirplaneTank {
      private:
        AirplaneTank *llNext_;
        int fuelLevel_;

      public:
        void llNextIs(AirplaneTank *t) { llNext_ = t; }
        AirplaneTank *llNext() const { return llNext_; }

        int fuelLevel() const { return fuelLevel_; }

        int totalFuel() const {
          int total = 0;
          while ( this ) {
            total += fuelLevel();
            this = this->llNext_;
          }
          return total;
        }
    };

    class Airplane {
      private:
        AirplaneTank *tankList_;

      public:
        int totalFuel() const { return tankList_->totalFuel(); }
    };
     He admits that the code as presented doesn't quite compile (g++ gets upset if you use this as an lvalue), but asks excitedly "isn't this a neat way to use invasive collections?"
    1. (2 pts) - This can be made to compile by changing only the totalFuel() function to make it recursive. Write a working (compiling) version of totalFuel().
    2. (6 pts) - One of the "neat" features of this approach is it would be possible to replace all instances of LinkedList (for instance) with simple pointers, since the class itself would provide the means to add and remove elements from the list. Provide 3 reasons why method-invasiveness is a good or bad idea.
  2. (8 pts) Audit
    1. (2 pts) Why is audit scoped? Specifically, if each object is simply validating that its state is consistent, why would you ever wish to audit just a portion of the program?
    2. (2 pts) Why do we support so many different types of audit? Specifically, if each object audits itself, why would we ever want to have a global audit routine?
    3. (4 pts) Suppose that during audit processing object A calls for an audit on object B, and object B calls for an audit of object A. We could theoretically end up with an infinite audit loop. Give 2 reasons why this is not a problem in practice.
  3. (8 pts) Value Types
    1. (6 pts) In class we discussed a number of ways in which application-specific value types can be used effectively. Give 3 good uses of application-specific value types. These should be specific examples of useful value type classes, rather than abstract categories.
    2. (2 pts) Give one example of a poor use of application-specific value types.
  4. (8 pts) Type Structure of Programs
    Consider the following simple socket interface class: 
        class Packet {
      public:
        Packet(char *bytes, int len) : bytes_(bytes), len_(len) {}

        char *bytes() const { return bytes_; }
        int len() const { return len_; }

      private:
        char *bytes_;
        int len_;
    };

    class Socket {
      public:
        Socket(int osSocketFileDescriptor) : fd_(osSocketFileDescriptor) {}

        void newPacket( Packet *p );
        Packet *firstPacket();

      private:
        int fd_;
    };
     Suppose there is consensus among your developers that this is the appropriate interface for network sockets throughout your code, and is therefore unchangeable (consensus is so difficult to attain!). Nonetheless, for TCP sockets you realize that you need to be able to determine the number of unacknowledged bytes. If you were able to change the Socket class, you would add a method with signature
            int unacknowledgedBytes() const;
    1. (3 pts) How can this functionality be supported without changing the Socket class? You will need to create a new interface class. Provide the code for this new interface class.
    2. (3 pts) Provide the code which, given a Socket *, is able to compute the number of unacknowledged bytes on that socket.
    3. (2 pts) Have we broken the type system in doing this? If so, was it strictly necessary to do so? If not, why not?
  5. (8 pts) Descriptions
    1. (2 pts) Defend the following statement: "In the case of descriptions, PEEVE can be a painful (computationally expensive) property to provide."
    2. (2 pts) Refute the following statement: "Sometimes it is not possible to provide PEEVE for shared descriptions."
    3. (2 pts) What advantages do named descriptions have over simple value type ADTs?
    4. (2 pts) Describe how you might construct a value object so that it utilizes the power of shared descriptions but looks like a simple ADT.
  6. (8 pts) Concurrency
    1. (4 pts) Identify 4 pitfalls of concurrent programming.
    2. (2 pts) Identify 2 reasons why we might still want to use concurrent programming.
    3. (2 pts) Identify and explain 2 techniques covered in this course which help to reduce the impact of the pitfalls you identified in part (a).
  7. (8 pts) Memory Management
    Choose 4 of the memory pools covered in class and discuss for each a potential application which would need that particular form of memory management. For each, justify why the application would need that specific memory manager type (as opposed to any of the other mem managers).

Thanks, The End