Rebelsky - CS2 Data Structures (Proposal)

Revision as of 19:39, 24 June 2013

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 an open-source 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'll start by providing them with a wrapper class that handles communication with the server and parsing data into a collection of objects. Later in the semester (probably when we get to trees), I'll have them parse the raw JSON or XML data.

The initial focus for this wrapper class will be a standalone Java application that students may run through the terminal or Eclipse. However, I also plan to explore ways in which we might extend the Ushahidi Android App to provide opportunities to use the same API to achieve goals within that app. I've assigned three summer students to explore this opportunity.

Meeting Course Goals

In terms of the core algorithms and data structure issues, sorting and searching are two obvious approaches: "Write a program that presents the data in sorted order by ___. Generalize your core algorithm so that someone else can use your code to sort in different ways"; "Find all entries that meet these criteria. Generalize your code."

Ushahidi permits administrators to both validate and approve incidents. I can see having students explore relationships between the core linear structures (queue, stack, and priority queue) through a simple interface for approving incidents. 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. I see the API that they eventually program to as supporting two basic methods: addIncident(Incident) and nextIncident.

Meeting HFOSS Goals

Many of the HFOSS Community Activities that we've talked about don't quite seem appropriate for this kind of course. Students in the course generally aren't advanced enough to contribute code patches to the project. In addition, they don't really have time to do projects, such as writing documentation,that are tangential to the main learning goals of the course. So, how do they contribute beyond just using the data feed?

I hope to incorporate HFOSS in their work in two ways. For the first half of the semester, as they learn the core topics of the course, they will do homework assignments that involve gathering data from an Ushahidi install. I hope to set up an Ushahidi installation that logs incidents that they may find of interest on campus. Right now, my plan is to focus on campus outreach to the community - each time students volunteers in town, they can log their activities. I'll be meeting with Grinnell's director of Service Learning and Engagement to consider this approach. Alternately, we can track some kind of events on campus. In that case, I'll need to talk to our Office of Student Affairs to see what they think would be useful and acceptable.

Toward the second half of the semester, I hope to have students 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 students 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 back to Ushahidi? 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.)

In addition, if the research students who are extending the Ushahidi App to support the class develop extensions that will be useful to the broader Ushahidi community, they will contribute those back to the community.

Assignments

I expect to write between six and nine "assignments". Some assignments will be designed to be short in-class exercises. Others will be week-long programming homeworks. At the end of the semester, students will do a longer, project-style assignment that involves developing an Ushahidi installation. A list of potential assignments follows.

HFOSS

Working with github (~1 hour)

A short introduction to using 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.

Ushahidi

Working with a simplified Ushahidi API (~1 hour)

Introduces students to the simple Wrapper API that we've designed for communication with Ushahidi. Students will print out one or two incidents and perhaps approve an incident.

Building the Ushahidi Andoid App (~2 hours)

Walks students through the process of downloading the Android SDK and the Ushahidi code, building, and installing on an Android device.

Setting up an Ushahidi Server(~2 hours)

Walks students through the process of setting up a server. (Hopefully, a simplified version of what the POSSE Ushahidi team did.)

Algorithms

Simple Linear Search (~1 hour)

Using the simplified API, print out all entries that match some criterion. (E.g., all unverified reports more than a week old.)

Binary Search (~4 hours)

Given an id and an array of UshahidiIncidents that are sorted by id, return the UshahidiIncident with that id. Determine the number of comparisons that this took.

Given a date and an array of UshahidiIncidents that are sorted by date, return the last incident before the given date. Determine the number of comparisons required.

Given a starting and ending date and an array of UshahidiIncidents that are sorted by date, return the number of incidents that occur between those two dates.

Testing Sorting Algorithms (~3 hours)

Write a thorough set of unit tests for the method sort(UshahidiIncident[], Comparator<UshahidiIncident>). Submit your tests back to our common code repository.

Selection Sort (~3 hours)

Implement the sort method using the selection sort algorithm.

Quicksort (~3 hours)

Implement the sort method using the Quicksort algorithm.

Heapsort (~5 hours)

Implement the sort method using the Heapsort algorithm.

Object-Oriented Design

Generalizing Linear Search (~ 4 hours)

Write and test a utility function that takes a stream of UshahidiIncidents and a Predicate<UshahidiIncident> as parameters and returns a list of UshahidiIncidents for which the predicate holds.

Data Structures

Stacks and Queues [4 hours]

The application "Approval" provides a simple interface which allows administrators to see and approve/reject/skip incidents one by one. Basically, incoming events trigger calls to the addIncident method and the UI does a call to the nextIncident each time the administrator wants to consider another incident. But what happens when the incidents arrive faster than the administrator can approve the data? The application needs a policy to indicate which incident should be considered next.

Implement addIncident and nextIncident so that the policy is "first in, first out". That is, the incidents are processed in the order in which they arrive.

Implement addIncident and nextIncident so that the policy is "last in, first out". That is, the most recently added incident that has not yet been processed is processed next.

Priority Queues [3 hours]

Of course, we may have other ways of prioritizing incidents. For example, some categories may have higher priority than others. Add a setIncidentOrder(Comparator<UshahidiIncident> method and then implement addIncident and nextIncident to support that order.

Parsing and Trees [4 hours]

You may have been wondering how we get the data from the Ushahidi server. Ushahidi provides a Web API that returns data in JSON format. Write a program that reads in this format and prints it out nicely indented.

Project

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 show the results of these applications. Will they be interactive? Will they be command-line tools? Will they be Web-based? Will they be applets? Will they take advantage of a modified Android App?

Activities

• Learn more about Ushahidi and ways that it is used.
• Lurk in Ushahidi development community.
• Meet with Director of Service Learning and with Student Affairs to discuss possible projects.
• Develop local deployment that students can use in the course. (Requires picking a topic and gathering data.)
• Develop appropriate library to ease student use of the Ushahidi data feed.
• Experiment with extending the Ushahidi Android App to see if it is amenable to course use.
• Design assignments.
• Write assignments and supporting materials (e.g., instructions, code, unit tests).
• Test assignments.
• Post materials to foss2serve or teachingopensource

Assessment

We only offer one section of this course each semester, so a direct course-to-course comparison is not possible.

I think it's important to look at general learning and attitudinal outcomes (not just CS, but things you might hope for in any course, such as understanding of how disciplines interoperate or building student confidence). I appreciate the general, course- and discipline-independent "Research in the Integrated Science Curriculum" (RISC) instrument.

We do not return finals in the course (and at least one of my colleagues keeps all of the submitted finals), so it will be possible to reuse some questions from previous offerings of the course and to compare student answers.

Schedule

I'm teaching our CS2 course this fall, so I'd expect to do development in the summer and pilot the approach in the fall.

I am fortunate to have a group of three summer research students available to work on parts of this project. Each completed the course this past spring. They are interested in helping build the wrapper library and to work on making the Android App more adaptable to this course. They are also willing to provide student-centric critiques of the assignments. And I think I can convince them to write some of the unit tests for the various assignments.