We present interactive software designed to support students' exploration of concepts involving Huffman coding. This software illustrates the association between binary codewords and paths in a Huffman tree, the greedy algorithm that is used to construct an optimal tree, and the use of the tree in the decoding process. It allows the user to control the input upon which the code is built, to step forward and backward through an animation of the algorithm process for constructing a tree, and to choose data to encode or decode. We have used this software with students in an introductory computing principles course, a first-year data structures course, and an upper-level algorithms course. The software is publicly available as a Java applet at http://cs.slu.edu/~goldwasser/demos/huffman.

We describe cs1graphics, a new Python drawing package designed with pedagogy in mind. The package is simple enough that students can sit down and make use of it from the first day of an introductory class. Yet it provides seamless support for intermediate and advanced lessons as students progress. In this paper, we discuss its versatility in the context of an introductory course. The package is available at www.cs1graphics.org.

There is an ongoing debate regarding the role of object orientation in the introductory programming sequence. While the pendulum swings to and fro between the "objects first" and "back to basics" extremes, there is general agreement that object-oriented programming is central to modern software development and therefore integral to a computer science curriculum. Developing effective approaches to teach these principles raises challenges that have been exacerbated by the use of Java or C++ as the first instructional language.

We demonstrate the use of a new Python graphics package named cs1graphics, while discussing its impact on pedagogy and showcasing the recent work of our students. Our package was originally developed with two goals in mind. First, we insisted that it be intuitive enough that students can sit down and make use of it from the very first day of an introductory class. Second, we wanted to provide seamless support for intermediate and advanced lessons as students progress. The resulting package is freely available at www.cs1graphics.org. We find its combination of simplicity and functionality unmatched by existing packages.

Teams representing the USA and Europe engage in a battle of words and wits to establish "once and for all" which educational system produces the superior outcome. This "no holds barred" debate leaves no stone unturned in a search for truth on this question, providing a final answer to a controversy that has plagued our community since the inception of computing itself. Witness this historic moment in the history of CS education first hand!

We consider the nonpreemptive scheduling of two identical machines for jobs with equal processing times yet arbitrary release dates and deadlines. Our objective is to maximize the number of jobs completed by their deadlines. Using standard nomenclature, this problem is denoted as P 2 | p j = p , r j | Σ Ū j . The problem is known to be polynomially solvable in an offline setting. In an online variant of the problem, a job's existence and parameters are revealed to the scheduler only upon that job's release date. We present an online deterministic algorithm for the problem and prove that it is 3/2-competitive. A simple lower bound shows that this is the optimal deterministic competitiveness.

Incorporating advanced programming concepts into an introductory programming course has to be done carefully to avoid overwhelming the students. We describe our experiences doing network programming in a CS1 course taught in Python. The simplicity of the built-in libraries allowed a fair amount of networking to be introduced in a week-long module of the course. In this short time we had the students writing both multithreaded clients and servers.

Python's use in education has grown rapidly, due to its elegantly simple syntax. Though often viewed as a "scripting language," Python is a fully object-oriented language with an extremely consistent object model and a rich set of built-in classes.

We investigate the use of a thin-client based configuration in providing students with universal access to a centralized, graphical computing environment. The primary goal is to enable students to work effectively from arbitrary locations and computing platforms, while always interacting with the consistent environment seen in tightly controlled labs.

In this paper, we study the complexity of self-assembly under models that are natural generalizations of the tile self-assembly model. In particular, we extend Rothemund and Winfree's study of the tile complexity of tile self-assembly [Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, 2000, pp. 459--468]. They provided a lower bound of $\Omega(\frac{\log N}{\log\log N})$ on the tile complexity of assembling an $N\times N$ square for almost all N. Adleman et al. [Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Heraklion, Greece, 2001, pp. 740--748] gave a construction which achieves this bound. We consider whether the tile complexity for self-assembly can be reduced through several natural generalizations of the model. One of our results is a tile set of size $O(\sqrt{\log N})$ which assembles an $N\times N$ square in a model which allows flexible glue strength between nonequal glues. This result is matched for almost all N by a lower bound dictated by Kolmogorov complexity. For three other generalizations, we show that the $\Omega(\frac{\log N}{\log\log N})$ lower bound applies to $N\times N$ squares. At the same time, we demonstrate that there are some other shapes for which these generalizations allow reduced tile sets. Specifically, for thin rectangles with length N and width k, we provide a tighter lower bound of $\Omega(\frac{N^{1/k}}{k})$ for the standard model, yet we also give a construction which achieves $O(\frac{\log N}{\log\log N})$ complexity in a model in which the temperature of the tile system is adjusted during assembly. We also investigate the problem of verifying whether a given tile system uniquely assembles into a given shape; we show that this problem is NP-hard for three of the generalized models.

Current biological evidence suggests a correlation between the function and the position of genes in chromosomes. Examples include operon structure in prokaryotic genomes and similar expression patterns of neighboring genes in some eukaryotic genomes. In this paper, we present a new model and algorithm for identifying conserved gene clusters from pairwise genome comparison. This generalizes a recent model called "gene teams." A gene team is a set of orthologous genes that appear in two or more species, possibly in a different order yet with the distance of adjacent genes in the team for each chromosome always no more than a certain threshold. We remove the constraint in the original model that each gene must have a unique copy in the chromosomes, and thus allow the analysis on complex prokaryotic or eukaryotic genomes with extensive paralogs. Our algorithm runs in O(mn) time and uses O(m+n) space, where m and n are the number of common genes in each chromosomes. We used this approach to study two bacterial genomes, E. coli and B. subtilis and successfully identified 85 conserved clusters, including clusters containing uncharacterized genes and a large cluster consisting of 21 ribosomal proteins. Our implementation is publicly available at http://euler.slu.edu/~goldwasser/cogteams/.

We discuss our experiences in which students of a programming course were asked to submit both an implementation as well as a test set. A portion of a student's grade was then devoted both to the validity of a student's program on others' test sets, as well as how that student's test set performed in uncovering flaws in others' programs. The advantages are many, as this introduces implicit principles of software testing together with a bit of fun competition. The major complication is that such an all-pairs execution of tests grows quadratically with the number of participants, necessitating a fully automated scoring system.

We examine various complexity measures for two-handed assembly sequences. For many products there exists an exponentially large set of valid sequences, and a natural goal is to use automated systems to select wisely from the choices. Since assembly sequencing is a preprocessing phase for a long and expensive manufacturing process, any work towards finding a "better" assembly sequence is of great value when it comes time to assemble the physical product in mass quantities. We take a step in this direction by introducing a formal framework for studying the optimization of several complexity measures. This framework focuses on the combinatorial aspect of the family of valid assembly sequences, while temporarily separating out the specific geometric assumptions inherent to the problem. With an exponential number of possibilities, finding the true optimal cost solution is non-trivial. In the most general case, our results show that even finding an approximate solution is hard. Furthermore, we can show several hardness results, even in simple geometric settings. Future work is directed towards using this model to study how the original geometric assumptions can be reintroduced to prove stronger approximation results.

No abstract available.