Stanford University
Computer Science 249B: Winter 2008 - 2009

CS249B Midterm 2009

You should complete the exam yourself without assistance from others. It is a violation of the honor code to receive assistance from others or to copy material without proper attribution.

Feel free to use point form. Each question can be answered satisfactorily in a page of writing or less. I am primarily interested in the three (3) key points responsive to each question. Each question is weighted equally.

1. Software Engineering: Ms. Scrabel, a "diversity consultant", has advised your boss that you need to move away from the rigid Cheriton view of following a strict software development process that focuses on hiring discipline "common culture" engineers that fit into this. With the benefit of her liberal arts BA, she claims that: 1) diversity brings different points of view, 2) giving people liberty in how they approach problems leads to greater creativity, and 3) there are many ways of solving problems. Describe the three key points you would make to counter her position.
2. Audit:
   1. Give an example of a bug that would not likely be caught by conventional functional testing, and too expensive to check as part of inline asserts yet would be caught with audit.
   2. A procedure signature does not completely specify the situations in which the procedure can effectively do something useful. Some programmers argue for asserts as specification of preconditions to handle this. The alternative is to have the procedure check for such conditions and just return if nothing it can do. Describe the trade-offs between asserts and the "just return" approach.
3. Shared Descriptions:
   1. Mr. Knowitall claims that what Cheriton advocates for large value types, namely implementing them as a hidden pointer to a shared description is just one way of dealing with large values. Describe the argument for this being the best way, perhaps only way.
   2. PEEVE (pointer equality equals value equality) is challenging to achieve. Describe how to do this, and the costs of doing so.
4. Concurrency: Consider a sophisticated security monitoring system that is processing multiple streams of video from security cameras in a building, matching objects in the video to door card reader indications of personnel entry and tracking their path through the building, maintaining a log of activities and generating alarms according to departure from profiles. The system needs to support C cameras and D door card readers, where C and D can range from small to quite large, as required on a major enterprise campus. Assuming you are to implement this application to run on a cluster of shared memory multiprocessors, sketch the design of a parallel implementation of this system reflecting the principles of the course, focusing on providing scalability of processing and fault tolerance.
5. Collections and Iterators:
   1. Mr. Knowitall argues that non-invasive collections are far superior because: i) they handle objects in other modules that you cannot modify (unlike invasive collections), ii) objects can be in arbitrarily many collections, iii) memory is cheap. Describe the counter-argument to each of these points.
   2. Cheriton's version-based approach to detecting a collection has changed during iteration seems pretty questionable at first glance, given that does not guarantee the application a consistent view of the collection directly and may cause livelock if the application retries until no version change during iteration. Describe why this is the best of the feasible solutions in many situations.

   The End