UNO Gets Easier for a Single Player

This work is a follow up to 2, FUN 2010], which initiated a detailed analysis of the popular game of UNO (R). We consider the solitaire version of the game, which was shown to be NP-complete. In 2], the authors also demonstrate a (O)(n)(c(2)) algorithm, where c is the number of colors across all the cards, which implies, in particular that the problem is polynomial time when the number of colors is a constant. In this work, we propose a kernelization algorithm, a consequence of which is that the problem is fixed-parameter tractable when the number of colors is treated as a parameter. This removes the exponential dependence on c and answers the question stated in 2] in the affirmative. We also introduce a natural and possibly more challenging version of UNO that we call ``All Or None UNO''. For this variant, we prove that even the single-player version is NP-complete, and we show a single-exponential FPT algorithm, along with a cubic kernel.

Checking Liveness Properties of Presburger Counter Systems Using Reachability Analysis

Counter systems are a well-known and powerful modeling notation for specifying infinite-state systems. In this paper we target the problem of checking liveness properties in counter systems. We propose two semi decision techniques towards this, both of which return a formula that encodes the set of reachable states of the system that satisfy a given liveness property. A novel aspect of our techniques is that they use reachability analysis techniques, which are well studied in the literature, as black boxes, and are hence able to compute precise answers on a much wider class of systems than previous approaches for the same problem. Secondly, they compute their results by iterative expansion or contraction, and hence permit an approximate solution to be obtained at any point. We state the formal properties of our techniques, and also provide experimental results using standard benchmarks to show the usefulness of our approaches. Finally, we sketch an extension of our liveness checking approach to check general CTL properties.

A Brief Overview of the Recent Bio-Medical Applications of Fiber Bragg Grating Sensors

Fiber Bragg Grating (FBG) sensors have become one of the most widely used sensors in the recent times for a variety of applications in the fields of aerospace, civil, automotive, etc. It has been recently realized that FBGs and etched FBGs can play an important role in biomedical applications. This article provides a brief overview of the recent advancements in the application of FBG sensors in bio-mechanical, bio-sensing and bio-medical fields.

Microstructure-hardness-fretting wear resistance correlation in ultrafine grained Cu-TiB2-Pb composites

The retention of the desired combination of mechanical/tribological properties in ultrafine grained materials presents important challenges in the field of bulk metallic composites. In order to address this aspect, the present work demonstrates how one can achieve a good combination of hardness and wear resistance in Cu-Pb-TiB2 composites, consolidated by spark plasma sintering at low temperatures ( < 500 degrees C). Transmission electron microscope (TEM) studies reveal ultrafine grains of Cu (100-400 nm) with coarser TiB2 particles (1-2 mu m) along with fine scale Pb dispersoid at triple junctions or at the grain boundaries of Cu. Importantly, a high hardness of around 2.2 GPa and relative density of close to 90% relative density (rho(theo)) have been achieved for Cu-15 wt% TiB2-10 wt% Pb composite. Such property theo, combination has never been reported for any Cu-based nanocomposite, by conventional processing route. In reference to the tribological performance, fretting wear tests were conducted on the sintered nanocomposites and a good combination of steady state COF (0.6-0.7) and wear rate (10-4 mm(3)/N m) were measured. An inverse relationship between wear rate and hardness was recorded and this commensurates well with Archard's relationship of abrasive wear. The formation of a wear-resistant delaminated tribolayer consisting of TiB2 particles and ultrafine oxide debris, (Cu, Fe, Ti)(x)O-y as confirmed from subsurface imaging using focused ion beam microscopy has been identified as the key factors for the low wear rate of these composites. (C) 2014 Elsevier B.V. All rights reserved.

Room Temperature-Processed TiO2 MIM Capacitors for DRAM Applications

We report the room temperature fabrication of Ta/TiO2/Ta metal-insulator-metal (MIM) capacitors (mainly, for DRAM applications). The fabricated devices show high capacitance density (similar to 15 fF/mu m(2)), and low leakage current density of 6.4 X 10(-8) A/cm(2) (27 degrees C) and 3.3 x 10(-6) A/cm(2) (125 degrees C) at -1 V. We analyze the electrical and material characteristics of the fabricated capacitors, and compare the device performance of these capacitors with other TiO2 and TiO2-based MIM capacitors reported in recent literature.

Stress Engineering using Si3N4 for stiction free release of SOI beams

We report on the effect of thin silicon nitride (Si3N4) induced tensile stress on the structural release of 200nm thick SOI beam, in the surface micro-machining process. A thin (20nm / 100nm) LPCVD grown Si3N4 is shown to significantly enhance the yield of released beam in wet release technique. This is especially prominent with increase in beam length, where the beams have higher tendency for stiction. We attribute this yield enhancement to the nitride induced tensile stress, as verified by buckling tendency and resonance frequency data obtained from optical profilometry and laser doppler vibrometry.

Surface Enhanced Raman Scattering on Anodized Alumina Templates for Bio-sensing Applications

SERS substrate was fabricated by depositing silver on anodized aluminum oxide (AAO) template. The thickness of the AA0 template was 200 nm with 40 nm circular pore and 15 nm spacing. SERS effect was observed on these metal coated structures due to electric field enhancement around the edge of the pores. Para-Nitrophenol (pnp) solution of 10(-6) M concentration was detected which refers to an enhancement factor of 10(4).

Gold Catalyzed Plasma Assisted Growth of Germanium Nanoneedles

A systematic study of Gold catalyzed growth of Ge nanoneedles by PECVD at low temperatures (<400 degrees C) is presented. Morphology, growth rate and aspect ratio of the needles are studied as a function of power, gas flow rate and chamber pressure. Nanoneedles were grown at pre-defined positions with catalytic particles obtained by e-Beam Lithography and lift off. This opens up the possibility of using Ge Nano needles in photovoltaic, nanoelectronics and nanosensor device applications.

Conductivity Studies of Silver-, Potassium-, and Magnesium-Doped Hydroxyapatite

We report the electrical transport properties of silver-, potassium-, and magnesium-doped hydroxyapatites (HAs). While Ag+ or K+ doping to HA enhances the conductivity, Mg+2 doping lowers the conductivity when compared with undoped HA. The mechanism behind the observed differences in ionic conductivity has been discussed using the analysis of high-temperature frequency-dependent conductivity data, Cole-Cole plots of impedance data as well as on the basis of the frequency dependence of the imaginary part (M) of the complex electric modulus. The f(max) of modulus M decreased in silver- and potassium-doped samples in comparison with the undoped HA.

Prediction of Queue Waiting Times for Metascheduling on Parallel Batch Systems

Prediction of queue waiting times of jobs submitted to production parallel batch systems is important to provide overall estimates to users and can also help meta-schedulers make scheduling decisions. In this work, we have developed a framework for predicting ranges of queue waiting times for jobs by employing multi-class classification of similar jobs in history. Our hierarchical prediction strategy first predicts the point wait time of a job using dynamic k-Nearest Neighbor (kNN) method. It then performs a multi-class classification using Support Vector Machines (SVMs) among all the classes of the jobs. The probabilities given by the SVM for the class predicted using k-NN and its neighboring classes are used to provide a set of ranges of predicted wait times with probabilities. We have used these predictions and probabilities in a meta-scheduling strategy that distributes jobs to different queues/sites in a multi-queue/grid environment for minimizing wait times of the jobs. Experiments with different production supercomputer job traces show that our prediction strategies can give correct predictions for about 77-87% of the jobs, and also result in about 12% improved accuracy when compared to the next best existing method. Experiments with our meta-scheduling strategy using different production and synthetic job traces for various system sizes, partitioning schemes and different workloads, show that the meta-scheduling strategy gives much improved performance when compared to existing scheduling policies by reducing the overall average queue waiting times of the jobs by about 47%.

Parameterized Algorithms and Kernels for 3-Hitting Set with Parity Constraints

The 3-Hitting Set problem involves a family of subsets F of size at most three over an universe U. The goal is to find a subset of U of the smallest possible size that intersects every set in F. The version of the problem with parity constraints asks for a subset S of size at most k that, in addition to being a hitting set, also satisfies certain parity constraints on the sizes of the intersections of S with each set in the family F. In particular, an odd (even) set is a hitting set that hits every set at either one or three (two) elements, and a perfect code is a hitting set that intersects every set at exactly one element. These questions are of fundamental interest in many contexts for general set systems. Just as for Hitting Set, we find these questions to be interesting for the case of families consisting of sets of size at most three. In this work, we initiate an algorithmic study of these problems in this special case, focusing on a parameterized analysis. We show, for each problem, efficient fixed-parameter tractable algorithms using search trees that are tailor-made to the constraints in question, and also polynomial kernels using sunflower-like arguments in a manner that accounts for equivalence under the additional parity constraints.

Translation Induction on Indian Language Corpora Using Translingual Themes from Other Languages

Identifying translations from comparable corpora is a well-known problem with several applications, e.g. dictionary creation in resource-scarce languages. Scarcity of high quality corpora, especially in Indian languages, makes this problem hard, e.g. state-of-the-art techniques achieve a mean reciprocal rank (MRR) of 0.66 for English-Italian, and a mere 0.187 for Telugu-Kannada. There exist comparable corpora in many Indian languages with other ``auxiliary'' languages. We observe that translations have many topically related words in common in the auxiliary language. To model this, we define the notion of a translingual theme, a set of topically related words from auxiliary language corpora, and present a probabilistic framework for translation induction. Extensive experiments on 35 comparable corpora using English and French as auxiliary languages show that this approach can yield dramatic improvements in performance (e.g. MRR improves by 124% to 0.419 for Telugu-Kannada). A user study on WikiTSu, a system for cross-lingual Wikipedia title suggestion that uses our approach, shows a 20% improvement in the quality of titles suggested.