This paper presents a new sensing and interaction environment for post-stroke and upper extremity limb rehabilitation. The device is a combination of camera-based multitouch sensing and a supporting therapeutic software application that advances the treatment, provides feedback, and records a user's progress. The image-based analysis of hand position provided by a Microsoft Surface is used as an input into a tabletop game environment. Tailored image analysis algorithms assess rehabilitative hand movements. Visual feedback is provided in a game context. Experiments were conducted in a sub-acute rehabilitation center. Preliminary user studies with a stroke-afflicted population determined essential design criteria. Hand and wrist sensing, as well as the goals of the supporting game environment, engage therapeutic flexion and extension as defined by consulted physicians. Participants valued personalization of the activity, novelty, reward and the ability to work at their own pace in an otherwise repetitive therapeutic task. A "character" - game element personifying the participant's movement - was uniquely motivating relative to the media available in the typical therapeutic routine.

This paper compares several models for student software engineering projects. We discuss our experience using projects for external customers, using computer game projects, and finally using game projects for external customers, specifically middle school teachers. We discuss the problems we encountered with the first two approaches and how they are solved with our current model.

Computer games are widely used as pedagogical tools in the classroom. In recent years, the use of game projects in Computer Science (CS) curriculum has grown in popularity. The Muddy Hill Games project marries these ideas by engaging CS students in the design and development of educational games for middle school students. This approach enhances the game projects by providing a real customer and users. It results in free educational software that serves middle school learning objectives. Finally, it informs middle school students' understanding of Computer Science and motivates interest in the field. Here we describe four games that have come out of the project.

Recruitment of students to Computer Science has been a major focus of effort for educators since the dot-com bust in 2001. Two largely disparate themes in these efforts are women and games. There have been numerous efforts to broaden participation in computer science by attracting women to the field. At the same time, games are increasingly used to attract new students. Our interest lies at the intersection of these methods. We began using game design/development projects in our software engineering course, CS121, in 2002. The game focus was extremely successful with many of our students. But a nagging minority of students objected to building games, and women tend to be overrepresented in that group.So while are awed by the power of games to engage and motivate many of our students, we need to ask: Do games in our curriculum reinforce gender stereotypes of Computer Science? Do they foster development of the so-called Geek mythology?[7] In short, must we choose: women or games?We argue the answer is no. While traditional game projects may disenfranchise women, our experience shows that serious game projects both attract and engage them. This paper describes our results.

Computer and video games have grown to be a major industry but, until recently, have largely been ignored by academia. The last couple of years, however, have seen the emergence of new academic programs, conferences, and journals dedicated to games studies. For the past three years we have used computer games as projects in our introductory software engineering course. Small teams of students build three games across the semester. In this paper we describe the course and discuss its success.

Computer and video games have grown to be a major industry but, until recently, have largely been ignored by academia. The last couple of years, however, have seen the emergence of new academic programs, conferences, and journals dedicated to games studies. This panel discusses a variety of ways, and whys, for introducing games into computer science curricula. Panelists discuss their experiences in designing a broad range of courses including a games course for women, a software development course that uses games as projects, an introductory games programming course in Java, and an advanced graphics course that focuses on games.

Job-shop scheduling is a classical NP-hard problem. Shmoys, Stein, and Wein presented the first polynomial-time approximation algorithm for this problem that has a good (polylogarithmic) approximation guarantee. We improve the approximation guarantee of their work and present further improvements for some important NP-hard special cases of this problem (e.g., in the preemptive case where machines can suspend work on operations and later resume). We also present NC algorithms with improved approximation guarantees for some NP-hard special cases.

Given a set of strings S={s 1 ,s 2 . . . ,s n } over a finite alphabet $\Sigma$, a superstring of S is a string that contains each s i as a contiguous substring. The shortest superstring (SS) problem is to find a superstring of minimum length. This problem has important applications in computational biology and in data compression (see, respectively, [A. Lesk, ed., Computational Molecular Biology, Sources and Methods for Sequence Analysis, Oxford University Press, Oxford, 1988]; [J. Storer, Data Compression: Methods and Theory, Computer Science Press, Rockville, MD, 1988]). SS is MAX SNP-hard [A. Blum et al., Proc. 23rd Annual ACM Symposium on Theory of Computing, ACM, New York, 1991, pp. 328--336] so it is unlikely that the length of a shortest superstring can be approximated to within an arbitrary constant. Several heuristics have been suggested and it is conjectured that GREEDY achieves an approximation factor of 2. This, unfortunately, remains an open question. Several linear approximation algorithms for SS have been proposed. The first, by Blum et al. [ Proc. 23rd Annual ACM Symposium on Theory of Computing, ACM, New York, 1991, pp. 328--336], guarantees a performance factor of 3. The factor has been successively improved to $2\frac{8}{9}$, $2 \frac{5}{6}$, $2 \frac{50}{63}$, $2 \frac{3}{4}$, $2\frac{2}{3}$, and $2.596$ (see, respectively, [S. Teng and F. Yao, Proc. 34th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Piscataway, NJ, 1993, pp. 158--165]; [A. Czumaj et al., Proc. First Scandinavian Workshop on Algorithm Theory, Lecture Notes in Comput. Sci. 824, Springer-Verlag, Berlin, 1994, pp. 95--106]; [R. Kosaraju, J. Park, and C. Stein, Proc. 35th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Piscataway, NJ, 1994, pp. 166--177]; [C. Armen and C. Stein, Proc. 5th Internat. Workshop on Algorithms and Data Structures, Lecture Notes in Comput. Sci. 955, Springer-Verlag, Berlin, 1995, pp. 494--505]; [C. Armen and C. Stein, Proc. Combinatorial Pattern Matching, Lecture Notes in Comput. Sci. 1075, Springer-Verlag, Berlin, 1996, pp. 87--101]; and [D. Breslauer, T. Jiang, and Z. Jiang, J. Algorithms, 24 (1997), pp. 340--353]). In this paper we give an algorithm that guarantees a $2\frac{1}{2}$-approximation factor.

The paper studies the computational complexity and approximation algorithms for a new evolutionary distance between multi-chromosomal genomes introduced recently by Ferretti, Nadeau and Sankoff. Here, a chromosome is represented as a set of genes and a genome is a collections of chromosomes. The syntenic distance between two genomes is defined as the minimum number of translocations, fusions and fissions required to transform one genome into the other. We prove that computing the syntenic distance is NP-hard and give a simple approximation algorithm with performance ratio 2. For the case when an upper bound d on the syntenic distance is known, we show that an optimal syntenic sequence can be found in O(nk + 2o(d2)) time, where n and k are the number of chromosomes in the two given genomes. Next, we show that if the set of operations for transforming a genome is significantly restricted, we can nevertheless find a solution that performs at most O(log d) additional moves, where d is the number of moves performed by the unrestricted optimum. This result should help in the design of approximation algorithms. Finally, we investigate the median problem: Given three genomes, construct a genome minimizing the total syntenic distance to the three given genomes and compute the corresponding median distance. The problem has application in the inference of phytogenies based on the syntenic distance. We prove that the problem is NP-hard and design a polynomial time approximation algorithm with a performance ratio of 4+ε for any constant ε > 0.

Article Free Access Share on On the complexity and approximation of syntenic distance Authors: B. DasGupta Department of Computer Science, Rutgers University, Camden, NJ Department of Computer Science, Rutgers University, Camden, NJView Profile , T. Jiang Department of Computer Science, McMaster University, Hamilton, Ontario L8S 4K1, Canada Department of Computer Science, McMaster University, Hamilton, Ontario L8S 4K1, CanadaView Profile , S. Kannan Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PAView Profile , M. Li Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong Department of Computer Science, City University of Hong Kong, Kowloon, Hong KongView Profile , Z. Sweedyk Department of Computer and Information Sciences, University of Pennsylvania, Philadelphia, PA Department of Computer and Information Sciences, University of Pennsylvania, Philadelphia, PAView Profile Authors Info & Claims RECOMB '97: Proceedings of the first annual international conference on Computational molecular biologyJanuary 1997 Pages 99–108https://doi.org/10.1145/267521.267536Published:19 January 1997Publication History 6citation243DownloadsMetricsTotal Citations6Total Downloads243Last 12 Months11Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A quasi-polynomial-time algorithm is presented for sampling almost uniformly at random from then-slice of the languageL(G) generated by an arbitrary context-free grammarG. (Then-slice of a languageLover an alphabetΣis the subsetL∩Σnof words of length exactlyn.) The time complexity of the algorithm isε−2(n |G|)O(log n)where the parameterεbounds the variation of the output distribution from uniform, and |G| is a natural measure of the size of grammarG. The algorithm applies to a class of language sampling problems that includes slices of context-free languages as a proper subclass. For the restricted case of homogeneous languages expressed by regular expressions without Kleene-star, a truly polynomial-time algorithm is presented.

Inferring phylogenetic trees is a fundamental problem in computational biology. We present a new objective criterion, the phylogenetic number, for evaluating evolutionary trees for species defined by biomolecular sequences or other qualitative characters. The phylogenetic number of a tree T is the maximum number of times that any given character state arises in T. By contrast, the classical parsimony criterion measures the total number of times that different character states arise in T. We consider the following related problems: finding the tree with minimum phylogenetic number, and computing the phylogenetic number of a given topology in which only the leaves are labeled by species. When the number of states is bounded (as is the case for biomolecular sequence characters), we can solve the second problem in polynomial time. Given the topology for an evolutionary tree, we can also compute a phylogeny with phylogenetic number 2 (when one exists) for an arbitrary number of states. This algorithm can be used to further distinguish trees that are equal under parsimony. We also consider a number of other related problems.

We prove the following about the Nearest Lattice Vector Problem (in any l/sub p/ norm), the Nearest Code-word Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems. 1. Approximating the optimum within any constant factor is NP-hard. 2. If for some /spl epsiv/>0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2/sup log(0.5-/spl epsiv/)/ /sup n/ then NP is in quasi-polynomial deterministic time: NP/spl sube/DTIME(n/sup poly(log/ /sup n)/). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l/sub /spl infin// norm. Improving the factor 2/sup log(0.5-/spl epsiv/)/ /sup n/ to /spl radic/(dim) for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l/sub 2/ norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems, either directly, or through a set-cover problem.>