Comments on Identification of Totally Symmetric Boolean Functions

A modification in the algorithm for the detection of totally symmetric functions as expounded by the author in an earlier note1 is presented here. The modified algorithm takes care of a limited number of functions that escape detection by the previous method.

Optimum geometry for uniform deposits on a rotating substrate from a point source

The application of an algorithm shows that maximum uniformity of film thickness on a rotating substrate is achieved for a normalized source-to-substrate distance ratio, h/r =1.183.

Divide-and-Correct Algorithm for Division in a Negative Base

A divide-and-correct algorithm is described for multiple-precision division in the negative base number system. In this algorithm an initial quotient estimate is obtained from suitable segmented operands; this is then corrected by simple rules to arrive at the true quotient.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

Deterministic Division Algorithm in a Negative Base

Described here is a deterministic division algorithm in a negative-base number system; here, the divisor is mapped into a suitable range by premultiplication, so that the choice of the quotient digit is deterministic.

Systematic search for optical Barker codes with minimum length

A method that yields optical Barker codes of smallest known lengths for given discrimination is described.

Optimal popular matchings

In this paper we consider the problem of computing an “optimal” popular matching. We assume that our input instance View the MathML source admits a popular matching and here we are asked to return not any popular matching but an optimal popular matching, where the definition of optimality is given as a part of the problem statement; for instance, optimality could be fairness in which case we are required to return a fair popular matching. We show an O(n2+m) algorithm for this problem, assuming that the preference lists are strict, where m is the number of edges in G and n is the number of applicants.

Estimation of Execution Times of Process Control Algorithms on Microcomputers

An important question which has to be answered in evaluting the suitability of a microcomputer for a control application is the time it would take to execute the specified control algorithm. In this paper, we present a method of obtaining closed-form formulas to estimate this time. These formulas are applicable to control algorithms in which arithmetic operations and matrix manipulations dominate. The method does not require writing detailed programs for implementing the control algorithm. Using this method, the execution times of a variety of control algorithms on a range of 16-bit mini- and recently announced microcomputers are calculated. The formulas have been verified independently by an analysis program, which computes the execution time bounds of control algorithms coded in Pascal when they are run on a specified micro- or minicomputer.

Waves in branched hydraulic pipes

The paper deals with the classical problem of axi-symmetric transmission of low amplitude waves through a circular pipe containing a viscous liquid. Exact governing equations are identified and solved, the radial as well as the axial component of the velocity being considered. Attention is drawn to certain fallacies underlying the conventional approach. The parameters required in the formulation of the transfer matrix for a pipe have been evaluated. In order to evaluate the response at the terminal point of a branched system for a sinusoidal input at one of the ends, a general algorithm has been developed.

Application of the Conjugate Gradient Method to a Problem on Minimum Time Orbit Transfer

This correspondence considers the problem of optimally controlling the thrust steering angle of an ion-propelled spaceship so as to effect a minimum time coplanar orbit transfer from the mean orbital distance of Earth to mean Martian and Venusian orbital distances. This problem has been modelled as a free terminal time-optimal control problem with unbounded control variable and with state variable equality constraints at the final time. The problem has been solved by the penalty function approach, using the conjugate gradient algorithm. In general, the optimal solution shows a significant departure from earlier work. In particular, the optimal control in the case of Earth-Mars orbit transfer, during the initial phase of the spaceship's flight, is found to be negative, resulting in the motion of the spaceship within the Earth's orbit for a significant fraction of the total optimized orbit transfer time. Such a feature exhibited by the optimal solution has not been reported at all by earlier investigators of this problem.

A rational synthesis of vibration isolators

The paper deals with a rational approach to the development of general design criteria for non-dissipative vibration isolation systems. The study covers straight-through springmass systems as well as branched ones with dynamic absorbers. Various design options, such as the addition of another spring-mass pair, replacement of an existing system by one with more spring-mass pairs for the same space and material requirements, provision of one or more dynamic absorbers for the desired frequency range, etc., are investigated quantitatively by means of an algebraic algorithm which enables one to write down straightaway the velocity ratio and hence transmissibility of a linear dynamical system in terms of the constituent parameters.

An Optimal Mechanism for Sponsored Search Auctions on the Web and Comparison With Other Mechanisms

In this paper, we first describe a framework to model the sponsored search auction on the web as a mechanism design problem. Using this framework, we describe two well-known mechanisms for sponsored search auction-Generalized Second Price (GSP) and Vickrey-Clarke-Groves (VCG). We then derive a new mechanism for sponsored search auction which we call optimal (OPT) mechanism. The OPT mechanism maximizes the search engine's expected revenue, while achieving Bayesian incentive compatibility and individual rationality of the advertisers. We then undertake a detailed comparative study of the mechanisms GSP, VCG, and OPT. We compute and compare the expected revenue earned by the search engine under the three mechanisms when the advertisers are symmetric and some special conditions are satisfied. We also compare the three mechanisms in terms of incentive compatibility, individual rationality, and computational complexity. Note to Practitioners-The advertiser-supported web site is one of the successful business models in the emerging web landscape. When an Internet user enters a keyword (i.e., a search phrase) into a search engine, the user gets back a page with results, containing the links most relevant to the query and also sponsored links, (also called paid advertisement links). When a sponsored link is clicked, the user is directed to the corresponding advertiser's web page. The advertiser pays the search engine in some appropriate manner for sending the user to its web page. Against every search performed by any user on any keyword, the search engine faces the problem of matching a set of advertisers to the sponsored slots. In addition, the search engine also needs to decide on a price to be charged to each advertiser. Due to increasing demands for Internet advertising space, most search engines currently use auction mechanisms for this purpose. These are called sponsored search auctions. A significant percentage of the revenue of Internet giants such as Google, Yahoo!, MSN, etc., comes from sponsored search auctions. In this paper, we study two auction mechanisms, GSP and VCG, which are quite popular in the sponsored auction context, and pursue the objective of designing a mechanism that is superior to these two mechanisms. In particular, we propose a new mechanism which we call the OPT mechanism. This mechanism maximizes the search engine's expected revenue subject to achieving Bayesian incentive compatibility and individual rationality. Bayesian incentive compatibility guarantees that it is optimal for each advertiser to bid his/her true value provided that all other agents also bid their respective true values. Individual rationality ensures that the agents participate voluntarily in the auction since they are assured of gaining a non-negative payoff by doing so.

A Reactive Inverse PN Algorithm for Collision Avoidance among Multiple Unmanned Aerial Vehicles

While performing a mission, multiple Unmanned Aerial Vehicles (UAVs) need to avoid each other to prevent collisions among them. In this paper, we design a collision avoidance algorithm to resolve the conflict among UAVs that are on a collision course while flying to heir respective destinations. The collision avoidance algorithm consist of each UAV that is on a collision course reactively executing a maneuver that will, as in `inverse' Proportional Navigation (PN), increase Line of Sight (LOS) rate between them, resulting in a `pulling out' of collision course. The algorithm is tested for high density traffic scenarios as well as for robustness in the presence of noise.

Feature extraction for fingerprint classification

This paper presents two algorithms for smoothing and feature extraction for fingerprint classification. Deutsch's(2) Thinning algorithm (rectangular array) is used for thinning the digitized fingerprint (binary version). A simple algorithm is also suggested for classifying the fingerprints. Experimental results obtained using such algorithms are presented.

Determination of optimal trajectory under design constraints for a satellite launch vehicle

An optimal pitch steering programme of a solid-fuel satellite launch vehicle to maximize either (1) the injection velocity at a given altitude, or (2) the size of circular orbit, for a given payload is presented. The two-dimensional model includes the rotation of atmosphere with the Earth, the vehicle's lift and drag, variation of thrust with time and altitude, inverse-square gravitational field, and the specified initial vertical take-off. The inequality constraints on the aerodynamic load, control force, and turning rates are also imposed. Using the properties of the central force motion the terminal constraint conditions at coast apogee are transferred to the penultimate stage burnout. Such a transformation converts a time-free problem into a time-fixed one, reduces the number of terminal constraints, improves accuracy, besides demanding less computer memory and time. The adjoint equations are developed in a compact matrix form. The problem is solved on an IBM 360/44 computer using a steepest ascent algorithm. An illustrative analysis of a typical launch vehicle establishes the speed of convergence, and accuracy and applicability of the algorithm.