Theory and Algorithms Commons^™

Cryptography Using Steganography: New Algorithms And Applications, Jonathan Blackledge

Articles

Developing methods for ensuring the secure exchange of information is one of the oldest occupations in history. With the revolution in Information Technology, the need for securing information and the variety of methods that have been developed to do it has expanded rapidly. Much of the technology that forms the basis for many of the techniques used today was originally conceived for use in military communications and has since found a place in a wide range of industrial and commercial sectors. This has led to the development of certain industry standards that are compounded in specific data processing algorithms together …

Tight Lower Bound For The Sparse Travelling Salesman Problem, Fredrick Mtenzi

Conference papers

The Sparse Travelling Salesman Problem (Sparse TSP) which is a variant of the classical Travelling Salesman Problem (TSP) is the problem of finding the shortest route of the salesman when visiting cities in a region making sure that each city is visited at least once and returning home at the end. In the Sparse TSP, the distance between cities may not obey the triangle inequality; this makes the use of algorithms and formulations designed for the TSP to require modifications in order to produce near-optimal results. A lower bound for optmisation problems gives us the quality guarantee of the near-optimal …

Modular Exponentiation Via The Explicit Chinese Remainder Theorem, Daniel J. Bernstein, Jonathan P. Sorenson

Scholarship and Professional Work - LAS

In this paper we consider the problem of computing xe mod m for large integers x, e, and m. This is the bottleneck in Rabin’s algorithm for testing primality, the Diffie-Hellman algorithm for exchanging cryptographic keys, and many other common algorithms.

Optimizing The Replication Of Multi-Quality Web Applications Using Aco And Wolf, Judson C. Dressler

Theses and Dissertations

This thesis presents the adaptation of Ant Colony Optimization to a new NP-hard problem involving the replication of multi-quality database-driven web applications (DAs) by a large application service provider (ASP). The ASP must assign DA replicas to its network of heterogeneous servers so that user demand is satisfied and replica update loads are minimized. The algorithm proposed, AntDA, for solving this problem is novel in several respects: ants traverse a bipartite graph in both directions as they construct solutions, pheromone is used for traversing from one side of the bipartite graph to the other and back again, heuristic edge values …

A Fast And Simple Algorithm For Computing M Shortest Paths In Stage Graph, M. Sherwood, Laxmi P. Gewali, Henry Selvaraj, Venkatesan Muthukumar

Electrical & Computer Engineering Faculty Research

We consider the problem of computing m shortest paths between a source node s and a target node t in a stage graph. Polynomial time algorithms known to solve this problem use complicated data structures. This paper proposes a very simple algorithm for computing all m shortest paths in a stage graph efficiently. The proposed algorithm does not use any complicated data structure and can be implemented in a straightforward way by using only array data structure. This problem appears as a sub-problem for planning risk reduced multiple k-legged trajectories for aerial vehicles.

A Fast And Simple Algorithm For Computing M-Shortest Paths In State Graph, M. Sherwood, Laxmi P. Gewali, Henry Selvaraj, Venkatesan Muthukumar

Electrical & Computer Engineering Faculty Research

We consider the problem of computing m shortest paths between a source node s and a target node t in a stage graph. Polynomial time algorithms known to solve this problem use complicated data structures. This paper proposes a very simple algorithm for computing all m shortest paths in a stage graph efficiently. The proposed algorithm does not use any complicated data structure and can be implemented in a straightforward way by using only array data structure. This problem appears as a sub-problem for planning risk reduced multiple k-legged trajectories for aerial vehicles.

Real-Time Travel Time Estimation Using Macroscopic Traffic Flow Models, Pushkin Kachroo, Kaan Ozbay, Antoine G. Hobeika

Electrical & Computer Engineering Faculty Research

This paper presents the estimation of travel time on highways based on macroscopic modelling. The focus is on real-time values as compared to average or static values. The macroscopic models are used for distributed and time/space lumped settings and corresponding travel time estimation functions and algorithms are developed. The implications of these algorithms for the implementation of various incident management and traffic control strategies are also discussed.

Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer

Mathematical Sciences Technical Reports (MSTR)

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP­ complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, …

Asymptotically Tight Bounds For Performing Bmmc Permutations On Parallel Disk Systems, Thomas H. Cormen, Thomas Sundquist, Leonard F. Wisniewski

Dartmouth Scholarship

This paper presents asymptotically equal lower and upper bounds for the number of parallel I/O operations required to perform bit-matrix-multiply/complement (BMMC) permutations on the Parallel Disk Model proposed by Vitter and Shriver. A BMMC permutation maps a source index to a target index by an affine transformation over GF(2), where the source and target indices are treated as bit vectors. The class of BMMC permutations includes many common permutations, such as matrix transposition (when dimensions are powers of 2), bit-reversal permutations, vector-reversal permutations, hypercube permutations, matrix reblocking, Gray-code permutations, and inverse Gray-code permutations. The upper bound improves upon the asymptotic …

Fast Discrete Polynomial Transforms With Applications To Data Analysis For Distance Transitive Graphs, J. R. Driscoll, D. M. Healy, D. N. Rockmore

Dartmouth Scholarship

Let $\poly = \{P_0,\dots,P_{n-1}\}$ denote a set of polynomials with complex coefficients. Let $\pts = \{z_0,\dots,z_{n-1}\}\subset \cplx$ denote any set of {\it sample points}. For any $f = (f_0,\dots,f_{n-1}) \in \cplx^n$, the {\it discrete polynomial transform} of f (with respect to $\poly$ and $\pts$) is defined as the collection of sums, $\{\fhat(P_0),\dots,\fhat(P_{n-1})\}$, where $\fhat(P_j) = \langle f,P_j \rangle = \sum_{i=0}^{n-1} f_iP_j(z_i)w(i)$ for some associated weight function w. These sorts of transforms find important applications in areas such as medical imaging and signal processing.

In this paper, we present fast algorithms for computing discrete orthogonal polynomial transforms. For a system …

Investigating The Use Of Kalman Filtering Approaches For Dynamic Origin-Destination Trip Table Estimation, Pushkin Kachroo, Kaan Ozbay, Arvind Narayanan

Electrical & Computer Engineering Faculty Research

This paper studies the applicability of Kalman filtering approaches for network wide traveler origin-destination estimation from link traffic volumes. The paper evaluates the modeling assumptions of the Kalman filters and examines the implications of such assumptions.

An Algorithm For The Electromagnetic Scattering Due To An Axially Symmetric Body With An Impedance Boundary Condition, F. Stenger, M. Hagmann, J. Scheing

Computer Science Faculty Publications

Let B be a body in R³, and let S denote the boundary of B. The surface S is described by S = {(x, y, z): (x² + Y²)^½= ƒ(z), -1≤ z ≤ I}, where ƒ analytic function that is real and positive on (-1, 1) and ƒ(±1) = 0. An algorithm is described for computing the scattered field due to a plane wave incident field, under Leontovich boundary conditions. The Galerkin method of solution used here leads to a block diagonal matrix involving 2M …