Rebelsky - CS2 Data Structures (Proposal)

This very rough draft is presented in the spirits of (a) transparency and openness and (b) ask for funding for work that you're going to be doing anyway. (I think you know that I was going to do this anyway, since I talked about it at the second IRC chat.)

Context

A number of us are talking about ways to incorporate open source earlier in the curriculum, in courses that are already packed. In particular, many of us were considering what I refer to as CS2 - Data Structures and Algorithms, with perhaps a bit of Object-Oriented Programming and Abstract Data Types mixed in. That class is typically full enough that it is difficult to add something significant to it. And, as Cam said, the students aren't advanced enough to make deep contributions to the project.

An Approach

So ... I've been thinking about ways to incorporate an HFOSS project while still meeting the main goals of the course. One natural approach to me seems to be to take advantage of Ushahidi's data feeds. It should be pretty straightforward to build an infrastructure that lets students work with a local Ushahidi install, grab data from the install, and process it in different ways. I'm not sure whether or not I want to have them deal with the raw data, or whether I should add a wrapper that lets them just grab a list or stream of objects (e.g., Incidents).

Meeting Course (Coarse?) Goals

In terms of the core algorithms and data structure issues, sorting and searching are two obvious approaches: "Present the data in sorted order by ___"; "Find all entries that meet these criteria"; .... And the data feed is a tree, of sorts, so we might be able to find some tree algorithms to deal with it.

I can also see modeling the "validate" step using the three common linear data structures - queue, stack, priority queue. That is, as data comes in, what order do you want to process it in and how do you store the data to make it easiest to process it in that order. Sometimes the newest request is the most important. Sometimes the first. And sometimes you have another kind of priority. This example also provides an opportunity to talk about some simple good designs. Ideally, the "validate" client can let us plug in whichever linear structure will best serve our policy.

Meeting HFOSS Goals

Many of the HFOSS Community Activities that we've talked about don't quite seem appropriate for this type of class. They aren't advanced enough to contribute code patches to the project. They don't really have time to do projects like write documentation. So, how do they contribute beyond just using the data feed?

I hope to personalize their work in two ways. For the first half of the semester, as they learn the first core topics of the course, they will do homework assignments that involve gathering data from an Ushahidi install. I hope to build one that logs incidents that they may find of interest on campus. (Illness outbreaks? Drunkenness? I'll need to talk a bit to our student affairs office to see what they think would be useful and acceptable.) Alternately, we might look for something to track in the community.

Toward the second half of the semester, I hope to have them work with a client (an office on campus, someone in the community, an alum who is willing to be or to simulate a real client) to build a small Ushahidi application. To prepare them to work with clients, I will probably have them follow appropriate aspects of the Ushahidi community. (After all, they'll need to have examples to show clients the kinds of things that they can build.)

So, how does this contribute? I think that this approach of *build things using an HFOSS application provides many of the things we want for students and for the community. They'll need to be a bit involved with the community to understand the uses of Ushahidi (and perhaps to set up their own application). They'll be pushing it in certain ways, which may provide opportunities for submitting feature and/or bug requests. (Perhaps they will even be inspired to learn enough to make changes, although I doubt that they'll have the time.)

Assignments

HFOSS: Working with Github

This is somewhat secondary to the main project, but I do expect them to use github for the course. I'll be putting any "course code" on github and will ask them to submit via github.

Algorithms: Linear Search

Summary: Using a simple API (downloaded from github), get a list (iterator) of incidents from Ushahidi and print out all of the ones that meet some criteria

Prerequisites: Basic Java knowledge. Iterators.

Learning Goals (HFOSS): Existence of HFOSS software (Ushahidi). Public APIs.

Learning Goals (Design): Working with a library. Designing algorithms that use comparators.

Learning Goals (Algorithms): Review of Linear Search

Algorithms: Binary Search

Summary: Using a simple API (dowloaded from github) that presents an array of incidents from Ushahidi that are sorted by _, find the ones that meet some criteria and determine the time it took you to do so.

Data Structures and Algorithm: Parsing a Tree

Summary: Given an API that returns the JSON or XML, write an API for something that returns the data as a tree (or list or ....).

Project: Build Something for A Client

Summary: Meet one of the identified clients. Tell them about the capabilities of Ushahidi. Identify a project that they like that you think would be able to complete and that draws upon what you have learned this semester. Build the project. Present it to the class in a lightning presentation. 'Blog about it.

Issues

I'd like to make sure that the assignments are exciting ... not just "search for X" but "here's a reason you want to search for X". That will take some consideration.

I need to figure out the best way to s how the results of these applications. Will they be interactive? Will they be command-line tools? Will they be Web-based?

I need to figure out reasons for the applications to send data back to Ushahidi. (And I think that will help refine the design of the applications.)

I would like to consider incorporating the Ushahidi Android application. It may be that all of this will work better if they have the option of working with a Java API in addition to a Web API. I also expect that they will be more excited to deploy a customized version of the application. And deploying that customized version will put them more deeply in touch with the community. But I worry that figuring out how to do all that will be very time consuming.

Schedule

I'm teaching our course this fall, so I'd expect to do the test run this fall.

I am fortunate to have a group of four summer research students available to work on parts of this project. (They have other things to do, but they've agreed to work on assignments that include Computing for Social Good as a theme of the course.)