Individuals, institutions and even cities and countries are often ranked according to some linear weighting of their attributes. Under commonly prevailing conditions, it is possible to find weights that give top rank to most arbitrarily designated entries. The number of entries may exceed the number of attributes by orders of magnitude. Necessary and sufficient conditions on the subject-attribute matrix are derived in terms of one-against-all halfplane dichotomies and convex hulls. Pairwise attribute difference vectors are more effective than attribute vectors for one-against-all classification. Comparisons of MeFirst algorithms based on neural networks and on linear programming (LP), on datasets drawn from published rankings of scientists and universities, show that on these tasks, LP is significantly faster.

Many computer science programs have capstone experiences or project courses that allow students to integrate knowledge from the full breadth of their major. Such capstone projects may be student-designed, instructor-designed, designed in conjunction with outside companies, or integrated with ongoing free and open source (FOSS) projects. The literature shows that the FOSS approach has attracted a great deal of interest, in particular when implemented with projects that have humanitarian goals (HFOSS). In this article, we describe five unique models from five distinct types of institutions for incorporating sustained FOSS or HFOSS (alternatively H/FOSS) project work into capstone experiences or courses. The goal is to provide instructors wishing to integrate open source experiences into their curriculum with additional perspectives and resources to help in adapting this approach to the specific needs and goals of their institution and students. All of the models presented are based on sustained engagement with H/FOSS projects that last at least one semester and often more. Each model is described in terms of its characteristics and how it fits the needs of the institution using the model. Assessment of each model is also presented. We then discuss the themes that are common across the models, such as project selection, team formation, mentoring, and student assessment. We examine the choices made by each model, as well as the challenges faced. We end with a discussion how the models have leveraged institutional initiatives and collaborations with outside organizations to address some of the challenges associated with these projects.

We present a method based on header paths for efficient and complete extraction of labeled data from tables meant for humans. Although many table configurations yield to the proposed syntactic analysis, some require access to semantic knowledge. Clicking on one or two critical cells per table, through a simple interface, is sufficient to resolve most of these problem tables. Header paths, a purely syntactic representation of visual tables, can be transformed ("factored") into existing representations of structured data such as category trees, relational tables, and RDF triples. From a random sample of 200 web tables from ten large statistical web sites, we generated 376 relational tables and 34,110 subject-predicate-object RDF triples.

This article describes the use of fractal simulations of African design in a high school computing class. Fractal patterns---repetitions of shape at multiple scales---are a common feature in many aspects of African design. In African architecture we often see circular houses grouped in circular complexes, or rectangular houses in rectangular complexes. Typically the accompanying ceremonies, cosmologies, and other traditions make use of scaling and recursion in their conceptual models. African scaling designs include textiles, sculpture, adornment, and other forms; in many cases there are explicit geometric algorithms and other formal aspects (e.g., pseudorandom number generation in divination systems) embedded in the associated indigenous knowledge system. Thus African fractals provide a strong counter to stereotypes of African culture as primitive or simplistic. Following this fieldwork, we developed a Web site which uses Java simulations of these African designs to teach computational perspectives on fractals to high school students.1We hypothesized that this combination of anti-primitivist “ethnocomputing” and design-based creative learning would enhance both the engagement and performance of under-represented students in computing. A quasi-experimental study used two 10th grade computing classes, both taught by the same instructor, and both including more than 50% under-represented students (Latino and African American). The control class received six days of instruction using a popular Web site (with Java applets but no cultural content or design activities) for high school fractal lessons; the experimental class received the same amount of instruction using our Web site. Pre/post differences on both achievement and attitude tests indicate statistically significant improvement for the students in the experimental class. Potential implications for improving participation and achievement of under-represented students in computing education are discussed.

We describe a component of a document analysis system for constructing ontologies for domain-specific web tables imported into Excel. This component automates extraction of the Wang Notation for the column header of a table. Using column-header specific rules for XY cutting we convert the geometric structure of the column header to a linear string denoting cell attributes and directions of cuts. The string representation is parsed by a context-free grammar and the parse tree is further processed to produce an abstract data-type representation (the Wang notation tree) of each column category. Experiments were carried out to evaluate this scheme on the original and edited column headers of Excel tables drawn from a collection of 200 used in our earlier work. The transformed headers were obtained by editing the original column headers to conform to the format targeted by our grammar. Forty-four original headers and their reformatted versions were submitted as input to our software system. Our grammar was able to parse and the extract Wang notation tree for all the edited headers, but for only four of the original headers. We suggest extensions to our table grammar that would enable processing a larger fraction of headers without manual editing.

Influenza Pandemic of 1957-1958, also called Asian Flu Pandemic, was one of the most widespread pandemics in history. In this paper, we model the pandemic, considering the effect of the Cold War. There were some restrictions between Western and Eastern nations due to the Cold War during the pandemic. We expect that such restrictions influenced the spread of the pandemic. We propose a hybrid model to determine how the pandemic spread through the world. The model combines the SEIR-based model for local areas and the network model for global connection between countries. First, we reproduce the situation in 19 countries. Then, we run another experiment to find the influence of the war in the spread of the pandemic, simulation considering international relationships in different years. The simulation results show that the impact of the pandemic in each country was much influenced by international relationships. This study indicates that if there was less effect of the Cold War, Western nations would have larger number of death cases, Eastern nations would have smaller number of death cases, and the world impact would be increased somewhat.

Amazon.com is among the largest bookstores on the internet. It provides the sales rank of each book. Our hypothesis is as follows: if a book has low sales rank (i.e., it is well-sold), the related book also has a low sales rank. In the small world principle, if a network is connected, any two nodes are connected with relatively small number of links. If this hypothesis is true, any book can link to a bestseller book with small number of distance by linking some related books. In this paper, we design an algorithm to ascertain our hypothesis, and analyze the network structure of Amazon.com.

Collaborative Filtering is one of the most widely used approaches in recommendation systems which predicts user preferences by learning past user-item relationships. In recent years, item-oriented collaborative filtering methods came into prominence as they are more scalable compared to user-oriented methods. Item-oriented methods discover item-item relationships from the training data and use these relations to compute predictions. In this paper, we propose a novel item-oriented algorithm, Random Walk Recommender, that first infers transition probabilities between items based on their similarities and models finite length random walks on the item space to compute predictions. This method is especially useful when training data is less than plentiful, namely when typical similarity measures fail to capture actual relationships between items. Aside from the proposed prediction algorithm, the final transition probability matrix computed in one of the intermediate steps can be used as an item similarity matrix in typical item-oriented approaches. Thus, this paper suggests a method to enhance similarity matrices under sparse data as well. Experiments on MovieLens data show that Random Walk Recommender algorithm outperforms two other item-oriented methods in different sparsity levels while having the best performance difference in sparse datasets.

Abstract Keyword‐based search engines such as Google™ index Web pages for human consumption. Sophisticated as such engines have become, surveys indicate almost 25% of Web searchers are unable to find useful results in the first set of URLs returned (Technology Review, March 2004). The lack of machine‐interpretable information on the Web limits software agents from matching human searches to desirable results. Tim Berners‐Lee, inventor of the Web, has architected the Semantic Web in which machine‐interpretable information provides an automated means to traversing the Web. A necessary cornerstone application is the search engine capable of bringing the Semantic Web together into a searchable landscape. We implemented a Semantic Web Search Engine (SWSE) that performs semantic search, providing predictable and accurate results to queries. To compare keyword search to semantic search, we constructed the Google CruciVerbalist (GCV), which solves crossword puzzles by reformulating clues into Google queries processed via the Google API. Candidate answers are extracted from query results. Integrating GCV with SWSE, we quantitatively show how semantic search improves upon keyword search. Mimicking the human brain's ability to create and traverse relationships between facts, our techniques enable Web applications to ‘think’ using semantic reasoning, opening the door to intelligent search applications that utilize the Semantic Web. Copyright © 2007 John Wiley & Sons, Ltd.

We describe a new model for evaluating similarities among a large number of web logs, and compare several algorithms using the model. Possible uses of this include isolating and tracking like-minded networks for surveillance and improved categorization. Our model consists of similarity analysis combined with clustering. Experimental results show that our algorithm is able to separate blogs into categories, consistently achieving over 90% success rate.

Recent works in spatial data clustering view the input data set in terms of inter-point edge lengths rather than the points themselves. Cluster detection in such a system is a matter of finding connected paths of edges whose weight is no greater than some user input threshold or cutoff value. The SMTIN algorithm[9] is one such system that uses Delaunay triangulation to compute the set of nearest neighbor edges quickly and efficiently. Experiments demonstrate a substantial performance and accuracy improvement using SMTIN in comparison to other clustering systems.

Emerging technologies on the World Wide Web promise to make program, algorithm and concept simulations universally accessible. Simulations involving animation and visualization have a tremendous benefit when applied to various algorithms. We present a simulation tool for experimenting with concepts in fuzzy clustering that has proved useful in visualizing the results and demonstrating the computation method of the algorithms. This is especially advantageous in a classroom or laboratory setting where students may become more comfortable with the mechanics of fuzzy clustering through personal discovery and online experimentation.

Emerging technologies on the World Wide Web promise to make program, algorithm and concept simulations universally accessible, and Java appears to be the best technology available. Simulations involving animation and visualization have a tremendous benefit when applied to various algorithms. We present a simulation tool for experimenting with concepts in fuzzy clustering that has proved useful in visualizing the results and demonstrating the computation method of the algorithms. This is an asset when working with people unfamiliar with the mechanics of fuzzy clustering, such as non-computer scientists or students. This system was integral in the development of an algorithm capable of locating an unknown number of clusters embedded in background noise. © 1997 John Wiley & Sons, Ltd.

As Multichip Modules (MCMs) evolve from niche solutions to necessary ingredients of high performance computing systems, this change must be reflected in the associated CAD tools for MCM system design. Given the transmission velocities of modern thin film substrates, conventional design techniques where chips are developed in isolation from the substrate fall short of producing optimal solutions. Critical to the success of these tools is the ability to influence chip pad placement. Our research indicates that an integrated chip/MCM codesign environment should be established. MCM CAD tools must provide advice for and accommodate an interactive pad migration facility, where chip designers are provided recommended signal pad locations that contribute to the optimization of the overall system.

this paper discusses only its application to switch statements. There has been considerable work in the past ([2], [3], [5], [6] and [10]) on the Pascal case statement and code generation. The generation of code for switch statements is discussed in [4] and [11]. A scheme similar to MRST, but restricted to binary radix search trees, appears in [9]. Preprint submitted to Elsevier Preprint 8 August 1997 Applications for fast sparse switch statements are many and varied. Two examples are: -- Let L be a Common-Lisp-like language with dynamic type dispatch on function arguments. Let F be an n argument generic function in L, with

N-tuple features for optical character recognition have received only scattered attention since the 1960s. Our main purpose is to show that advances in computer technology and computer science compel renewed interest. N-tuple features are useful for printed character classification because they indicate the presence or absence of a given rigid configuration of n black and white pixels in a pattern. Desirable n-tuples fit each pattern of a specified (positive) training set of characters in at least p different shift positions, and fail to fit each pattern of a specified (negative) training set by at least n-q pixels in each shift position. We prove that the problem of finding a distinguishing n-tuple is NP-complete, by examining a natural subproblem with binary strings called the missing configuration problem. The NP-completeness result notwithstanding, distinguishing n-tuples are found automatically in a few seconds on contemporary workstations. We exhibit a practical search algorithm for generating, from a small training set, a collection of n-tuples with low class-conditional correlation and with specified design parameters n, p, and q. The generator, which is available on the Internet, is empirically shown to be effective through a comparison with a benchmark generator. We show experimentally that the design parameters provide a useful tradeoff between distinguishing power and generation time, and also between the conditional probabilities for the positive and negative classes. We explore the feature probabilities obtainable for various dichotomies, and show that the design parameters control the feature probabilities.

We develop a strategy for extracting the underlying relational information from the images of printed tables. Visual clues that exist in the image are used for extracting first the physical, and then the logical structure of the table. Since these visual clues generally have a logical meaning, there must be some association made between the graphical attributes extracted and their function of reflecting the logic expressed by the table; this knowledge is coordinated in a model. This approach, therefore, can be adapted to all tables which have graphical attributes discernible to the image analysis being used.

The software package of Audio Formatting of a Graph (AFG) is primarily designed for people who are visually challenged to study graph theory. It is menu-driven so that a user can get information about a graph easily and conveniently.

MCM designs require independent analysis in loosely coupled but interrelated design regimes. This paper proposes wiring pitch as the unifying thread in a real time iterative design environment that facilitates analysis in all pertinent domains. Actual system results demonstrate the strengths of the technique.>

Recently published findings indicate that full differential routing of both VLSI chips and MCMs may be necessary to preserve noise margins in high performance systems. The optimal differential routing technique relies on routing signal pairs as logical nets and bifurcating the results to achieve a physical realization. Based on our research, CIF (Caltech. Interchange Format) has emerged as the ideal medium for the bifurcation process associated with differential routing of MCMs. Since MCMs have not as yet fully come of age, many of their design variables are under constrained. One of the greatest strengths of our finding is CIF's ability to handle the design uncertainty associated with current MCM system development, where both package and chip specification are typically in a tremendous state of flux throughout the engineering design cycle.>

A method for extracting alternating horizontal and vertical projection profiles are from nested sub-blocks of scanned page images of technical documents is discussed. The thresholded profile strings are parsed using the compiler utilities Lex and Yacc. The significant document components are demarcated and identified by the recursive application of block grammars. Backtracking for error recovery and branch and bound for maximum-area labeling are implemented with Unix Shell programs. Results of the segmentation and labeling process are stored in a labeled x-y tree. It is shown that families of technical documents that share the same layout conventions can be readily analyzed. Results from experiments in which more than 20 types of document entities were identified in sample pages from two journals are presented.>

Abstract This paper proposes graphics primitives for constructing programs for algorithm animation. Our experiments show that these primitives can reduce program development time. Future directions of the current research is also discussed.

We consider the gate matrix layout problem for VLSI circuits, which is known to be NP-complete. We present an efficient algorithm for determining whether two tracks suffice. For the general problem of minimizing the number of tracks (and, hence, the area) needed, we design an attractive dynamic programming formulation to guarantee optimality. We also investigate the performance of fast heuristic algorithms published in the literature and demonstrate that there exist families of problem instances for which the ratio of the number of tracks required by these heuristics to the optimal value is unbounded. Moreover, we show that this result holds for any on-line layout algorithm. We additionally prove that, unless P = NP, no polynomial-time layout algorithm can ensure that the number of tracks it requires never exceeds k plus the optimum, for any constant k.

The following problem is considered: Given an undirected, connected graph G, find a spanning tree in G such that the sum of the lengths of the fundamental cycles (with respect to this tree) is minimum.This problem, besides being interesting in its own right, is useful in a variety of situations It is shown that this problem is NP-complete.A number of polynomial-time, heuristic algorithms which yield "good" suboptimal solutions are presented and their performances are discussed.Finally, it is shown that for regular graphs of order n the expected value of the total length of a minimum fundamentalcycle set does not exceed O(n2).

Abstract Any complex project consists of a number of activities which are carried out in some specified precedence order. One of the factors that is considered is in minimizing the project completior, time. The computation of the optimum project completion time is proportional to the number of edges, including dummy activities. In the past, many algorithms were proposed to yield minimum number of dummy activities required to satisfy the given precedence relation. In this paper we transform the node‐cover problem in graphs of degree at most 3 to the minimum‐dummy‐activities problem. Using this transformation we show that the minimum‐dummy‐activities problem in a PERT network is NP‐complete. The significance of this result is that it is worthwhile in developing a polynomial time heuristic algorithm for solving the dummy activities problem.

The entire class of node-deletion problems can be stated as follows: Given a graph G, find the minimum number of nodes to be deleted so that the remaining subgraph g satisfies a specified property $\pi $. For each $\pi $, a distinct node-deletion problem arises. The various deletion problems considered here are for the following properties: each component of g is (i) null, (ii) complete, (iii) a tree, (iv) nonseparable, (v) planar, (vi) acyclic, (vii) bipartite, (viii) transitive, (ix) Hamiltonian, (x) outerplanar, (xi) degree-constrained, (xii) line invertible, (xiii) without cycles of a specified length, (xiv) with a singleton K-basis, (xv) transitively orientable, (xvi) chordal, and (xvii) interval. In this paper, these 17 different node-deletion problems are shown to be NP-complete. A unified approach is taken for the transformations employed in the proofs.