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: 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 hands-on 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 real-world 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 non-technical co-workers, 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: 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:

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 2-quarter 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 trade-offs 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:

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: 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 in-depth study of process and thread communication and synchronization in the Unix/Linux environments. We covered inter-process 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 inter-process 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:

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: