Project Information

This course is a project course: the evaluation for the course is based on the satisfactory completion of the project. There are no other course assignments.

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:

The problem definition and literature background should explore and describe the problem or area of interest and provide some investigation of background work in this area. It should examine the research literature in the selected area, according to what are the important problems, to what degree are these problems understood and solved, how different solutions interrelate, and what are the important issues for the future. Original thoughts, solutions, insights are strongly encouraged and will be rewarded. Because of the time limits of the quarter and our emphasis on software implementation, this stage is generally expected to be very limited, e.g. google around, read a couple of papers, think hard for awhile and write your project proposal.

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

The project is to be structured into the following three stages (or requirements):
  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.


All work submitted should be done in a professional manner as though you were being paid for it. Documents should be type-written and use good technical English. Software submitted for credit should be well-written, meeting reasonable standards of programming.

Course Computing Resources

The Stanford course facilities are expected to be the instructional workstation clusters. You are also free to use any computer facilities you might have available to you that would serve better the needs of your project.

Projects Ideas and Areas

In general, every project must be clearly related to carefully structured statically type object-oriented programming along the lines advocates in CS249a/b and related techniques. The following are some suggestions that indicate the general type of project acceptable as well as hopefully suggest further project ideas.
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.
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.
All of these are germs of ideas that would need to be fleshed out and focused further before writing a proposal once you are "infected".

The Initial Project Proposal

The following describes what is expected in the Initial Project Proposal. It is also hoped that this will help in the selection and definition of a suitable project. The format outlined below is not mandatory.

Overview of the Proposal

Briefly state the topic chosen, why it is of interest, the goals, and how you intend to carry this out. This should be a short paragraph of about 4-5 sentences.

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

Describe the chosen area, which should be fairly narrowly defined, giving a few references to relevant work (if known). This description should be terse and at a high technical level (e.g. do not spend time defining technical terms used). Next give reasons why the area is of current interest to the technical community in general and to you in particular. Finally list (at least three) potential problems which merit further investigation. (Note: your project need not necessarily advance the state of the art, but it must advance the state of your knowledge and skills.)

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

Describe in some detail the problem which you have chosen to attack and the reasons for its importance in relation to the other problems, if any, listed above. Describe your proposed method of investigation. Give some convincing reasons why you believe you will be able to complete the project as proposed by the end of the quarter. A division of the work into phases with a timetable for completion of the phases would be helpful. It is better to propose a modest project and complete it successfully by the end of the quarter than to make a vague or grandiose proposal which you are unable to complete.

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

Describe as specifically as possible the results which you expect to obtain. Give an outline of the design which you think will solve the problem at hand. State what you think the experiments will show. The objective of this portion at this stage is to get you to focus your thinking somewhat, based what you can do so you have something to say at the end of the project.

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

Below are a project proposal and milestone from the Winter 2008 offering of this course.
Project Proposal

Below are the project proposal and milestone from by course assistant in 2010 from him taking the course the year before. (Please note that the project changed from the proposal stage to the milestone).
Project Proposal

The End