Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

A New Liquid Level Sensor for Process-Control Applications

Many process-control systems are air-operated. In such an environment, it would be desirable and economical to use pneumatic sensors. Bubble-back pressure sensors perform quite satisfactorily, but in case of viscous inflammable and slurry-like liquids with a tendency to froth, this level sensor is inadequate. The method suggested in this paper utilizes a pneumatic capacitor, one boundary of which is formed by the liquid level, to modulate a fluid amplifier feedback oscillator. The absence of moving parts and economy obtained makes this method attractive for process-control applications. The system has been mathematically modeled and simulated on an IBM 360/44 digital computer. Experimental values compare fairly well with the theoretical results. For the range tested, the sensor is found to have a linear frequency variation with the liquid level Extended running in the laboratory shows that the system is very reliable. This system has been found insensitive to temperature variations of up to 15ðC.

Mechanical Properties of Al-Mica Particulate Composite Material

Cast aluminium alloy mica particle composites of varying mica content were tested in tension, compression, and impact. With 2.2 percent mica (size range 40µm – 120µm) the tensile and compression strengths of aluminium alloy decreased by 56 and 22 percent, respectively. The corresponding decreases in percent elongation and percent reduction are 49 and 39 percent. Previous work [2] shows that despite this decrease in strength the composite with 2.5 percent mica and having an UTS of 15 kg/mm2 and compression strength of 28 kg/mm2 performs well as a bearing material under severe running conditions. The differences in strength characteristics of cast aluminium-mica particle composites between tension and compression suggests that, as in cast iron, expansion of voids at the matrix particle interface may be the guiding mechanism of the deformation. SEM studies show that on the tensile fractured specimen surface, there are large voids at the particle matrix interface.

Maximum-entropy calculation of the electron density at 4 A resolution of Pf1 filamentous bacteriophage

A 4 A electron-density map of Pf1 filamentous bacterial virus has been calculated from x-ray fiber diffraction data by using the maximum-entropy method. This method produces a map that is free of features due to noise in the data and enables incomplete isomorphous-derivative phase information to be supplemented by information about the nature of the solution. The map shows gently curved (banana-shaped) rods of density about 70 A long, oriented roughly parallel to the virion axis but slewing by about 1/6th turn while running from a radius of 28 A to one of 13 A. Within these rods, there is a helical periodicity with a pitch of 5 to 6 A. We interpret these rods to be the helical subunits of the virion. The position of strongly diffracted intensity on the x-ray fiber pattern shows that the basic helix of the virion is right handed and that neighboring nearly parallel protein helices cross one another in an unusual negative sense.

Armchair or Zigzag? A tool for characterizing graphene edge

Electronic, magnetic, and structural properties of graphene flakes depend sensitively upon the type of edge atoms. We present a simple software tool for determining the type of edge atoms in a honeycomb lattice. The algorithm is based on nearest neighbor counting. Whether an edge atom is of armchair or zigzag type is decided by the unique pattern of its nearest neighbors. Particular attention is paid to the practical aspects of using the tool, as additional features such as extracting out the edges from the lattice could help in analyzing images from transmission microscopy or other experimental probes. Ultimately, the tool in combination with density-functional theory or tight-binding method can also be helpful in correlating the properties of graphene flakes with the different armchair-to-zigzag ratios. Program summary Program title: edgecount Catalogue identifier: AEIA_v1_0 Program summary URL: http://cpc.cs.qub.ac.uk/summaries/AEIA_v1_0.html Program obtainable from: CPC Program Library, Queen's University, Belfast, N. Ireland Licensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.html No. of lines in distributed program, including test data, etc.: 66685 No. of bytes in distributed program, including test data, etc.: 485 381 Distribution format: tar.gz Programming language: FORTRAN 90/95 Computer: Most UNIX-based platforms Operating system: Linux, Mac OS Classification: 16.1, 7.8 Nature of problem: Detection and classification of edge atoms in a finite patch of honeycomb lattice. Solution method: Build nearest neighbor (NN) list; assign types to edge atoms on the basis of their NN pattern. Running time: Typically similar to second(s) for all examples. (C) 2010 Elsevier B.V. All rights reserved.

Toward Effective Scalar Hardware for Highly Vectorizable Applications

The performance of a program will ultimately be limited by its serial (scalar) portion, as pointed out by Amdahl′s Law. Reported studies thus far of instruction-level parallelism have mixed data-parallel program portions with scalar program portions, often leading to contradictory and controversial results. We report an instruction-level behavioral characterization of scalar code containing minimal data-parallelism, extracted from highly vectorized programs of the PERFECT benchmark suite running on a Cray Y-MP system. We classify scalar basic blocks according to their instruction mix, characterize the data dependencies seen in each class, and, as a first step, measure the maximum intrablock instruction-level parallelism available. We observe skewed rather than balanced instruction distributions in scalar code and in individual basic block classes of scalar code; nonuniform distribution of parallelism across instruction classes; and, as expected, limited available intrablock parallelism. We identify frequently occurring data-dependence patterns and discuss new instructions to reduce latency. Toward effective scalar hardware, we study latency-pipelining trade-offs and restricted multiple instruction issue mechanisms.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Indian Nanoelectronics Users Program An Outreach Vehicle to Expedite Nanoelectronics Research in India

The worldwide research in nanoelectronics is motivated by the fact that scaling of MOSFETs by conventional top down approach will not continue for ever due to fundamental limits imposed by physics even if it is delayed for some more years. The research community in this domain has largely become multidisciplinary trying to discover novel transistor structures built with novel materials so that semiconductor industry can continue to follow its projected roadmap. However, setting up and running a nanoelectronics facility for research is hugely expensive. Therefore it is a common model to setup a central networked facility that can be shared with large number of users across the research community. The Centres for Excellence in Nanoelectronics (CEN) at Indian Institute of Science, Bangalore (IISc) and Indian Institute of Technology, Bombay (IITB) are such central networked facilities setup with funding of about USD 20 million from the Department of Information Technology (DIT), Ministry of Communications and Information Technology (MCIT), Government of India, in 2005. Indian Nanoelectronics Users Program (INUP) is a missionary program not only to spread awareness and provide training in nanoelectronics but also to provide easy access to the latest facilities at CEN in IISc and at IITB for the wider nanoelectronics research community in India. This program, also funded by MCIT, aims to train researchers by conducting workshops, hands-on training programs, and providing access to CEN facilities. This is a unique program aiming to expedite nanoelectronics research in the country, as the funding for projects required for projects proposed by researchers from around India has prior financial approval from the government and requires only technical approval by the IISc/ IITB team. This paper discusses the objectives of INUP, gives brief descriptions of CEN facilities, the training programs conducted by INUP and list various research activities currently under way in the program.

A quasi-steady performance prediction model for dynamic characteristics of a volute pump

A performance prediction model generally applicable for volute-type centrifugal pumps has been extended to predict the dynamic characteristics of a pump during its normal starting and stopping periods. Experiments have been conducted on a volute pump with different valve openings to study the dynamic behaviour of the pump during normal start-up and stopping, when a small length of discharge pipeline is connected to the discharge flange of the pump. Such experiments have also been conducted when the test pump was part of a hydraulic system, an experimental rig, where it is pumping against three similar pumps, known as supply pumps, connected in series, with the supply pumps kept idle or running. Instantaneous rotational speed, flowrate, and delivery and suction pressures of the pump were recorded and it was observed in all the tested cases that the change of pump behaviour during the transient period was quasi-steady, which validates the quasi-steady approach presented in this paper. The nature of variation of parameters during the transients has been discussed. The model-predicted dynamic head-capacity curves agree well with the experimental data for almost all the tested cases.

Frontier Based Multiple Goal Search in Unknown Environments

We present a frontier based algorithm for searching multiple goals in a fully unknown environment, with only information about the regions where the goals are most likely to be located. Our algorithm chooses an ``active goal'' from the ``active goal list'' generated by running a Traveling Salesman Problem (Tsp) routine with the given centroid locations of the goal regions. We use the concept of ``goal switching'' which helps not only in reaching more number of goals in given time, but also prevents unnecessary search around the goals that are not accessible (surrounded by walls). The simulation study shows that our algorithm outperforms Multi-Heuristic LRTA* (MELRTA*) which is a significant representative of multiple goal search approaches in an unknown environment, especially in environments with wall like obstacles.

Simulation of ENSO-Related Surface Winds in the Tropical Pacific by an Atmospheric General Circulation Model Forced by Observed Sea Surface Temperatures

The authors present the simulation of the tropical Pacific surface wind variability by a low-resolution (R15 horizontal resolution and 18 vertical levels) version of the Center for Ocean-Land-Atmosphere Interactions, Maryland, general circulation model (GCM) when forced by observed global sea surface temperature. The authors have examined the monthly mean surface winds acid precipitation simulated by the model that was integrated from January 1979 to March 1992. Analyses of the climatological annual cycle and interannual variability over the Pacific are presented. The annual means of the simulated zonal and meridional winds agree well with observations. The only appreciable difference is in the region of strong trade winds where the simulated zonal winds are about 15%-20% weaker than observed, The amplitude of the annual harmonics are weaker than observed over the intertropical convergence zone and the South Pacific convergence zone regions. The amplitudes of the interannual variation of the simulated zonal and meridional winds are close to those of the observed variation. The first few dominant empirical orthogonal functions (EOF) of the simulated, as well as the observed, monthly mean winds are found to contain a targe amount of high-frequency intraseasonal variations, While the statistical properties of the high-frequency modes, such as their amplitude and geographical locations, agree with observations, their detailed time evolution does not. When the data are subjected to a 5-month running-mean filter, the first two dominant EOFs of the simulated winds representing the low-frequency EI Nino-Southern Oscillation fluctuations compare quite well with observations. However, the location of the center of the westerly anomalies associated with the warm episodes is simulated about 15 degrees west of the observed locations. The model simulates well the progress of the westerly anomalies toward the eastern Pacific during the evolution of a warm event. The simulated equatorial wind anomalies are comparable in magnitude to the observed anomalies. An intercomparison of the simulation of the interannual variability by a few other GCMs with comparable resolution is also presented. The success in simulation of the large-scale low-frequency part of the tropical surface winds by the atmospheric GCM seems to be related to the model's ability to simulate the large-scale low-frequency part of the precipitation. Good correspondence between the simulated precipitation and the highly reflective cloud anomalies is seen in the first two EOFs of the 5-month running means. Moreover, the strong correlation found between the simulated precipitation and the simulated winds in the first two principal components indicates the primary role of model precipitation in driving the surface winds. The surface winds simulated by a linear model forced by the GCM-simulated precipitation show good resemblance to the GCM-simulated winds in the equatorial region. This result supports the recent findings that the large-scale part of the tropical surface winds is primarily linear.

Smart applications for energy harvested WSNs

A Wireless Sensor Network (WSN) powered using harvested energies is limited in its operation by instantaneous power. Since energy availability can be different across nodes in the network, network setup and collaboration is a non trivial task. At the same time, in the event of excess energy, exciting node collaboration possibilities exist; often not feasible with battery driven sensor networks. Operations such as sensing, computation, storage and communication are required to achieve the common goal for any sensor network. In this paper, we design and implement a smart application that uses a Decision Engine, and morphs itself into an energy matched application. The results are based on measurements using IRIS motes running on solar energy. We have done away with batteries; instead used low leakage super capacitors to store harvested energy. The Decision Engine utilizes two pieces of data to provide its recommendations. Firstly, a history based energy prediction model assists the engine with information about in-coming energy. The second input is the energy cost database for operations. The energy driven Decision Engine calculates the energy budgets and recommends the best possible set of operations. Under excess energy condition, the Decision Engine, promiscuously sniffs the neighborhood looking for all possible data from neighbors. This data includes neighbor's energy level and sensor data. Equipped with this data, nodes establish detailed data correlation and thus enhance collaboration such as filling up data gaps on behalf of nodes hibernating under low energy conditions. The results are encouraging. Node and network life time of the sensor nodes running the smart application is found to be significantly higher compared to the base application.

A Tutorial on Integrating CDS/ISIS Databases with the World Wide Web

With the emergence of Internet, the global connectivity of computers has become a reality. Internet has progressed to provide many user-friendly tools like Gopher, WAIS, WWW etc. for information publishing and access. The WWW, which integrates all other access tools, also provides a very convenient means for publishing and accessing multimedia and hypertext linked documents stored in computers spread across the world. With the emergence of WWW technology, most of the information activities are becoming Web-centric. Once the information is published on the Web, a user can access this information from any part of the world. A Web browser like Netscape or Internet Explorer is used as a common user interface for accessing information/databases. This will greatly relieve a user from learning the search syntax of individual information systems. Libraries are taking advantage of these developments to provide access to their resources on the Web. CDS/ISIS is a very popular bibliographic information management software used in India. In this tutorial we present details of integrating CDS/ISIS with the WWW. A number of tools are now available for making CDS/ISIS database accessible on the Internet/Web. Some of these are 1) the WAIS_ISIS Server. 2) the WWWISIS Server 3) the IQUERY Server. In this tutorial, we have explained in detail the steps involved in providing Web access to an existing CDS/ISIS database using the freely available software, WWWISIS. This software is developed, maintained and distributed by BIREME, the Latin American & Caribbean Centre on Health Sciences Information. WWWISIS acts as a server for CDS/ISIS databases in a WWW client/server environment. It supports functions for searching, formatting and data entry operations over CDS/ISIS databases. WWWISIS is available for various operating systems. We have tested this software on Windows '95, Windows NT and Red Hat Linux release 5.2 (Appolo) Kernel 2. 0. 36 on an i686. The testing was carried out using IISc's main library's OPAC containing more than 80,000 records and Current Contents issues (bibliographic data) containing more than 25,000 records. WWWISIS is fully compatible with CDS/ISIS 3.07 file structure. However, on a system running Unix or its variant, there is no guarantee of this compatibility. It is therefore safe to recreate the master and the inverted files, using utilities provided by BIREME, under Unix environment.

Synthesis of acicular hydrogoethite (alpha-FeOOH center dot xH(2)O; 0.1 < x < 0.22) particles using morphology controlling cationic additives and magnetic properties of maghemite derived from hydrogoethite

A method for the preparation of acicular hydrogoethite (alpha -FeOOH.xH(2)O, 0.1 < x < 0.22) particles of 0.3-1 mm length has been optimized by air oxidation of Fe( II) hydroxide gel precipitated from aqueous (NH4)(2)Fe(SO4)(2) solutions containing 0.005-0.02 atom% of cationic Pt, Pd or Rh additives as morphology controlling agents. Hydrogoethite particles are evolved from the amorphous ferrous hydroxide gel by heterogeneous nucleation and growth. Preferential adsorption of additives on certain crystallographic planes thereby retarding the growth in the perpendicular direction, allows the particles to acquire acicular shapes with high aspect ratios of 8-15. Synthetic hydrogoethite showed a mass loss of about 14% at similar to 280 degreesC, revealing the presence of strongly coordinated water of hydration in the interior of the goethite crystallites. As evident from IR spectra, excess H2O molecules (0.1- 0.22 per formula unit) are located in the strands of channels formed in between the double ribbons of FeO6 octahedra running parallel to the c- axis. Hydrogoethite particles constituted of multicrystallites are formed with Pt as additive, whereas single crystallite particles are obtained with Pd (or Rh). For both dehydroxylation as well as H-2 reduction, a lower reaction temperature (similar to 220 degreesC) was observed for the former (Pt treated) compared to the latter (Pd or Rh) (similar to 260 degreesC). Acicular magnetite (Fe3O4) was prepared either by reducing hydrogoethite (magnetite route) or dehydroxylating hydrogoethite to hematite and then reducing it to magnetite (hematite- magnetite route). According to TEM studies, preferential dehydroxylation of hydrogoethite along < 010 > leads to microporous hematite. Maghemite (gamma -Fe2O3 (-) (delta), 0 < < 0.25) was obtained by reoxidation of magnetite. The micropores are retained during the topotactic transformation to magnetite and finally to maghemite, whereas cylindrical mesopores are formed due to rearrangement of the oxygen sublattice from hexagonal to cubic close packing during the conversion of hydrogoethite to magnetite and then to maghemite. Accordingly, three different types of maghemite particles are realized: strongly oriented multicrystalline particles, single crystalline acicular particles with micropores or crystallites having mesopores. Higher values of saturation magnetization ((s) = 74 emu g(-1)) and coercivity (H-c = 320 Oe) are obtained for single crystalline mesoporous particles. In the other cases, the smaller size of particles and larger distribution of micropores decreases sigma (s) considerably ( < 60 emu g(-1)) due to relaxation effects of spins on the surface atoms as revealed by Mossbauer spectroscopy.

Copper, Zinc-Superoxide Dismutase from Clinically Isolated Escherichia coli: Cloning, Analysis of sodC and Its Possible Role in Pathogenicity

Superoxide dismutase has been discovered within the periplasm of several Gram-negative pathogens. We studied the Cu,Zn-SOD enzyme in Escherichia coli isolated from clinical samples (stool samples) collected from patients suffering from diarrhea. Antibiogram studies of the isolates were carried out to determine the sensitive and resistant strains. The metal co-factor present in the enzyme was confirmed by running samples in native gels and inhibiting with 2 mM potassium cyanide. A 519 bp sodC gene was amplified from resistant and sensitive strains of Escherichia coli. Cloning and sequencing of the sodC gene indicated variation in the protein and amino acid sequences of sensitive and resistant isolates. The presence of sodC in highly resistant Escherichia coli isolates from diarrheal patients indicates that sodC may play role in enhancing the pathogenicity by protecting cells from exogenous sources of superoxide, such as the oxidative burst of phagocytes. The presence of SodC could be one of the factors for bacterial virulence.