ROBERT FLOYD

images45

Computer pioneer Robert W. Floyd, a professor emeritus and former chair of the Department of Computer Science. Born in New York on June 8, 1936, Floyd was recognized as a child prodigy at age 6; he skipped three grades and finished high school at 14. A scholarship allowed him to study at the University of Chicago, where he received a bachelor’s degree in liberal arts in 1953 at age 17. After that he supported himself and earned another bachelor’s degree in physics in 1958. “His entire career in computing was based on autodidactic efforts,” recalls his second ex-wife, Christiane Floyd, a computer scientist at the University of Hamburg in Germany. “He started as an operator in the night shift, taught himself how to program, started to publish in the early 1960s and re-entered academia as an associate professor at Carnegie Mellon at the age of 27. He was only 32 when he got his full professorship at Stanford.”

“In the old days, programmers would just twiddle with programs till they seemed to work,” says Professor Emeritus of The Art of Computer Programming Donald Knuth. “Floyd showed that there was a way to prove programs would work.” His approach of marrying math with computer science was “a revelation to the field,” Knuth says.”Floyd’s 1960s method of invariants, in which assertions are attached to points in a computer program, is still the basis of much work in proving that computer programs meet their specifications,” says John McCarthy, professor emeritus of computer science.

His research included design and analysis of algorithms for finding the shortest paths in a network, parsing (decomposing) programming languages, calculating quantiles, printing shades of gray on a dot printer, sorting information and selecting random permutations and combinations.

His most important scientific achievement, however, was pioneering systematic methods of program verification. His seminal 1967 paper, “Assigning Meanings to Programs,” opened the field of program verification. His basic idea was to attach so-called “tags” in the form of logical assertions to individual program statements or branches that would define the effects of the program based on a formal semantic definition of the programming language. Many researchers in formal methods of computing worldwide adopted this method. One of the most important influences was on C. A. R. Hoare, who in 1969, starting from Floyd’s work, developed his calculus of pre- and post condition semantics for computer programs.

“The Art of Computer Programming eventually was transformed into a series of seven volumes and is still a work in progress”. Floyd may have been the first advocate of refactoring — the rewriting of working programs from scratch, re-using only the essential ideas. Refactoring is now standard practice among computer programmers. By continuously looking for simpler ways to do the same thing, Floyd aimed to improve not only programs but also programmers’ abilities and understanding.

At Stanford, he taught algorithmic courses, including “Sorting and Searching.” With his former graduate student Richard Beigel, he wrote a textbook titled The Language of Machines: An Introduction to Computability and Formal Languages (Computer Science Press, 1994).

He enjoyed backgammon — pitting his skill against computer opponents at home and human opponents in major tournaments, says friend and colleagues.

He also was a passionate hiker and mountain climber who loved the wilderness country in the High Sierra, recalls Christiane Floyd.Floyd is survived by four children — Susan Barnett of Butte, Mont.; Michael Floyd of Urbana, Ill.; Sean Floyd of Berlin, Germany; and Erik Schorr of Roseville, Calif. — as well as by his mother, Mary Floyd of Alexandria, Va., and siblings Shelby Floyd of Kamuela, Hawaii, Jeff Floyd of Alexandria, Va., and Fred Floyd of Elko, Nev.

In 1991, the Institute of Electrical and Electronics Engineers (IEEE) Computer Society awarded Floyd its Computer Pioneer Award for his work on early compilers. (A compiler is software that translates a computer program as a whole into machine code that is saved for subsequent execution at a desired time.)

In 1994, Floyd retired from Stanford .He was a fellow of the American Academy of Arts and Sciences, the American Association for the Advancement of Science and the ACM.

In 1978, Floyd won the Association for Computing Machinery (ACM) Turing Award — the highest honor in computer science — “for having a clear influence on methodologies for the creation of efficient and reliable software, and for helping to found the following important subfields of computer science: the theory of parsing, the semantics of programming languages, automatic program verification, automatic program synthesis, and analysis of algorithms.”

He died at Stanford University Medical Center on Sept 25 after a long illness. He was 65.

Floyd’s Cycle Detection   Algorithm (The Tortoise and the Hare)

3211f8901b4c0d5490fdbcb2e37413ca

tortoise = top
 hare = top
 forever:
    if hare == end :
        return 'No Loop Found'
    hare = hare.next
  if hare == end :
         return 'No Loop Found'
     hare = hare.next
 tortoise = tortoise.next
 if hare == tortoise:
         return 'Loop Found'

How do you determine if your singly-linked list has a cycle? In the late 1960s, Robert W. Floyd invented an algorithm that worked in linear (O(N)) time. It is also called Floyd’s cycle detection algorithm.

The easiest solution to the cycle detection problem is to run through the list, keeping track of which nodes you visit, and on each node check to see if it is the same as any of the previous nodes. It’s pretty obvious that this runs in quadratic ( O(N^2)) time… not very efficient, and actually more complicated than this one.

The Tortoise and the Hare is possibly the most famous cycle detection algorithm, and is surprisingly straightforward. The Tortoise and the Hare are both pointers, and both start at the top of the list. For  each iteration, the Tortoise takes one step and the Hare takes two. If there is a loop, the hare will go around that loop (possibly more than once) and eventually meet up with the turtle when the turtle gets into the loop. If there is no loop, the hare will get to the end of the list without meeting up with the turtle.

How to find the length of the Loop ?
Once Hare and Tortoise finds the loop in a Singly linked List move Tortoise one step forward everytime maintaining the count of the nodes until it reaches the Hare again.

Example:

llllllhuuuSingly Linked List with a Loop

Both Tortoise and Hare starts at First node of the list and Tortoise moves 1 step forward while Hare moves 2 steps forward.

iokll

Hare and Tortoise starts at First Node of the List

 Hare           Tortoise
1                      1
3                      2
5                      3
7                      4
3                      5
5                      6
7                      7

 

Both Hare and Tortoise meet up at Node 7. That proves there is a loop in the list.

908665Complexity:

♣  Time Complexity: O(n)

♣  Space Complexity: O(1)

Floyd-Warshall All-Pairs Shortest Pairs Algorithm

A  Brief Introduction to Graphs

Graphs are a very important data structure in computer science. Many otherwise very difficult problems can be expressed in terms of a graph and solved using standard graph searching/manipulation algorithms.

Graphs can be simply viewed as a set of vertices/nodes and edges connecting these vertices. Mathematically G = (V,E), if u and v are elements of V, then an edge can be denoted as (u,v).

Graphics can be basically classified as either being undirected or directed. In the former, the edges do not have a direction i.e. (u,v) and (v,u) denote the same edge. In the latter the edges have a direction.

Another important aspect of graphs is the identification of cycles. A cycle is a path such that the first vertex and the last vertex are the same.

The following illustrates a directed graph that contains cycles and negatively weighted edges (see below). The graph consists of 5 vertices and 9 edges.

graph

The adjacency matrix that represents the above graph is:

0 3 8 inf. -4
inf. 0 inf. 1 7
inf. 4 0 inf. inf.
2 inf. -5 0 inf.
inf. inf. inf. 6 0

NB: inf. Represents a distance of infinity, i.e. no (direct) connection.

Floyd-Warshall  All-Pairs-Shortest-Path algorithm

The Floyd-Warshall All-Pairs-Shortest-Path algorithm uses a dynamic-programming methodology to solve the All-Pairs-Shortest-Path problem. The algorithm runs in O(|V|3) time and negatively weighed edges may be present, however negatively weighted cycles cause problems with the algorithm.

For a detailed description of the dynamic approach used in the Floyd-Warshall algorithm see:

The main recursively definition of the algorithm is given by:

floyd_al

This leads to the following bottom-up procedure compute the all-pairs-shortest-path table.

SHA1CRK

SHA1CRK is a distributed brute force attack on the cryptographic hashing function SHA-1, using the micro-blogging site Twitter as a medium of communication. You can follow the initiative on Twitter using the tag #SHA1CRK. If you’re confused by the messages that are being tweeted, check out the  SHA1CRK protocol for a short explanation of their meaning.

If you want to learn more about the project, you can watch a presentation held at NDC 2010.

How Will SHA1CRK Find Collisions?

SHA1CRK uses a technique called Floyd’s cycle finding algorithm to find collisions in SHA-1.  This is the same technique that  MD5CRK  used a few years ago, and is illustrated by the figure to the right.

890

The algorithm can be described by analogy with a random walk. By its definition, SHA-1 is a function with a finite number of possible outputs, namely 2160. Using the principle that any such function placed in a feedback loop will cycle, one can use a relatively small amount of memory to store outputs with particular structures and use them as “markers”. These markers can then be used to detect when they have been “passed” before. The project calls these markers distinguished points, and the point where two inputs produce the same output is called a collision point. Just like MD5CRK, SHA1CRK considers any point whose first 32 bits are zeroes to be a distinguished point.

Before a collision will be found, a lot of near-collisions will be found. A near-collision with Hamming distance d is defined as two points that produce outputs that differ only in d bits. As d becomes smaller, these pairs may start to give hints about the structure of a collision point. The near-collision with the smallest Hamming distance will also be a good indicator of the progress of the project.

ROBERT FLOYD’S QUOTES

♠  ” It is, therefore, possible to extend a partially specified interpretation to a complete interpretation, without loss of verifiability, […] This fact offers the possibility of automatic verification of programs, the programmer merely tagging entrances and one edge in each innermost loop. ”

 ♠ “If the advancement of the general art of programming requires the continuing invention and elaboration of paradigms, advancement of the art of the individual programmer requires that he expand his repertory of paradigms. ”

 ♠ ” The establishment of formal standards for proofs in about programs […] and the proposal that the semantics of a programming language may be defined independently of all processors for that language, by establishing standards of rigor for proofs about programs in the language, appears to be novel. ”

 

ROBERT FLOYD’S PUBLICATIONS

1996

Robert W. Floyd, Richard Beigel: Die Sprache der Maschinen. International Thomson 1996

1990

Robert W. Floyd, Donald E. Knuth: Addition Machines. SIAM J. Comput. (SIAMCOMP) 19(2):329-340 (1990)

1982

Robert W. Floyd, Jeffrey D. Ullman: The Compilation of Regular Expressions into Integrated Circuits. J. ACM (JACM) 29(3):603-622 (1982)

1980

Robert W. Floyd, Jeffrey D. Ullman: The Compilation of Regular Expressions into Integrated Circuits (Extended Abstract) FOCS 1980:260-269

1979

Robert W. Floyd: The Paradigms of Programming. Commun. ACM (CACM) 22(8):455-460 (1979)

1978

Larry Carter, Robert W. Floyd, John Gill, George Markowsky, Mark N. Wegman: Exact and Approximate Membership Testers STOC 1978:59-65

1975

Robert W. Floyd, Ronald L. Rivest: Expected Time Bounds for Selection. Commun. ACM (CACM) 18(3):165-172 (1975)
Robert W. Floyd, Ronald L. Rivest: The Algorithm SELECT – for Finding the ith Smallest of n Elements [M1] (Algorithm 489). Commun. ACM (CACM) 18(3):173 (1975)
Robert W. Floyd: The Exact Time Required to Perform Generalized Addition FOCS 1975:3-5

1973

Robert W. Floyd, Alan Jay Smith: A Linear Time Two Tape Merge. Inf. Process. Lett. (IPL) 2(5):123-125 (1973)
Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, Robert Endre Tarjan: Time Bounds for Selection. J. Comput. Syst. Sci. (JCSS) 7(4):448-461 (1973)
Alfred V. Aho, Allan Borodin, Robert L. Constable, Robert W. Floyd, Michael A. Harrison, Richard M. Karp, H. Raymond Strong: Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30 – May 2, 1973, Austin, Texas, USA STOC 1973

1972

Robert W. Floyd: Permuting Information in Idealized Two-Level Storage. Complexity of Computer Computations 1972:105-109
Donald E. Knuth, Robert W. Floyd: Errata: Notes on Avoiding “go to” Statements. Inf. Process. Lett. (IPL) 1(4):177 (1972)
James C. King, Robert W. Floyd: An Interpretation-Oriented Theorem Prover over Integers. J. Comput. Syst. Sci. (JCSS) 6(4):305-323 (1972)
Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, Robert Endre Tarjan: Linear Time Bounds for Median Computations STOC 1972:119-124

1971

Robert W. Floyd: Toward Interactive Design of Correct Programs. IFIP Congress 1971:7-10
Donald E. Knuth, Robert W. Floyd: Notes on Avoiding “go to” Statements. Inf. Process. Lett. (IPL) 1(1):23-31 (1971)

1970

James C. King, Robert W. Floyd: An Interpretation Oriented Theorem Prover over Integers STOC 1970:169-179

Advertisements