Project Information

The project is a vehicle for the student to take an active part in exploring the subject area, as appropriate for an advanced course. Thus, a project must be chosen that will clearly extend your knowledge and understanding of some area of relevant to the couse. Moreover, the primary criterion for evaluating your project will be what you have learned and discovered from the project, not the amount of work involved or the amount of code written or the number of pages of written report. Thus, you should define your project with this consideration in mind and prepare submissions that communicate what you have learned to the instructor.

The project is also intended as a useful prototype experience for those going on to advanced design work or research.

There are three aspects to a project:

• Problem definition and literature background.
• design
• implementation and experimentation

The design should try to map out a software solution that is implementable with the available time and computer resources. With the intended "prototyping" nature of the projects, the design, implementation and evaluation may be performed iteratively. However, there is merit in trying to think things through before doing at each iteration.

In the implementation and experimentation phase, the design, or some aspect of the design is implemented to demonstrate feasibility. The experimentation involves developing a reasonable hypothesis and designing and performing an experiment to test this hypothesis.

In general, the course project must be relevant to the issues and techniques and directions covered in the course or cs249a. Students may work alone or in groups of 2 or 3 with the prior consent of the instructor.

Structuring the Project

1. Initial Proposal A written proposal describing the area and problems to be explored, the motivations for choosing this area, possible directions of investigation, proposed type of project, and the expected results. And the progress to be expected by the milestone. This should be roughly 1-3 typewritten pages.
   Submission Instructions: Email your written proposal in txt, pdf or doc(x) format to the instructor by 11:59pm Thursday, January 20. We will give you feedback shortly thereafter and you have a chance to iterate.
2. Milestone 1 page report describing progress or a change in plans/course given work done. Should show roughly half completion as described in the initial proposal
3. Final Report and Demonstration A final description of what was attempted, what was accomplished, and what was learned from the project. Ideally, this will be a revision of the proposal, changing the descriptions of proposed work to descriptions of accomplished work; refining the goals and objectives, including a brief literature survey for completeness and extended with some final conclusions and observations. The idea is for this to be the cumulation of the previous steps, not an entirely new document. The demonstration should provide some working evidence of the work accomplished, ideally demonstrating some point to the project, i.e. the performance of some critical aspect to the design, etc.

   Note: negative results that indicate something did not work are welcome. In fact, it is important to recognize the limitations of the results in any case.

Standards

Course Computing Resources

Projects Ideas and Areas

Restructuring Existing Software

Restructure some existing software to follow the CS249 discipline, measuring the effect on lines of code, performance, etc. as well as exploring any other issues that arise. The target is to evaluate the approach with yet another application, understand the benefits and disadvantages and identify open issues.

Audit

Take some existing software and add audit capability, exploring how to structure, support templates, etc. that would facilitate and perhaps aspects of getting completeness.

Object-oriented Transaction Support

Explore the design, implementation and use of a Transaction object, to manage the state associated with multi-action transactions.

Geometric Descriptions

Look the design of a geometric description API from the CS249a/b standpoint, implementing and comparing some existing API, such as SGI's Performer. This could also be done at the lower-level such as graphics API such as OpenGL. There is some effort called "Longs Peak" associated with OpenGL that is supposedly making it more object-oriented and might be worth reviewing.

One could control the size of the project by only implementing some basic subset of the revised API.

Other Descriptions

Related to the above, one could implement other non-trivial descriptions to evaluate the PEEVE approach described in the named description chapter. Even implementing and evaluating the proposed String implementation could be the basis of a project.

Single-writer vs. Multi-write Concurrency

You could explore the structure of some concurrent programs using the single-writer (multiple reader) approach advocated in the concurrency chapter. For example, how would a parallel file server or web server be structured in this approach?

Knowledge-based Representation

In the comparisons I have done to the so-called knowledge-based representation systems (KBR) of AI, they are basically untyped versions of the object models we build in C++. One could look at one or more representative KBR systems and explore the issues of providing comparable functionality in a C++ library or similar

Collection/Iterator Semantics

Java and C# and C++ STL have substantially different semantics associated with collections in general, and iterators in particular. A project could explore these differences in semantics and try to understand and quantify the differences. For example, Java and C# iterators can throw exceptions in some cases. What are the implications in performance when not wanted.

Unit Testing vs Statistics/Counters

We consider in the course the possibility of providing more extensive statistics and counters in a software system, and relying on tests checking the correctness of these counters to reduce the amount of direct test output checking. A project could look at evaluating this approach using some existing software system, considering additional counters and statistics to add, how they would be tested and some sense of how they contribute to the actual testing of the system.

Collision Paradigm

CS249a talked about the collision paradigm as a means to support dynamic discovery of relationships and to reduce the burden of maintaining references as part of relationships. Develop a general-purpose framework that supports this approach, ideally evaluating cost to help with making good trade-off decisions. Alternatively, explore the collision model within the context of some game or simulation.

Physical Simulation Value Types

In physical simulation, there is scalar, coordinates, velocities, accelerations plus their angular equivalents. Moreover, these are formed into 3-D vectors that need to support various operations. Explore how to model these various types and their operators such that the appropriate operators and conversions are allowed and inappropriate ones are precluded.

Collection Support

Develop an improved collection foundation for programming, perhaps building the work in various programming languages for group operations as well as addressing the deficiencies of STL, if you believe there are some. More specifically, consider the implementation of a string class or other variable-sized type, e.g. a sparse bitmap. How should it be designed so that its space requirements and processing requirements can be predicted in terms of overall application data demands?

Synchronization and Concurrency

The course proposes a particular approach to concurrency based on non-blocking synchronization and notifications. A project could develop a parallel or concurrency application in this structure to evaluate this approach. Alternatively, there could be an effort to compare this approach to other alternatives.

Open Router Platform

Click and XORP are two efforts to develop a framework for network/router components to provide an open, extensible platform. Evaluate these, or else develop some portion of your own. You could also focus on one particular aspect, such as packet buffering. The instructor will try to come up with more thoughts, plus you are invited to develop your own ideas.

Spec Languages vs. C++/Java

Programming languages have improved a lot since the early days, providing a higher-level representation of the design. What role, if any, can a separate specification language play. The use of such languages seems to be negligible in industry except for very high-reliability systems. Can we understand the issues here better? Semantics: Can we get a better handle on semantics. For instance, develop a class library that allows representing semantics as properties and testing objects and classes for specified properties.

C++ Templates and Genericity

Analyze the advantages and disadvantages of using C++ Templates for generic programming in the context of a sizeable software system. Perhaps examine the potential savings in lines of code and minimizing code duplication, amongst others, weighed against disadvantages such as added complexity and cryptic error messages. For example, you can take some existing piece of software that is not built on templates and rewrite it to use templates wherever feasible, and compare and contrast the two versions.

Memory Management

Explore effective ways of managing memory in the traditional engineering sense, that is, being able to state with substantial accurancy how much memory a software system requires. Additionally, look into leveraging the memory management techniques taught in class and elsewhere, such as PEEVE and copy-on-write, to effectively minimize memory demands from existing software or your own.

Invasive Collections

Traditional collection libraries such as the STL use metadata structures to support their internal behaviors. In class, you will learn about invasive collections and their advantages and disadvantages. I have heard more and more companies in industry employing this technique for performance-critical processes. A project you could do in this regard is to take an existing piece of software built using traditional STL collections, modify it to use invasive collections, and analyze the benefits and downsides in this system.

Named Descriptions and Large Value Types

In class, you will learn some techniques for managing very large value types and objects in software. A possible project you can do is to take an existing piece of software that uses very large objects naively, and explore techniques taught in class and elsewhere to efficiently and predictably manage the memory.

Transactional Memory

Haskell, a contemporary functional language with modal support for non-functional IO and built-in concurrency features, has out-of-the-box support for Software Transactional Memory (STM). If you're somewhat familiar with Haskell, a potential project could be to build a software system using Haskell's STM facilities and examine its benefits and downsides in comparison to more traditional methods.

Fault Tolerance and Audit

More and more software systems in industry are emphasizing fault tolerance and the notion of "four nines", that is, 99.99% up-time. Examine different ways within a sizeable software project to leverage an integrated auditing facility to support fault tolerance and reliability.

The Initial Project Proposal

Overview of the Proposal

Example: A topic of overriding concern at Stanford is the transportation problem. We propose to study the traffic patterns in White Plaza and to submit a design which will reduce the hazards currently faced by both cyclists and pedestrians by partially segregating the two. The existing traffic patterns will be measured and the proposed design simulated to provide a comparison.

Background and Motivation

Example: Several modes of transportation are used by people to move about the Stanford campus. The traffic at several places becomes very congested and uncontrolled during certain periods. This has caused several accidents, resulting in at least one fatality in the past [Stanford Daily, Campus Report]. While some effort has been made to keep automotive traffic out of the inner campus, bicyclists and pedestrians roam uncontrolled over all areas of the campus. Several places in the inner campus merit study of traffic patterns and implementation of controls to reduce the hazards involved in moving about the campus.

Proposed Project

Example: We propose to study the traffic problems in White Plaza and to design a system to reduce the hazards posed to travelers in this area. Using statistically sound methods we intend to measure the volume of pedestrian and bicyclist traffic from secure vantage points during selected periods. This study will take several weeks. The data gathered during this period will enable us to construct a model of the traffic in White Plaza. Using this model we will devise a system to segregate bicyclists and pedestrians whilst minimizing the inconvenience caused. This will probably necessitate the use of underpasses, overpasses, bike traps, pedestrian traps, . . .

Expected Results

Example: The benefits of the project are two-fold. Firstly, we will quantify the magnitude of the traffic problem in White Plaza. This will enable extrapolations to other congested parts of the inner campus. Secondly, we will present to the administration a traffic control system for White Plaza which will make it safe for both bicyclists and pedestrians while retaining the functionality and architectural beauty of the area.

Examples from Previous Years

The End