In this paper, we describe the design and preliminary evaluation of a hybrid desktop-handheld system developed to support individuals with aphasia, a disorder which impairs the ability to speak, read, write, or understand language. The system allows its users to develop speech communication through images and sound on a desktop computer and download this speech to a mobile device that can then support communication outside the home. Using a desktop computer for input addresses some of this population's difficulties interacting with handheld devices, while the mobile device addresses stigma and portability issues. A modified participatory design approach was used in which proxies, that is, speech-language pathologists who work with aphasic individuals, assumed the role normally filled by users. This was done because of the difficulties in communicating with the target population and the high variability in aphasic disorders. In addition, the paper presents a case study of the proxy-use participatory design process that illustrates how different interview techniques resulted in different user feedback.

No abstract available.

Aphasia is a cognitive disorder that impairs speech and language. From interviews with aphasic individuals, their caregivers, and speech-language pathologists, the need was identified for a daily planner that allows aphasic users to independently manage their appointments. We used a participatory design approach to develop ESI Planner (the Enhanced with Sound and Images Planner) for use on a PDA and subsequently evaluated it in a lab study. This methodology was used in order to achieve both usable and adoptable technology. In addition to describing our experience in designing ESI Planner, two main contributions are provided: general guidelines for working with special populations in the development of technology, and design guidelines for accessible handheld technology.

This research investigates the role of interface manipulation style on reflective cognition and concept learning through a comparison of the effectiveness of three verisons of a software application for learning two-dimensional transformation geometry. The three versions respectively utilize a Direct Object Manipulation (DOM) interface in which the user manipulates the visual representation of objects being transformed; a Direct Concept Manipulation (DCM) interface in which the user manipulates the visual representation of the transformation being applied to the object; and a Reflective Direct Concept Manipulation (RDCM) interface in which the DCM approach is extended with scaffolding. Empirical results of a study showed that grade-6 students using the RDCM version learned significantly more than those using the DCM version, who is turn learned significantly more than those using the DOM version. Students using the RDCM version had to process information consciously and think harder than those using the DCM and DOM versions. Despite the relative difficulty when using the RDCM interface style, all three groups expressed a similar (positive) level of liking for the software. This research suggests that some of the educational deficiencies of Direct Manipulation (DM) interfaces are not necessarily caused by their “directness,” but by what they are directed at—in this case directness toward objects rather than embedded educational concepts being learned. This paper furthers our understanding of how the DM metaphor can be used in learning- and knowledge-centered software (i.e., learnware) by proposing a new DM metaphor (i.e., DCM), and the incorporation of scaffolding to enhance the DCM approach to promote reflective cognition and deep learning.

This paper studies the long-standing open question of whether optimal alphabetic binary trees can be constructed in $o( n\lg n )$ time. We show that a class of techniques for finding optimal alphabetic trees which includes all current methods yielding $O( n\lg n )$-time algorithms are at least as hard as sorting in whatever model of computation is used. We also give $O( n )$-time algorithms for the case where all the input weights are within a constant factor of one another and when they are exponentially separated.

A tight lower bound is proved on the minimum number of vertices in a planar graph in which any permutation between t distinguished vertices can be realized by vertex disjoint paths.

We give a new Ο(n log log n)-time deterministic linear-time algorithm for triangulating simple n-vertex polygons, which avoids the use of complicated data-structures. In addition, for polygons whose vertices have integer coordinates of polynomially bounded size, the algorithm can be modified to run in Ο(n log* n) time. The major new techniques employed are the efficient location of horizontal visibility edges which partition the interior of the polygon into regions of approximately equal size, and a linear-time algorithm for obtaining the horizontal visibility partition of a subchain of a polygonal chain, from the horizontal visibility partition of the entire chain. This latter technique has other interesting applications, including a linear-time algorithm to convert a Steiner triangulation of a polygon into a true triangulation.

An $O( m\alpha ( n ) + n )$ time algorithm is given for finding row-maxima and minima in totally monotone partial $n \times n$ matrices. As a result, faster algorithms are obtained for some optimization problems concerning distance and visibility between vertices of two convex polygons. Also shown is how the algorithm can be modified to give an $O( n \alpha ( n ) )$ algorithm for a class of dynamic programming problems satisfying convex quadrangle inequalities. This results in faster algorithms for a number of problems arising in molecular biology, speech recognition, and geology.

Article Free Access Share on Geometric applications of a matrix searching algorithm Authors: A Aggarwal IBM T. J. Watson Center, Yorktown Heights IBM T. J. Watson Center, Yorktown HeightsSearch about this author , M Klawe IBM Almaden Research Center, San Jose IBM Almaden Research Center, San JoseView Profile , S Moran IBM T. J. Watson Center, Yorktown Heights IBM T. J. Watson Center, Yorktown HeightsSearch about this author , P Shor Math. Sciences Research Institute, Berkeley Math. Sciences Research Institute, BerkeleyView Profile , R Wilber IBM Almaden Research Center, San Jose IBM Almaden Research Center, San JoseView Profile Authors Info & Claims SCG '86: Proceedings of the second annual symposium on Computational geometryAugust 1986Pages 285–292https://doi.org/10.1145/10515.10546Published:01 August 1986Publication History 39citation1,255DownloadsMetricsTotal Citations39Total Downloads1,255Last 12 Months234Last 6 weeks35 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

Problems in circuit fan-out reduction motivate the study of constructing various types of weighted trees that are optimal with respect to maximum weighted path length. An upper bound on the maximum weighted path length and an efficient construction algorithm will be presented for trees of degree at most t, along with their implications for circuit fan-out reduction.

In this paper we propose two new multi-layer grid models for VLSI layout, both of which take into account the number of contact cuts used. For the first model in which nodes "exist" only on one layer, we prove a tight area x (number of contact cuts) = Θ(n2) trade-off for embedding any degree 4 n-node planar graph in two layers. For the second model in which nodes "exist" simultaneously on all layers, we prove a number of bounds on the area needed to embed graphs using no contact cuts. For example we prove that any n-node graph which is the union of two planar subgraphs can be embedded on two layers in O(n2) area without contact cuts. This bound is tight even if more layers and an unbounded number of contact cuts are allowed. We also show that planar graphs of bounded degree can be embedded on two layers in O(n1.6) area without contact cuts. These results use some interesting new results on embedding graphs in a single layer. In particular we give an O(n2) area embedding of planar graphs such that each edge makes a constant number of turns, and each exterior vertex has a path to the perimeter of the grid making a constant number of turns. We also prove a tight Ω(n3) lower bound on the area of grid n-permutation networks.

Lengauer and Tarjan proved that the number of black and white pebbles needed to pebble the root of a tree is at least half the number of black pebbles needed to pebble the root. This result is extended to a larger class of acyclic directed graphs including pyramid graphs.

This paper concerns the following problem. Given vertices $v_1 , \cdots ,v_n $ with weights $w_1 , \cdots ,w_n $, construct a t-ary tree with leaves $v_1 , \cdots ,v_n $ in left to right order, such that if $l_i $ denotes the length of the path from $v_i $ to the root for each i, the maximum of $w_i + l_i $ is minimized. A linear algorithm is presented for the case where all the weights are integers, and this is used to obtain an $O(n\log n)$ algorithm for the case of general weights. Moreover it is shown that the minimax value obtained is bounded above by $2 + \log _t (\sum {t^{(w_i )} } )$. This result has applications in the study of the effect of fan-out constraints in logical circuits.

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with πk-formula of size n for which every σk-formula has size exp ω(n1/(k−1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a σk-formula of size exp o(n1/(k−1)). Thus our hierarchy theorem is the best possible.

Algorithms are presented which modify logical networks of bounded fan-in to obtain functionally equivalent networks of bounded fan-m and fan-out, so that both size and depth are not increased by more than constant factors.

Expanding graphs are the basic building blocks in constructions of many types of graphs with special connectivity properties which arise in a variety of applications including switching networks, sorting networks and establishing time-space trade-offs for numerous computational problems. Only one explicit method of constructing arbitrarily large expanding graphs with a linear number of edges is known (Margulis [13], Gabber and Galil [8]), but the number of edges used is much greater than the number known to be sufficient via probabilistic arguments. In this paper we show that various other constructions which have been proposed to obtain expanding graphs, including one-dimensional analogues of the Gabber–Galil construction and some pseudorandom constructions, cannot ever yield expanding graphs.

Lengauer and Tarjan proved that the number of black and white pebbles needed to pebble the root of a tree is at least 1/2 the number of black pebbles needed to pebble the root. We extend this result to a larger class of acyclic directed graphs including pyramid graphs.

Expanding graphs are the basic building blocks used in constructions of graphs with special connectivity properties such as superconcentrators. The only known explicit method (Margulis[7], Gabber and Galil[5]) of constructing arbitrarily large expanding graphs with a linear number of edges, uses graphs whose edges are defined by a finite set of linear mappings restricted to a two-dimensional set, Zn × Zn, where Zn denotes the integers mod n. In this paper we prove that for any finite set of onedimensional linear mappings with rational coefficients, the graph they define by their restriction to Zn is not an expanding graph. We also show that shuffle exchange graphs can not be expanding graphs.