DRAFT **** DRAFT **** DRAFT **** DRAFT **** DRAFT ****
Fall Quarter
Data Structures I
This component, using the textbook Data Structures, Algorithms, and Applications in Java by Sartaj Sahni, covered the basic data structures: arrays, linear lists, stacks, queues, and trees. The focus of the study was on:

representation issues

how representation choices impact efficiency

applications that make use of the data structures studied.
Students were evaluated on seven programming assignments, a midterm, and a final. By the end of this class should should understand the range of representation choices available to them, how such design choices impact the behavior of algorithms, and how to critique a variety of data structures for their applicability to problems. They should also be able to read and understand complex designs and implementations and to to modify and create new implementations of data structures with required functionalities.
Operating Systems I
This component, using the textbook Modern Operating Systems by Andrew Tanenbaum was primarily a concept course. Students studied, in depth, the basics of Operating Systems design: virtual memory, the file system, schedulers, the interrupt structure, the IO subsystems. In addition, students began some handson work in the lab in order to learn the pragmatics of creating processes, process synchronization, how the file system is structured, and user level timers. These projects were based on the textbook Kernel Projects for Linux by Gary Nutt.
Students were evaluated based on six textbook assignments, five labs, and two exams.
By the end of the quarter, students should understand the basic design issues involved in modern operating systems. They should also be able to use a modern operating system (Linux), understanding how system calls work, and how to use them effectively to do systems level programming.
Software Architectures.
This component, using Essential Software Architecture by Ian Gorton was designed to give students insights into the complexities of large systems designs. The book introduced students to the kinds of knowledge, considerations, and skills a software architect should have and how those skills relate to project design and implementation. Students were encouraged to use their own experiences and to research projects in order to understand the real impacts of decisions made at this level, ranging from software structure, system quality, system correctness and maintainability, and the limitations placed on design by realworld constraints.
Students were evaluated on seminar participation, presentations, and a cumulative paper.
At the end of this component students should have a vocabulary that will allow them to communicate technical decisions to nontechnical coworkers, stand back from the details of design to articular essentials, and to work at a level that abstracts away particular technical decisions.
Project Research.
During this preliminary research component, students researched their general areas of interest. Midway through the quarter students were expected to submit a research proposal that included:

A description of their topic.

A justification as to why this topic is of interest to them or important to study.

A plan on how they will proceed to refine their topic.
At the end of the quarter, students were expected to submit a thesis proposal that identified the actual project they will work on for the remaining 2 quarters. The proposal included:

A description of the project and its intended outcomes.

The project milestones
Winter Quarter
Data Structures II
The second quarter of Data Structures was a continuation of Data Structures I, using the same textbook with the same expectations and approaches. The students covered trees, concentrating on binary search trees, and balanced trees, graphs, and a variety of algorithm design methods, including greedy methods, branch and bound, divide and conquer, and dynamic programming.
The students were evaluated on seven programming assignments, a midterm and a final.
At the end of this 2quarter sequence students will have studied the standard core of data structures in depth. They will also be prepared to study, on their own, variations of these data structures, to understand the tradeoffs each design decision entails, and to create their own data structures as needed.
Operating Systems Projects.
The second quarter of Operating Systems was based entirely on the textbook Kernel Projects for Linux by Gary Nutt. Students worked on five projects, exploring the Linux kernel in depth. These projects included:

Writing a Kernel modules

Writing a new system call.

Changing the shared memory implementation.

Exploring the kernel level synchronization.

Altering the Kernel scheduler.
The students were evaluated on the five projects and a comprehensive final. The students were expected to complete the projects and write a document describing their work.
By the end of this quarter students will be comfortable exploring the system independently, will understand the implementation structure of the kernel and, more importantly, will understand the range of design decisions possible, and the motivations for those decisions, so that they will be able to explore other operating systems and future designs on their own.
Technical Reading Seminar: Programming, Programming Language Design.
In this quarter students read a collection of technical papers covering three related themes: what is good code? issues in programming language definition, and the role of type systems in programming languages. We read the following papers:

Goto statement considered harmful by Dijkstra

The Model View Controller Xerox PARC technical note May 1979

Selected essays from Beautiful Code by Andy Oram, Greg Wilson

Notes on Postmodern Programming by James Noble, and Robert Biddle

Why Functional Programming Matters by John Hughes

Growing a Language by Guy Steele

Pizza into Java by Philip Wadler

How to add laziness to a strict language, without even being odd by Philip Wadler

What to know before Debating Type Systems by Chris Smith

Featherweight Java by Philip Wadler

Java is not type safe by Vijay Saraswat

Is the Java Type System Sound? by Drossopoulou
Students were expected to participate and keep a journal of their thoughts. This seminar, as well as being an opportunity to delve more deeply into programming language issues, was also an opportunity for the students to improve their skills in reading technical literature.
Project Research
Students continued on the project work, to be completed in the spring. Each group was expected to present progress reports to the class three times during the quarter, describing their work and any unforeseen problems that were encountered, and how those problems affected their goals.
Spring Quarter
Analysis of Algorithms
This component, using the textbook Analysis of Algorithms by Jeffrey McConnell covered the basics of algorithm analysis. We covered recursive algorithms, searching and sorting, numeric algorithms, matching algorithms, graph algorithms, and parallel algorithms. Students developed the skills needed to analyze algorithms and were expected to apply those skills to a variety of algorithms presented in the texts.
Students were evaluated based on 7 textbook assignments, a midterm and a final.
By the end of this course students should be able to apply their analytic skills to algorithms they encounter in existing systems and to those they write themselves. They will be able to critique algorithms and identify possible sources of inefficiency. They will gain experience in reading algorithms and selecting analytic criteria.
Concurrent Programming
This component, using the textbook Unix Systems Programming: Communication, Concurrency, and Threads by Kay Robbins and Steve Robbins was an indepth study of process and thread communication and synchronization in the Unix/Linux environments. We covered interprocess communication, how to manage concurrency, and multithreading techniques, using a variety of standards. We analyzed the techniques, when to use them, and the circumstances in which the techniques would be most effective. The students wrote a variety of projects that integrated these techniques and demonstrated best practices.
The students were evaluated on five to seven projects and a final exam.
By the end of this quarter the students should be able to use the interprocess communication and synchronization primitives provided in the Unix and Linux systems effectively, including the ability to design, implement, and test complex concurrent systems with a variety of synchronization constraints.
Technical Reading Seminar
During the spring quarter, we read:

Java is NOT type safe by Vijay Saraswat

Is the Java Type System Sound? by Sophia Drossopoulou, Susan Eisenbach, and Sarfraz Khurshid.

Gradual typing for objects. iek and Walid Taha

Josh Bloch on Design by Bill Venners

Amazon.com Interview with Joshua Bloch

Seven Myths of Formal Methods by Anthony Hall

CONS should not Evaluate its Arguments Daniel Friedman and David Wise

The Ugly Duckling by Martin Fowler

Is proof more costeffective than testing? by Steve King, Jonathan Hammond, Rod Chapman, and Andy Pryor

Software Development Practices, Software Complexity, and Software Maintenance Performance: A Field Study by Rajiv Banker, Gordon Davis, and Sandra Slaughter
Project Research and Implementation
During the spring quarter the students completed their research project. Students were expected to give a presentation of their project (either an implementation demonstration or a talk with significant examples of their work), Students also wrote a report of their work, including a description of their work, detailed examples, and a review of related work.
By the end of these three quarters, students will have gained the experience of:

selecting an area of interest

doing background research

forming a specific question or goal

creating an implementation plan

completing the work

presenting their work to the class

writing up their results in a formal paper complete with citations positioning their work in the field