**ROBERT FLOYD**

**ROBERT FLOYD**

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)**

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

tortoise = top hare = topforever:ifhare == end : return'No Loop Found'hare = hare.nextifhare == end : return'No Loop Found'hare = hare.next tortoise = tortoise.nextifhare == tortoise:return 'Loop Found'

How do you determine if your singly-linked list has a cycle? In the late **1960**s, 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**:

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

Hare and Tortoise starts at First Node of the List

Hare Tortoise1 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.

♣ Time Complexity: **O(n)**

♣ Space Complexity: **O(1) **

**Floyd-Warshall All-Pairs Shortest Pairs Algorithm**

**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.

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:

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.

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 2^{160}. 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*

*ROBERT FLOYD’S PUBLICATIONS*