4.3 Linked Structures

This section under major construction.

Linked structures. When writing computer programs, we are often faced with the problem of organizing huge quantities of related data. An array is a quintessential data structure for storing information that provides direct access to an element given its index. In this section we will consider more flexible user-defined mechanisms for associating related information that enables us to efficiently access elements and rearrange their order. In Sections XX, YY, and ZZ we will use linked structures to build useful higher level abstractions called stacks, queues, hash tables, binary search trees, and graphs. In this section we will concentrate on understanding their properties and how to implement them in Java. Knowing when and how to use linked structures is one of the defining skills that separates novice and advanced programmers.

List traversal.

One of the most common operations we perform on arrays and lists is to iterate over each element. The following idiomatic code prints out each of the items in a null-terminated linked list. We initialize a loop index variable x to reference the first node of the linked list. As long as x is not null, we print out it's value field. Then we update x to reference the next node on the linked list and repeat the process.

for (OneNode x = first; x != null; x = x.next)
    System.out.println(x.value);

See Exercise XYZ for traversing a circular linked list.

Arrays vs. linked lists. The main advantage of linked lists over arrays is flexibility. With arrays, we must specify the fixed size of the array when we declare it. With linked lists, we can gracefully add new nodes (until our system runs out of memory). A prime advantage of arrays over linked lists is that arrays provides random access to the elements: it is possible to directly access any element given its index. In contrast, linked lists provide only serial access: from a given node we can only directly access the next node. It is easy to efficiently simulate serial access with an array, but simulating random access with a linked list (See exercise XYZ) is inefficient. We can best understand the performance tradeoffs between arrays and linked lists by examining how they are represented in computer memory. When you create an array of one million elements, the system reserves enough space for exactly one million elements. This space is located consecutively in memory so that the system can access the ith element, given the memory address of the 0th element and the offset i. In contrast, when you create a linked list, the system allocated only one node at a time. Each node stores the memory address of the next node in the list. As a consequence, there is no need to store the linked list nodes consecutively in memory (or even specify the number of elements that the linked list will store ahead of time).

Elementary list processing. One of the prime advantages of a linked list is its flexibility. As a warmup, we first describe how to delete and insert a node into the middle of a linked list. Suppose that x is a linked list node and we want to delete the node immediately following x. Let y be a reference to the next node and z the one after that. We accomplish the deletion by changing the next field of x to be z. Assuming there are no outstanding references to the deleted node, the garbage collector will reclaim the memory once y changes values or goes out of scope.

OneNode y = x.next;
OneNode z = y.next;
x.next = z;

Suppose that x is a linked list node, and that we want to insert the linked list node t so that it immediately follows x. We achieve this by changing the next fields of both x and t.

OneNode y = x.next;
t.next = y;
x.next = t;

Functions on linked lists. It is easy to write functions that manipulate linked lists. As a first example, let's write a function count that takes as input a reference to the first node of a linked list and returns the total number of elements in the list, or 0 if the list is empty.

public static int count(OneNode list) {
   int n = 0;
   for (OneNode x = first; x != null; x = x.next)
      n++;
   return n;
}

There is an inherent ambiguity as to whether we view an object of type OneNode as a reference to a single node of a linked list or as a reference to linked list beginning at that node. Both interpretations are correct and can be used interchangeably. To emphasize which interpretation we are using, we name the variable list or first accordingly. We declare count as a classwide (static) method instead of an instance method because we want to be able to deal with empty linked lists. It is legal to pass null to a static method, but it is illegal to invoke an object method with null.

Since linked lists are defined recursively, it is natural to traverse a list using recursion. The following recursive function counts the number of elements in a linked list. The length of an empty linked list is zero (the base case), and the length of a non-empty linked list is one more than the length of the linked list starting at the second node.

public static int count(OneNode list) {
   if (list == null) return 0;
   OneNode rest = list.next;
   else return 1 + count(rest);
}

The recursive version is less efficient than the iterative version because it uses stack space proportional to the number of elements in the linked list (although an optimizing compiler might identify the tail recursion and convert it into the iterative version). Our main goal for showing the recursive version is that it is extremely useful when dealing with more complicated linked structures, including binary trees.

Trees. Trees are a mathematical abstraction that play a central role in the efficient organization of information. Like arrays and linked lists, a tree is a data type that stores a collection of data. Arrays and linked lists capture the ordered structure of elements in a collection. Trees are capable of capturing hierarchical structure. We are accustomed to many tree structures in everyday life including family trees, NCAA basketball tournament tree, the organization chart of a large company, and parse trees in grade school grammar. Trees also arise in numerous computer science applications including function call trees, parse trees, binary search trees, and file systems. However, many of their most prolific applications are rooted in science and engineering, including phylogenetic trees in computational biology, 2-d and k-d trees in computer graphics, minimax game trees in economics, and quad trees in molecular dynamics simulations.

Binary trees. Binary trees play an important role in computer programming because they strike a nice balance between flexibility and ease of implementation. A binary tree is defined recursively. It is a collection of nodes, where each each node contains some data plus two links to other nodes, called the left and right subtrees. Either or both links may be null. We assume all of the subtrees are disjoint. A binary tree node knows only about itself (some piece of data) and its left and right subtrees.

Binary trees in Java. Defining a binary tree in Java is almost exactly the same as a linked list, except that we allow for two links instead of one. For concreteness, we will describe how to create a linked list of strings. We implement a binary tree node as an object of type TwoNode: each node contains a reference to a string plus two references to other tree nodes.

public class TwoNode {
    private String value;
    private TwoNode left;
    private TwoNode right;
}

Program TwoNode.java illustrates how to create a binary tree of the five strings.

TwoNode a = new TwoNode();
a.value   = "10";
a.left    = null;
a.right   = null;

TwoNode b = new TwoNode();
b.value   = "12";
b.left    = null;
b.right   = null;

TwoNode c = new TwoNode();
c.value   = "*";
c.left    = a;
c.right   = b;

TwoNode d = new TwoNode();
d.value   = "7";
d.left    = null;
d.right   = null;

TwoNode e = new TwoNode();
e.value   = "+";
e.left    = c;
e.right   = d;

Functions on trees.

The number of elements in an empty binary tree is 0 (base case), and the number of elements in a non-empty binary tree is equal to one plus the number of elements in the left subtree plus the number of elements in the right subtree. We can quickly translate this into Java code. The following returns the number of nodes in the binary tree rooted at x.

public static int count(TwoNode x) {
   if (x == null) return 0;
   return 1 + count(x.left) + count(x.right);
}

Tree traversal.

W consider algorithms for the most basic tree-processing function: tree traversal: Given a (reference to) a tree, we want to process every node in the tree systematically. In a linked list, we move from one node to the next by following the single link; for trees, however, we have decisions to make, because there may be multiple links to follow. For linked lists, we had two basic options: process the node and then follow the link (in which case we would visit the nodes in order), or follow the link and then process the node (in which case we would visit the nodes in reverse order). For binary trees, we have two links, and we therefore have three basic orders in which we might visit the nodes:

Preorder: visit the node, then visit the left and right subtrees.
Inorder: visit the left subtree, then visit the node, then visit the right subtree.
Postorder: visit the left and right subtrees, then visit the node.

The sequences in the figure below indicate the order in which we visit nodes for a preorder(left), inorder (center), and postorder (right) tree traversal.

Preorder, inorder, and postorder traversal of a tree

Using recursion, it is easy to implement a preorder traversal as shown below.

public static void preorder(TwoNode x) {
   if (x == null) return;
   System.out.println(x.value);
   preorder(x.left);
   preorder(x.right);
}

To implement traversals in the other orders, we permute the calls in in the appropriate manner.

Parse trees. Give parse tree of English sentence. Similar ideas are extremely useful in deciphering arithmetic expressions. The program ParseTree.java reads in a preorder expression from standard input, explicitly builds a parse tree, and evaluates it. For example the prefix expression

* + + 4 5 * 6 7 8

corresponds so the infix expression (((4+5)+(6*7))*8) and is represented by the parse tree below.

Remark about s + " " + left + " " + right line and how Java knows to use concatenation.

Circuits. Create an abstract class Gate.java, and subclasses And.java, Or.java and Not.java to implement logic gates. Combine them to make Majority.java and OddParity.java. Caveat: exponential time to simulate if circuit components overlap.

Ancestor trees. Sometimes we want to create a binary tree where we can walk up the tree, in addition to walking down it. For example, in an ancestor tree, we might ask for the least common ancestor of two leaf nodes. Also useful in hierarchical clustering. In such situations we can define a tree node to have three links: one to the left child, one to the right child, and one to its parent.

public class ThreeNode {
    private String value;
    private ThreeNode left, right;
    private ThreeNode parent;
}

Program ThreeNode.java illustrates this procedure. It also includes a method to compute the least common ancestor, given references to two nodes.

Perspective on linked structures. Not all singly linked structures are linked lists (e.g., circular linked lists). Given a link to a collection of objects of type OneNode, each with a link to a OneNode, what can we say about its structural properties? Any path must end in a cycle or null, but paths could be shared. Parent-link trees. If we restrict each node to one incoming link, then it must be a linked list. Not all doubly-linked structures are doubly linked lists (e.g., binary tree). Given a link to a collection of objects of type TwoNode, each with two links to two TwoNodes, what can we say about its structural properties? If we restrict each node to have at most one incoming link, then it must be a binary tree. Branching program = exactly one source, two links per node, but no directed cycles.

Exercises

Draw using box-and-link notation the linked list that results from the following code fragment.

String s = "abracadabra";
OneNode first;
for (int i = 0; i < s.length(); i++) {
   OneNode x = new OneNode();
   x.value = s.substring(i, i+1);
   x.next  = first;
   first   = x;
}

Suppose that first is a reference to some OneNode on a circular linked list. Write a code fragment to iterate over the circular linked list and print out the string associated with each node. Solution: it's cleanest with a do-while loop.
OneNode x = first; do { System.out.println(x.value); x = x.next; } while (x != first)
Add a method count to Josephus that takes as input a TwoNode and returns the number of elements in the circular linked list.
Repeat the previous exercise with a circular linked list.
Suppose that you add the following toString method to OneNode. If the linked list beginning at node x is "3", "1", "4", "1", "5", "9", what does System.out.println(x) print?
public String toString() { return value + " " + next; }
Given a linked list with three integer elements, write a code fragment to rearrange list so that the elements are in increasing order.
Write an iterative method delete that takes an integer parameter k and inserts an item so that it becomes the kth element (assuming the list had at least k-1 elements to begin with).
Write an iterative method cut that divides the list into two (roughly) equal halves and puts the second half at the front of the first half.
Write an iterative method dedup that removes any duplicates from a sorted list of items.
Write an iterative method last that takes an integer argument and returns the last index of a Node containing that integer, or -1 if no such integer exists.
Write an iterative method penultimate returns the second to last element in the lined list, or null if the linked list has fewer than two elements.
Suppose we add the following constructor for OneNode.
public OneNode(String value, OneNode next) { this.value = value; this.next = next; } first = new OneNode("hello", first);
Why do the following two statements do?
OneNode first = null; first = new OneNode("hello", first);
Answer: it creates a null-terminated linked list of one node. Since first is null when the constructor is called, the result is equivalent to calling OneNode("hello", null). Thus, it does not create a circular linked list of one node as you might expect at first glance.
Write a program to build a null-terminated linked list containing the integers 1, 2, to N in order.
Write a program to build a circular linked list containing the integers 1, 2, to N in the order 1, N, N-1, ..., 2 by repeatedly adding each successive integer after the first node in the linked list.

Suppose that we pass the first OneNode of a null-terminated linked to mystery. Which OneNode is returned?

static Node(Node head) {
   Node x = head;
   Node xx = head;
   while(xx != null && xx.next != null) {
       x = x.next;
       xx = xx.next;
       xx = xx.next;
   }
   return x;
}

What does Mystery.java do?

public class Mystery {
   private Mystery x = new Mystery();

   public static void main(String[] args) {
      Mystery mystery = new Mystery();
   }
}

State variables get initialized before the body of the constructor. This creates an infinite recursive loop.

Give the preorder, inorder, postorder, and level-order traversals of the following binary trees.
Give the inorder and postorder traversal for the tree whose preorder traversal is
A B C - - D - - E - F -
The letters correspond to labeled internal nodes; the minus signs to external nodes.
Draw a binary tree of at least 5 nodes whose inorder traversal equals its preorder traversal.
How many tree shapes have the same preorder traversal as its postorder traversal?
Answer: two - a tree with zero or one nodes.
What happens if you try to create a new instance of type BrokenTwoNode?
public class BrokenTwoNode { private BrokenTwoNode left = new BrokenTwoNode(); private BrokenTwoNode right = new BrokenTwoNode(); private String = ""; }
Stack overflow. To create a new object, the initializers create two more objects, each of which creates two more objects, and so forth. This is an infinite recursive loop.
Give a binary tree with String values, write a method to print out all strings that are lexicographically less than a given value s.
Suppose that root is the root node of the following two-linked structure (not a binary tree). What is count(root)?
Answer: not what you expect.
A complete binary tree is a binary tree in which each level is completely filled. Write a method isComplete that takes a binary tree and returns true if it is complete, and false otherwise. Hint: call the methods count and depth.
The cost of a path in a tree is sum of the keys of the nodes participating in that path. Write a method that returns the cost of the most expensive path from the root to a leaf node.
Write a recursive method mirror that takes a binary tree and reverse the role of left and right. For example, it would replace the first tree with the second:
A A / \ / \ B C C B / \ \ \ / \ D E F F E D
A tree is min heap-ordered if the value stored in each child is greater than or equal to the value stored in its parent. Write a method isHeapOrdered that takes a binary tree and returns true if the tree is heap ordered, and false otherwise.
Consider the parse tree whose preorder traversal is
* * + 1 2 + * 3 4 5 6
What is the value of the parse tree (or equivalently of the above traversal interpreted as a prefix expression)?
What's wrong with the following program?
public class Tree { int value = 0; Tree left = new Tree(); Tree right = new Tree(); public static void main(String[] args) { Tree t = new Tree(); } }
It compiles, but produces a StackOverFlowError because the (no-argument) constructor is called recursively, and there is no base case.

Creative Exercises

Prefix trees. See data compression assignment.
Circular linked lists. A circular linked list is similar to a linked list in that each node contains data (e.g., a string) and a reference to the next element in the list. However, the last element in the list points back to the first node. This models situations where the elements are ordered, but there is no "first" element, e.g., knights sitting at a round table. Imagine that N knights have decided to elect a leader by sitting at a round table and eliminating every Mth person around the circle. To simulate this process, we build a circular linked list of the N knights, 1-2-3-4-5-6-7-8-9-1. Then we proceed to eliminate every 5th person. After the first round, 5 is eliminated and the linked lists contains 1-2-3-4-6-7-8-9-1. Then 1 is eliminated, and so on. Write a program Josephus.java to model this process.
Polynomials. A univariate polynomial of degree n is a function of the form where a_n is nonzero.

For example, 17x³ + 5x + 1 or x^1000000 - 1. Implement a polynomial using a real array a of size N+1 where a[i] stores the coefficient a_i.
Sparse polynomial. Implement a polynomial ADT that stores a linked list of only those coefficients that are nonzero, say with the following subclass
public class Term { private double coef; private int exp; private Term next; }
Polynomial tradeoff. The following questions compare the array and linked list implementations of a polynomial described above. Answer in terms of running time and memory consumption. Which implementation would you prefer if the polynomial is large, but dense? If the polynomial is huge and very sparse? If the polynomial is small?
Visualization of a binary tree. Add a method draw to ParseTree.java so that it plots the resulting parse tree. Name your program DrawableParseTree.java.
Random element of a linked list. Given a linked list, return an element of the list chosen uniformly at random. You may only make one pass through the list. Hint: traverse the list and maintain the "champion." When considering the ith element, make it the champion with probability 1/i.
Animated Josephus. Write a program to animate the Josephus elimination. Draw the N people in a circle and label each one with an integer from 1 to N. Connect them with lines, and when a person is eliminated, remove them from the circle.
Farey sequence. The Farey sequence of order N is the increasing sequence of all rational numbers (in lowest common form) between 0 and 1 whose numerator and denominator are integers between 0 and 1.
0: 0/1 1/1 1: 0/1 1/2 1/1 2: 0/1 1/3 1/2 2/3 1/1 3: 0/1 1/4 1/3 1/2 2/3 3/4 1/1 4: 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
Write a program Farey.java that takes a command line parameter N and prints the Farey sequence of order N. To generate the Farey sequence of order N, start with the list { 0/1, 1/1 } and make N-1 passes. That is, for each pair of neighboring rational numbers a/b and c/d, insert (a+c)/(b+d) assuming neither a+c or b+d is too big.
Insertion sort on linked lists.
Maze. Redo the maze generation and maze solver using OOP principles. Create a class Cell.java that represents a grid cell. It should know its four neighboring cells and the status of its four adjoining walls. It should also be able to draw itself using turtle graphics. Write a program Maze.java that takes a command line argument N and generates an N-by-N perfect maze and solves it.
Necklace. Given a necklace and black and white beads, determine the maximum number of consecutive beads of any one color. Assume the necklace is represented as a circular linked list, and the color is represented as false (white) or true (black).
Necklace with wildcards. Repeat the previous exercise, but assume there are red beads (2) as well. Find the maximum number of consecutive beads, but count the red beads as blanks which match either white or black.
Jotto. (Bob Vanderbei) Jotto is a word game where the first player chooses a secret 5 letter word. The second player tries to guess the secret word. After each guess, the first player states the number of letters (jots) that the guessed word has in common with the secret word.
1. Write a computer program for the first player. Choose a secret word at random from a list of 5 letters words that you read in from a file. Then, repeatedly prompt the user for 5 letter words. Calculate the number of jots for each guess and print it to the screen. End the game when the user guesses the correct word.
2. Write a computer program for the second player. Read in a list of 5 letters words from a file and store them in a linked list. Select a random word from the list and use it as your guess. Prompt the user for the number of jots with your random word, and delete all remaining words on the linked list that have a different number of jots. Repeat this process until there is only one word remaining (or all of the remaining words are anagrams) or the list is empty (the user cheated).
Floyd's cycle algorithm. Given a reference to the beginning of a linked list data structure, determine whether the "list" is a linear list or whether it is a path that leads to a cycle.
Solution: maintain two references x and xx. Set x = x.next and xx = xx.next.next. Repeat until xx or xx.next is null (a linear linked list) or until x == xx (a cycle).
Out of fuel. Suppose that there are N fuel stations along the DC beltway. You need G gallons of fuel to drive around and the total amount of fuel available in all of the fuel stations is equal to G. You must drive in a counterclockwise direction. You start with 0 gallons. At which station should you start to make it around the beltway without running out of fuel? Assume the input is presented to you as a circular linked list, where each node contains a real number representing the amount of fuel at that station and the amount of fuel needed to get to the next station.
Doubly linked list. A doubly linked list. Use: fast deletion of objects other than front or back. Application: window manager stores a list of windows. When user clicks, their window comes to the front.
Doubly linked list deletion. Given a reference to a node in a doubly linked list, delete that node.
Postfix expression. Replace the toString method in ParseTree.java above with the following. What is the result of printing out the parse tree above.
public String toString() { if (s.equals("+") || s.equals("*")) return left + " " + right + " " + s; else return s; }
Infix expression. Rewrite the toString method in ParseTree.java so that it prints out the infix representation of the arithmetic expression using parentheses as needed, e.g, (((4 + 5) + (6 * 7)) * 8) for the parse tree above.
public String toString() { if (s.equals("+") || s.equals("*")) return "(" + left + " " + s + " " + right + ")"; else return s; }
Binary tree iterator. Create an iterator for binary trees so that you can iterate through the nodes of a binary tree in preorder. Use "threaded tree" or maintain a stack.
Prefix free codes. Many data compression schemes (including Huffman codes) are based on encoding a set of symbols using a variable number of bits. A code is called prefix free if no codeword is a prefix of another. For example, the first code below is prefix-free, but the second is not since A is a prefix of C.
A:01 B:10 C:0010 D:0000 A:01 B:10 C:010 D:0000
Write a program to read in a list of codewords and print true if it is prefix-free and false otherwise. Hint: build a trie (or sort).
LZW compression. Use binary trie for binary input.
Parse tree from postfix expression. Read in a postfix expression and create the corresponding parse tree. Read in the elements of the postfix expression one at a time. When you get an integer, create a parse tree of one node containing that integer and push it onto a stack. When you get an operator, pop two trees off the stack, create a tree with the operator as the root and the two trees as the children, then push this tree back onto the stack.
Tree copy constructor. Create a copy constructor that takes as input a reference to a tree and creates a (deep) copy of a new tree. Assume the input is not null.
// untested public Tree(Tree x) { item = x.item; if (x.left != null) left = new Tree(x.left); if (x.right != null) right = new Tree(x.right); }
Tree sum. Give a binary tree of integers and a target sum S, find a path from the root to a leaf whose values sum to exactly S or report that no such path exists.
Least common ancestor. Given two nodes in a family tree where each node points to two parents, find their least common ancestor.
Family tree. In a family tree each member has a reference to their two parents. Given a family tree and references to two members x and y, determine their genetic relationship. If x is on the path from y to the root then x is a parent, grand parent, great grand parent, etc of y. If y is on the path from x to the root, then x is a child, grand child, great grand child of y. Otherwise, to determine what form of cousin relationship the two family members have, we define lca(x, y) to be the least common ancestor of x and y. Now, x and y are kth cousins, jth removed, where j = |m-n|, k = min(m, n), m is the length of the path from x to lca(x, y) and n is the length of the path from y to lca(x, y). If j = k = 0, then x and y are siblings.
Single-link hierarchical clustering. Creates a dendrogram or taxonomy of points. Repeatedly find two closest points not in the same cluster and merge them. (Hierarchical agglomerative clustering.)
Geneological tree. Argue why a geneological tree (e.g., British royalty) is not a tree.
Answer: inbreeding and overlap. This is inevitable since you would need exponentially many distinct people at level N.

Web Exercises and Unfinished Exercises

Windows manager. Use a linked lists of overlapping rectangles to model a bunch of open Windows. Allow the user to select a window and bring it to the front by moving that element to the beginning of the linked list. Here's a related Berkeley assignment.
Phylogenetic alignment. Given a tree T with distinct strings in each leaf, the phylogenetic alignment problem is to find an assignment of strings to the internal nodes of T that minimizes the sum of the edit distances between adjacent nodes. This phylogeny tree represents the evolutionary history of a set of species of interest and the differences between adjacent nodes represent mutations. Gusfield (p. 355) gives a dynamic programming heuristic that finds a provably good solution to this NP-hard optimization problem.

Zip code database. Create a database of US zip codes and town. There may be more than one zip code for a given town. Here is data from the 1990 Census. The format is: state Fips code, 5 digit zip code, USPS state abbreviation, town name, longitude (in decimal degrees, West is assumed with no minus sign), latitude (North is assumed with no plus sign), 1990 population, allocation factor (decimal portion of state within zipcode).

"34","08540","NJ","PRINCETON",74.640832,40.366633,33831,0.004376 
"34","08542","NJ","PRINCETON",74.659378,40.353545,2675,0.000346 
"34","08544","NJ","PRINCETON UNIVER",74.65754,40.346029,4227,0.000547 
"34","08550","NJ","PRINCETON JUNCTI",74.614596,40.297684,5807,0.000751 
"37","27569","NC","PRINCETON",78.167368,35.455833,5378,0.000811

Note that the same town name be appear in different states. See also the US Gazetteer.

Write a program that reads in two US zip codes and computes the approximate great circle distance between them. Given the latitude and longitude (L1, G1) and (L2, G2) of two points in degrees, the great circle distance is computed using spherical trigonometry:
D = 1.852 * 60 * arccos(sin(L1)*sin(L2) + cos(L1)*cos(L2)*cos(DG))
We assume 1 minute of arc is 1 nautical mile and 1 nautical mile is 1.852 km. All angles are in degrees.
Use data from the 2000 Census. The data format is: 5 digit zip code, followed by longitude, followed by latitude.
00210 71.0132 43.00589
Reference: this website. Variant: read in a zip code and compute all zip codes within 5 miles.
Something with states and area codes? Each state has one or more three digit area codes; some three digit area codes don't correspond to any state....
Given a binary tree (of inheritance relationships), determine if one class is a subclass of another. Or more generally, do least common ancestor.
Given a singly linked list of OneNodes, describe how to traverse the list in either direction so that given an arbitrary sequence (e.g., FFFFFFBBBFBFBBFFFBBBBFFFBFBF) you can print out the contents of each node.
Hint: reverse the links as you go forward, restore them as you go backwards.
Self-adjusting lists.
Perfect shuffling. A perfect shuffle of a deck of cards consists of cutting the deck into two equal piles, and then interleaving the cards from each pile. A perfect in-shuffle of the cards A B C D E F G H results in E A F B G C H D whereas a perfect out-shuffle results in A E B F C G D H. Write a program that takes a command line argument N and performs N perfect out-shuffles. Note: perfect shuffling arises in a number of parallel algorithms for signal processing applications, including the Fast Fourier Transform.
Perfect in-shuffles. Write a program to determine how many perfect out-shuffles it takes for a deck of 52 cards to return to its original order? How many perfect in-shuffles?
Answer: 8 and 52, respectively.
Perfect shuffling magic. Several card tricks rely on the magician to be able to perform perfect shuffles. Show that you can move the top card in a 52 card deck to any location by using the right combination of 8 perfect in-shuffles and out-shuffles. Write a program that takes a command line argument N (between 0 and 51) and performs 8 perfect shuffles so that the top card ends up in position N. Hint: consider N in binary (from left to right) and perform a perfect out-shuffle if the bit is 0, and a perfect in-shuffle if the bit is 1.
Top-in shuffle. Create a linked list of N playing cards. Repeatedly take the top card and reinsert it in any of the N positions between the N-1 remaining cards uniformly at random. Repeat until the original bottom card is reinserted for the first time. Remark: this produces a uniformly shuffled deck in about N log N reinsertions!
Riffle shuffle. Realist model of how N cards are shuffled (Gilbert-Shannon-Reeds). Cut the deck into two hands of size k and N-k, where k is chosen according to the binomial distribution (flip N fair coins and count the number of heads). Then, interleave (riffle) the cards in each hand at random: when you have l cards remaining in the left hand and r in the right hand, choose the "next" card from your left hand with probability l/(r+l), and from your right hand with probability r/(r+l). (Equivalent: label each card 0 or 1 according to a fair coin flip. Remove all of the cards labeled 0 and put them on top, followed by all the cards labeled 1, keeping the cards with the same relative order.)
Shuffling reference. Aldous, Bayer and Diaconis proved that the deck is close to uniformly shuffled (in variation norm) after 3/2 lg N shuffles (asymptotically as N approaches infinity). For a 52-card deck they concluded that you need at least 5 shuffles for reasonable randomization and recommended 7. Measuring randomness in a different way (entropy) Trefethen and Trefethen argue that 6 shuffles is enough.
Shuffle a linked list. Design an O(N log N) worst-case algorithm for shuffling a linked list that uses O(log N) or O(1) extra space.
Game tree.
Random parse tree. Write a constructor to generate a random parse tree. Assume for each node, the probability of including a + or * is p/2, and the probability of including one of the digits 0-9 is (1-p)/10. What is the average height of the tree as a function of p?
Random dendrogram. Start with a binary tree with two leaves. Random select a leaf, and add a new leaf to it. Repeat until you have the desired number of leaves. Randomly assign a label to each leaf.
Random trees. Useful in zoology. Random unlabelled trees, random labelled trees, Program RandomPreorder.java generates the preorder traversal of a random, rooted, labeled, binary tree.
Cladograms. Fancy name for ancestor trees. Cladistics.
Shortest sequence containing a given subsequence. Write a program Subsequence.java that reads in a text corpus from standard input and a sequence of query words from the command line, and finds the shortest sequence of words in the corpus for which the query sequence is a subsequence.
PQ trees. PQ trees are used for planarity testing and for creating contig map from DNA fragments.
Last node visited in a cycle. Create a circular, doubly-linked list with N nodes. Designate one node s as the starting point. Simulate a random walk around the cycle (moving clockwise with probability 1/2 and counterclockwise with probability 1/2) until every node has been visited at least once. Analyze the fraction of times each node (other than s) is the last one to be visited.
Solution: each node is equally likely.