In the above paper1Gupta, Lee, and Leung present a new algorithm for making an optimal assignment of wire segments to channels on a PC board. The new algorithm has a running time of 0(N log N) in the general case, but can be executed in 0(N) time if the wire segment endpoints are close to uniformly distributed.

Pless has proposed a stream cipher based on J–K flip-flops that uses 8 linear shift registers with feedback, having a combined length of 97 bits, 4 J–K flip-flops, and a 4-stage cycling counter. The cipher has 2.54 × 1051initial states (keys), and generates a presumably pseudorandom stream whose period is 1.52 × 1029bits. Despite these impressive statistics, it is computationally feasible to solve such a cipher with a known-plaintext attack, using as few as 15 characters

Algorithms are presented for encoding and decoding strings of characters as real binary fractions, using registers of fixed precision. The encoding is left to right and does not require blocking. The algorithms have storage requirementsO(N)and computation timeO(n \log_{2}N)for string lengthnand alphabet sizeN.

article Partition of Integers Share on Author: Frank Rubin Systems Development Division, IBM Corp., Box 390, Poughkeepsie, NY Systems Development Division, IBM Corp., Box 390, Poughkeepsie, NYView Profile Authors Info & Claims ACM Transactions on Mathematical SoftwareVolume 2Issue 4Dec. 1976 pp 364–374https://doi.org/10.1145/355705.355711Online:01 December 1976Publication History 2citation511DownloadsMetricsTotal Citations2Total Downloads511Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

An exact upper bound is found for the number of maximal compatible subsets of an n-state incompletely specified sequential machine (ISSM). This bound, on the order of 3n/3, iS also a worst case computer storage and computation time limit for any algorithm to find maximal compatibles.

Hopcroft and Tarjan [2] have recently proposed an algorithm that runs in linear time for testing the planarity of a graph. The technique finds a representation of the graph as a sequence of paths and then iteratively imbeds these paths to find a mesh structure, rearranging the meshes as needed to accommodate each new path. Demoucron et al. [1] have shown that this rearrangement process is unnecessary if the paths are considered in the proper order. The present implementation is found to run in linear time for most ordinary cases, about twice as fast as Tarjan's Algol implementation. A graph of 3000 vertices and 8994 edges required about 18 s.

A search procedure is given which will determine whether Hamilton paths or circuits exist in a given graph, and will find one or all of them. A combined procedure is given for both directed and undirected graphs. The search consists of creating partial paths and making deductions which determine whether each partial path is a section of any Hamilton path whatever, and which direct the extension of the partial paths.